https://wiki.cs.hse.ru/api.php?action=feedcontributions&feedformat=atom&user=Gusakov 2026-09-21T14:28:31Z Вклад MediaWiki 1.43.9 https://wiki.cs.hse.ru/index.php?title=%D0%A3%D1%87%D0%B8%D0%BC%D1%81%D1%8F_%D0%B8%D0%B3%D1%80%D0%B0%D1%82%D1%8C_%D0%B2_%D0%BD%D0%B0%D1%80%D0%B4%D1%8B_(%D0%BF%D1%80%D0%BE%D0%B5%D0%BA%D1%82)&diff=17573 2015-11-20T15:00:08Z

<p>Gusakov: /* Критерии оценки */</p> <hr /> <div>{{Карточка_проекта<br /> |name=Учимся играть в нарды<br /> |mentor=Алексей Гусаков<br /> |mentor_login={{URLENCODE:Gusakov|WIKI}}<br /> |semester=Весна 2016<br /> |course=1<br /> |summer=on<br /> |number_of_students=10<br /> |categorize=yes<br /> }}<br /> <br /> === Что это за проект? ===<br /> Проект заключается в том, чтобы научить компьютер играть в нарды.<br /> Делать мы это будем с помощью машинного обучения, причём все знания, которые алгоритм имеет о мире ограничиваются тем, какие ходы возможны из конкретной позиции и тем, какой же получился результат в конце (победа или поражение).<br /> Оказывается, что за несколько тысяч игр компьютер учится неплохо играть, а при более тщательном подходе обыгрывает человека.<br /> <br /> === Чему вы научитесь? ===<br /> Основы машинного обучения, методы линейной регрессии, понятие о нейросетях, temporal-difference learning.<br /> <br /> === Какие начальные требования? ===<br /> Интерес к машинному обучению, желание экспериментировать и упорно работать.<br /> Будет прикольно, но не просто.<br /> <br /> === Какие будут использоваться технологии? ===<br /> c++, gtest,<br /> scikit-learn<br /> <br /> === Темы вводных занятий ===<br /> Для начала немного поиграем в нарды.<br /> <br /> Потом обсудим интерфейсы, тесты, базовые решения, time-difference learning.<br /> <br /> === Направления развития ===<br /> Можно совершенствовать алгоритм машинного обучения, находя/генерируя автоматически факторы.<br /> Ещё одним развитием проекта является хорошая визуализация игры.<br /> <br /> === Критерии оценки ===<br /> 4 балла: Написан класс, описывающий позицию, реализованы правила, по которым делаются ходы.<br /> <br /> + балл (итого 5): Класс хорошо покрыт тестами.<br /> <br /> + балл (итого 6): Реализован механизм сравнения разных алгоритмов, есть несколько базовых реализаций алгоритма.<br /> <br /> + балл (итого 7): Реализован алгоритм, основанный на линейной модели, который побеждает все базовые подходы.<br /> <br /> + 2 балла (итого 9): То же самое, но на основе более глубокой нейоронной сети.<br /> <br /> + балл (итого 10): Как-то реализована визуализация, в результате чего можно и человеку сразиться с программой.<br /> <br /> Также между алгоритмами будет проведён турнир на спецприз от ментора :)<br /> <br /> === Ориентировочное расписание занятий ===<br /> В идеале - вечер пятницы или утро субботы.</div>

Gusakov https://wiki.cs.hse.ru/index.php?title=%D0%A3%D1%87%D0%B8%D0%BC%D1%81%D1%8F_%D0%B8%D0%B3%D1%80%D0%B0%D1%82%D1%8C_%D0%B2_%D0%BD%D0%B0%D1%80%D0%B4%D1%8B_(%D0%BF%D1%80%D0%BE%D0%B5%D0%BA%D1%82)&diff=17572 2015-11-20T14:59:37Z

<p>Gusakov: /* Темы вводных занятий */</p> <hr /> <div>{{Карточка_проекта<br /> |name=Учимся играть в нарды<br /> |mentor=Алексей Гусаков<br /> |mentor_login={{URLENCODE:Gusakov|WIKI}}<br /> |semester=Весна 2016<br /> |course=1<br /> |summer=on<br /> |number_of_students=10<br /> |categorize=yes<br /> }}<br /> <br /> === Что это за проект? ===<br /> Проект заключается в том, чтобы научить компьютер играть в нарды.<br /> Делать мы это будем с помощью машинного обучения, причём все знания, которые алгоритм имеет о мире ограничиваются тем, какие ходы возможны из конкретной позиции и тем, какой же получился результат в конце (победа или поражение).<br /> Оказывается, что за несколько тысяч игр компьютер учится неплохо играть, а при более тщательном подходе обыгрывает человека.<br /> <br /> === Чему вы научитесь? ===<br /> Основы машинного обучения, методы линейной регрессии, понятие о нейросетях, temporal-difference learning.<br /> <br /> === Какие начальные требования? ===<br /> Интерес к машинному обучению, желание экспериментировать и упорно работать.<br /> Будет прикольно, но не просто.<br /> <br /> === Какие будут использоваться технологии? ===<br /> c++, gtest,<br /> scikit-learn<br /> <br /> === Темы вводных занятий ===<br /> Для начала немного поиграем в нарды.<br /> <br /> Потом обсудим интерфейсы, тесты, базовые решения, time-difference learning.<br /> <br /> === Направления развития ===<br /> Можно совершенствовать алгоритм машинного обучения, находя/генерируя автоматически факторы.<br /> Ещё одним развитием проекта является хорошая визуализация игры.<br /> <br /> === Критерии оценки ===<br /> 4 балл: Написан класс, описывающий позицию, реализованы правила, по которым делаются ходы.<br /> + балл (итого 5): Класс хорошо покрыт тестами.<br /> + балл (итого 6): Реализован механизм сравнения разных алгоритмов, есть несколько базовых реализаций алгоритма.<br /> + балл (итого 7): Реализован алгоритм, основанный на линейной модели, который побеждает все базовые подходы.<br /> + 2 балла (итого 9): То же самое, но на основе более глубокой нейоронной сети.<br /> + балл (итого 10): Как-то реализована визуализация, в результате чего можно и человеку сразиться с программой.<br /> <br /> Также между алгоритмами будет проведён турнир на спецприз от ментора :)<br /> <br /> === Ориентировочное расписание занятий ===<br /> В идеале - вечер пятницы или утро субботы.</div>

Gusakov https://wiki.cs.hse.ru/index.php?title=%D0%A3%D1%87%D0%B8%D0%BC%D1%81%D1%8F_%D0%B8%D0%B3%D1%80%D0%B0%D1%82%D1%8C_%D0%B2_%D0%BD%D0%B0%D1%80%D0%B4%D1%8B_(%D0%BF%D1%80%D0%BE%D0%B5%D0%BA%D1%82)&diff=17570 2015-11-20T14:56:02Z

<p>Gusakov: /* Что это за проект? */</p> <hr /> <div>{{Карточка_проекта<br /> |name=Учимся играть в нарды<br /> |mentor=Алексей Гусаков<br /> |mentor_login={{URLENCODE:Gusakov|WIKI}}<br /> |semester=Весна 2016<br /> |course=1<br /> |summer=on<br /> |number_of_students=10<br /> |categorize=yes<br /> }}<br /> <br /> === Что это за проект? ===<br /> Проект заключается в том, чтобы научить компьютер играть в нарды.<br /> Делать мы это будем с помощью машинного обучения, причём все знания, которые алгоритм имеет о мире ограничиваются тем, какие ходы возможны из конкретной позиции и тем, какой же получился результат в конце (победа или поражение).<br /> Оказывается, что за несколько тысяч игр компьютер учится неплохо играть, а при более тщательном подходе обыгрывает человека.<br /> <br /> === Чему вы научитесь? ===<br /> Основы машинного обучения, методы линейной регрессии, понятие о нейросетях, temporal-difference learning.<br /> <br /> === Какие начальные требования? ===<br /> Интерес к машинному обучению, желание экспериментировать и упорно работать.<br /> Будет прикольно, но не просто.<br /> <br /> === Какие будут использоваться технологии? ===<br /> c++, gtest,<br /> scikit-learn<br /> <br /> === Темы вводных занятий ===<br /> <br /> <br /> === Направления развития ===<br /> Можно совершенствовать алгоритм машинного обучения, находя/генерируя автоматически факторы.<br /> Ещё одним развитием проекта является хорошая визуализация игры.<br /> <br /> === Критерии оценки ===<br /> 4 балл: Написан класс, описывающий позицию, реализованы правила, по которым делаются ходы.<br /> + балл (итого 5): Класс хорошо покрыт тестами.<br /> + балл (итого 6): Реализован механизм сравнения разных алгоритмов, есть несколько базовых реализаций алгоритма.<br /> + балл (итого 7): Реализован алгоритм, основанный на линейной модели, который побеждает все базовые подходы.<br /> + 2 балла (итого 9): То же самое, но на основе более глубокой нейоронной сети.<br /> + балл (итого 10): Как-то реализована визуализация, в результате чего можно и человеку сразиться с программой.<br /> <br /> Также между алгоритмами будет проведён турнир на спецприз от ментора :)<br /> <br /> === Ориентировочное расписание занятий ===<br /> В идеале - вечер пятницы или утро субботы.</div>

Gusakov https://wiki.cs.hse.ru/index.php?title=%D0%A3%D1%87%D0%B8%D0%BC%D1%81%D1%8F_%D0%B8%D0%B3%D1%80%D0%B0%D1%82%D1%8C_%D0%B2_%D0%BD%D0%B0%D1%80%D0%B4%D1%8B_(%D0%BF%D1%80%D0%BE%D0%B5%D0%BA%D1%82)&diff=17569 2015-11-20T14:53:56Z

<p>Gusakov: /* Какие начальные требования? */</p> <hr /> <div>{{Карточка_проекта<br /> |name=Учимся играть в нарды<br /> |mentor=Алексей Гусаков<br /> |mentor_login={{URLENCODE:Gusakov|WIKI}}<br /> |semester=Весна 2016<br /> |course=1<br /> |summer=on<br /> |number_of_students=10<br /> |categorize=yes<br /> }}<br /> <br /> === Что это за проект? ===<br /> Проект заключается в том, чтобы научить компьютер играть в нарды.<br /> Делать мы это будем с помощью машинного обучения, причём все знания, которые мы передаём алгоритму минимальные - он знает, какие ходы возможны из какой позиции, а в конце игры узнаёт результат.<br /> Оказывается, что за несколько тысяч игр компьютер учится неплохо играть, а при более тщательном подходе обыгрывает человека.<br /> <br /> === Чему вы научитесь? ===<br /> Основы машинного обучения, методы линейной регрессии, понятие о нейросетях, temporal-difference learning.<br /> <br /> === Какие начальные требования? ===<br /> Интерес к машинному обучению, желание экспериментировать и упорно работать.<br /> Будет прикольно, но не просто.<br /> <br /> === Какие будут использоваться технологии? ===<br /> c++, gtest,<br /> scikit-learn<br /> <br /> === Темы вводных занятий ===<br /> <br /> <br /> === Направления развития ===<br /> Можно совершенствовать алгоритм машинного обучения, находя/генерируя автоматически факторы.<br /> Ещё одним развитием проекта является хорошая визуализация игры.<br /> <br /> === Критерии оценки ===<br /> 4 балл: Написан класс, описывающий позицию, реализованы правила, по которым делаются ходы.<br /> + балл (итого 5): Класс хорошо покрыт тестами.<br /> + балл (итого 6): Реализован механизм сравнения разных алгоритмов, есть несколько базовых реализаций алгоритма.<br /> + балл (итого 7): Реализован алгоритм, основанный на линейной модели, который побеждает все базовые подходы.<br /> + 2 балла (итого 9): То же самое, но на основе более глубокой нейоронной сети.<br /> + балл (итого 10): Как-то реализована визуализация, в результате чего можно и человеку сразиться с программой.<br /> <br /> Также между алгоритмами будет проведён турнир на спецприз от ментора :)<br /> <br /> === Ориентировочное расписание занятий ===<br /> В идеале - вечер пятницы или утро субботы.</div>

Gusakov https://wiki.cs.hse.ru/index.php?title=%D0%A3%D1%87%D0%B8%D0%BC%D1%81%D1%8F_%D0%B8%D0%B3%D1%80%D0%B0%D1%82%D1%8C_%D0%B2_%D0%BD%D0%B0%D1%80%D0%B4%D1%8B_(%D0%BF%D1%80%D0%BE%D0%B5%D0%BA%D1%82)&diff=17568 2015-11-20T14:53:42Z

<p>Gusakov: /* Какие начальные требования? */</p> <hr /> <div>{{Карточка_проекта<br /> |name=Учимся играть в нарды<br /> |mentor=Алексей Гусаков<br /> |mentor_login={{URLENCODE:Gusakov|WIKI}}<br /> |semester=Весна 2016<br /> |course=1<br /> |summer=on<br /> |number_of_students=10<br /> |categorize=yes<br /> }}<br /> <br /> === Что это за проект? ===<br /> Проект заключается в том, чтобы научить компьютер играть в нарды.<br /> Делать мы это будем с помощью машинного обучения, причём все знания, которые мы передаём алгоритму минимальные - он знает, какие ходы возможны из какой позиции, а в конце игры узнаёт результат.<br /> Оказывается, что за несколько тысяч игр компьютер учится неплохо играть, а при более тщательном подходе обыгрывает человека.<br /> <br /> === Чему вы научитесь? ===<br /> Основы машинного обучения, методы линейной регрессии, понятие о нейросетях, temporal-difference learning.<br /> <br /> === Какие начальные требования? ===<br /> Интерес к машинному обучению, желание экспериментировать и упорно работать.<br /> Будет прикольно, но непросто.<br /> <br /> === Какие будут использоваться технологии? ===<br /> c++, gtest,<br /> scikit-learn<br /> <br /> === Темы вводных занятий ===<br /> <br /> <br /> === Направления развития ===<br /> Можно совершенствовать алгоритм машинного обучения, находя/генерируя автоматически факторы.<br /> Ещё одним развитием проекта является хорошая визуализация игры.<br /> <br /> === Критерии оценки ===<br /> 4 балл: Написан класс, описывающий позицию, реализованы правила, по которым делаются ходы.<br /> + балл (итого 5): Класс хорошо покрыт тестами.<br /> + балл (итого 6): Реализован механизм сравнения разных алгоритмов, есть несколько базовых реализаций алгоритма.<br /> + балл (итого 7): Реализован алгоритм, основанный на линейной модели, который побеждает все базовые подходы.<br /> + 2 балла (итого 9): То же самое, но на основе более глубокой нейоронной сети.<br /> + балл (итого 10): Как-то реализована визуализация, в результате чего можно и человеку сразиться с программой.<br /> <br /> Также между алгоритмами будет проведён турнир на спецприз от ментора :)<br /> <br /> === Ориентировочное расписание занятий ===<br /> В идеале - вечер пятницы или утро субботы.</div>

Gusakov https://wiki.cs.hse.ru/index.php?title=%D0%A3%D1%87%D0%B8%D0%BC%D1%81%D1%8F_%D0%B8%D0%B3%D1%80%D0%B0%D1%82%D1%8C_%D0%B2_%D0%BD%D0%B0%D1%80%D0%B4%D1%8B_(%D0%BF%D1%80%D0%BE%D0%B5%D0%BA%D1%82)&diff=17567 2015-11-20T14:52:54Z

<p>Gusakov: /* Какие будут использоваться технологии? */</p> <hr /> <div>{{Карточка_проекта<br /> |name=Учимся играть в нарды<br /> |mentor=Алексей Гусаков<br /> |mentor_login={{URLENCODE:Gusakov|WIKI}}<br /> |semester=Весна 2016<br /> |course=1<br /> |summer=on<br /> |number_of_students=10<br /> |categorize=yes<br /> }}<br /> <br /> === Что это за проект? ===<br /> Проект заключается в том, чтобы научить компьютер играть в нарды.<br /> Делать мы это будем с помощью машинного обучения, причём все знания, которые мы передаём алгоритму минимальные - он знает, какие ходы возможны из какой позиции, а в конце игры узнаёт результат.<br /> Оказывается, что за несколько тысяч игр компьютер учится неплохо играть, а при более тщательном подходе обыгрывает человека.<br /> <br /> === Чему вы научитесь? ===<br /> Основы машинного обучения, методы линейной регрессии, понятие о нейросетях, temporal-difference learning.<br /> <br /> === Какие начальные требования? ===<br /> Интерес к машинному обучению, желание экспериментировать и упорно работать.<br /> <br /> === Какие будут использоваться технологии? ===<br /> c++, gtest,<br /> scikit-learn<br /> <br /> === Темы вводных занятий ===<br /> <br /> <br /> === Направления развития ===<br /> Можно совершенствовать алгоритм машинного обучения, находя/генерируя автоматически факторы.<br /> Ещё одним развитием проекта является хорошая визуализация игры.<br /> <br /> === Критерии оценки ===<br /> 4 балл: Написан класс, описывающий позицию, реализованы правила, по которым делаются ходы.<br /> + балл (итого 5): Класс хорошо покрыт тестами.<br /> + балл (итого 6): Реализован механизм сравнения разных алгоритмов, есть несколько базовых реализаций алгоритма.<br /> + балл (итого 7): Реализован алгоритм, основанный на линейной модели, который побеждает все базовые подходы.<br /> + 2 балла (итого 9): То же самое, но на основе более глубокой нейоронной сети.<br /> + балл (итого 10): Как-то реализована визуализация, в результате чего можно и человеку сразиться с программой.<br /> <br /> Также между алгоритмами будет проведён турнир на спецприз от ментора :)<br /> <br /> === Ориентировочное расписание занятий ===<br /> В идеале - вечер пятницы или утро субботы.</div>

Gusakov https://wiki.cs.hse.ru/index.php?title=%D0%A3%D1%87%D0%B8%D0%BC%D1%81%D1%8F_%D0%B8%D0%B3%D1%80%D0%B0%D1%82%D1%8C_%D0%B2_%D0%BD%D0%B0%D1%80%D0%B4%D1%8B_(%D0%BF%D1%80%D0%BE%D0%B5%D0%BA%D1%82)&diff=17566 2015-11-20T14:52:28Z

<p>Gusakov: Новая страница, с помощью формы Новый_проект</p> <hr /> <div>{{Карточка_проекта<br /> |name=Учимся играть в нарды<br /> |mentor=Алексей Гусаков<br /> |mentor_login={{URLENCODE:Gusakov|WIKI}}<br /> |semester=Весна 2016<br /> |course=1<br /> |summer=on<br /> |number_of_students=10<br /> |categorize=yes<br /> }}<br /> <br /> === Что это за проект? ===<br /> Проект заключается в том, чтобы научить компьютер играть в нарды.<br /> Делать мы это будем с помощью машинного обучения, причём все знания, которые мы передаём алгоритму минимальные - он знает, какие ходы возможны из какой позиции, а в конце игры узнаёт результат.<br /> Оказывается, что за несколько тысяч игр компьютер учится неплохо играть, а при более тщательном подходе обыгрывает человека.<br /> <br /> === Чему вы научитесь? ===<br /> Основы машинного обучения, методы линейной регрессии, понятие о нейросетях, temporal-difference learning.<br /> <br /> === Какие начальные требования? ===<br /> Интерес к машинному обучению, желание экспериментировать и упорно работать.<br /> <br /> === Какие будут использоваться технологии? ===<br /> c++, gtest<br /> scikit-learn<br /> <br /> === Темы вводных занятий ===<br /> <br /> <br /> === Направления развития ===<br /> Можно совершенствовать алгоритм машинного обучения, находя/генерируя автоматически факторы.<br /> Ещё одним развитием проекта является хорошая визуализация игры.<br /> <br /> === Критерии оценки ===<br /> 4 балл: Написан класс, описывающий позицию, реализованы правила, по которым делаются ходы.<br /> + балл (итого 5): Класс хорошо покрыт тестами.<br /> + балл (итого 6): Реализован механизм сравнения разных алгоритмов, есть несколько базовых реализаций алгоритма.<br /> + балл (итого 7): Реализован алгоритм, основанный на линейной модели, который побеждает все базовые подходы.<br /> + 2 балла (итого 9): То же самое, но на основе более глубокой нейоронной сети.<br /> + балл (итого 10): Как-то реализована визуализация, в результате чего можно и человеку сразиться с программой.<br /> <br /> Также между алгоритмами будет проведён турнир на спецприз от ментора :)<br /> <br /> === Ориентировочное расписание занятий ===<br /> В идеале - вечер пятницы или утро субботы.</div>

Gusakov https://wiki.cs.hse.ru/index.php?title=2048_(%D0%BF%D1%80%D0%BE%D0%B5%D0%BA%D1%82)&diff=16764 2015-06-15T08:35:16Z

<p>Gusakov: </p> <hr /> <div>{{Карточка_проекта<br /> |name=2048<br /> |mentor=Алексей Гусаков<br /> |mentor_login={{URLENCODE:Gusakov|WIKI}}<br /> |semester=Весна 2015<br /> |course=1<br /> |summer=<br /> |categorize=yes<br /> }}<br /> <br /> === Что это за проект? ===<br /> 2048 - игра, известная многим офисным работникам. В неё можно играть онлайн, например, здесь http://go2048.com/<br /> <br /> Цель проекта - создать бота, который будет набирать больше, чем могут люди.<br /> <br /> === Чему вы научитесь? ===<br /> * Переборным решениям для игровых задач<br /> * Альфа-бета отсечениям<br /> * Monte Carlo tree search для оценки позиций<br /> * Делать плагин для браузера, который общается с С++ программой<br /> <br /> === Какие начальные требования? ===<br /> Программирование на C/C++ (в рамках прослушанного курса)<br /> <br /> === Какие будут использоваться технологии? ===<br /> * gtest<br /> * javascript<br /> <br /> === Темы вводных занятий ===<br /> * Основы теории игр<br /> * Перебор с возвратом, альфа-бета отсечения<br /> * Monte Carlo tree search<br /> <br /> === Направления развития ===<br /> * Использование машинного обучения при оценке позиций<br /> * Более серьёзные хаки в джава-скрипте - предсказание последующих ходов сервера<br /> <br /> === Критерии оценки ===<br /> Должен получиться бот, который с неплохой вероятностью (скажем, 10%) получает в одном из квадратов:<br /> <br /> * 7 - 4096<br /> * 9 - 8192<br /> <br /> +1 балл за попытку использования машинного обучения или за достижение &gt;= 16342 любым способом</div>

Gusakov https://wiki.cs.hse.ru/index.php?title=2048_(%D0%BF%D1%80%D0%BE%D0%B5%D0%BA%D1%82)&diff=16661 2015-05-30T18:50:51Z

<p>Gusakov: /* Критерии оценки */</p> <hr /> <div>{{Карточка_проекта<br /> |name=2048<br /> |mentor=Алексей Гусаков<br /> |mentor_login={{URLENCODE:Gusakov|WIKI}}<br /> |semester=Весна 2015<br /> |course=1<br /> |summer=<br /> |categorize=yes<br /> }}<br /> <br /> === Что это за проект? ===<br /> 2048 - игра, известная многим офисным работникам. В неё можно играть онлайн, например, здесь http://go2048.com/<br /> <br /> Цель проекта - создать бота, который будет набирать больше, чем могут люди.<br /> <br /> === Чему вы научитесь? ===<br /> * Переборным решениям для игровых задач<br /> * Альфа-бета отсечениям<br /> * Monte Carlo tree search для оценки позиций<br /> * Делать плагин для браузера, который общается с С++ программой<br /> <br /> === Какие начальные требования? ===<br /> Программирование на C/C++ (в рамках прослушанного курса)<br /> <br /> === Какие будут использоваться технологии? ===<br /> * gtest<br /> * javascript<br /> <br /> === Темы вводных занятий ===<br /> * Основы теории игр<br /> * Перебор с возвратом, альфа-бета отсечения<br /> * Monte Carlo tree search<br /> <br /> === Направления развития ===<br /> * Использование машинного обучения при оценке позиций<br /> * Более серьёзные хаки в джава-скрипте - предсказание последующих ходов сервера<br /> <br /> === Критерии оценки ===<br /> Должен получиться бот, который с неплохой вероятностью (скажем, 10%) получает в одном из квадратов:<br /> <br /> * 5 - 4096<br /> * 7 - 8192<br /> * 9 - 16384<br /> <br /> +1 балл за попытку использования машинного обучения или за достижение 32768 любым способом</div>

Gusakov https://wiki.cs.hse.ru/index.php?title=%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B0_%D0%BA%D0%BE%D0%BC%D0%BC%D0%B8%D0%B2%D0%BE%D1%8F%D0%B6%D0%B5%D1%80%D0%B0_(%D0%BF%D1%80%D0%BE%D0%B5%D0%BA%D1%82)&diff=680 2014-12-01T12:31:28Z

<p>Gusakov: /* Критерии оценки */</p> <hr /> <div>{{Карточка_проекта<br /> |name=Задача коммивояжера<br /> |mentor=Алексей Гусаков<br /> |mentor_login={{URLENCODE:{{REVISIONUSER}}|WIKI}}<br /> |semester=Весна 2015<br /> |course=1<br /> |summer=<br /> |categorize=yes<br /> }}<br /> <br /> === Что это за проект? ===<br /> Задача коммивояжера заключается в отыскании самого выгодного маршрута, проходящего через заданные города с последующим возвратом в исходный город. Для этой простой задачи нет (и скорее всего не будет) решения, правильно работающего за полиномиальное время. Однако, существуют подходы, дающие неплохие практические результаты. Мы изучим два таких подхода: переборный и приближённый. В первом подходе изучим техники, позволяющие быстро находить правильное решение для 50-100 городов, во втором - быстро находить решение, которое доказуемо &quot;не сильно&quot; (в 1.5 раза) отличается от правильного. Результатом работы будет библиотека, реализующая один из двух подходов.<br /> <br /> === Чему вы научитесь? ===<br /> * Основам теории графов<br /> * Основам приближённых алгоритмов<br /> * Как использовать линейное программирование (и что это такое), чтобы оптимизировать перебор<br /> * Писать код без ошибок (ну почти что)<br /> * Визуализировать решение<br /> <br /> === Какие начальные требования? ===<br /> * Программирование на C/C++ (в рамках прослушанного курса)<br /> * Желание разбираться в алгоритмах<br /> <br /> === Какие будут использоваться технологии? ===<br /> * Визуализация на python<br /> * Библиотека Lemon для алгоритмов на графах<br /> * gtest<br /> <br /> === Темы вводных занятий ===<br /> * Основы теории графов (что это такое, базовые алгоритмы: минимальное остовное дерево, Эйлеровы циклы)<br /> * Приближённые алгоритмы, 2-оптимальное решение, паросочетания, 3/2-оптимальное решение<br /> * Алгоритмы: перебор с возвратом, метод ветвей и границ, эвристики 2-opt и 3-opt, линейное программирование<br /> <br /> === Направления развития ===<br /> Поскольку задача имеет некоторую практическую ценность, уже существует великое множество методов, помимо рассмотренных. Так например, для точного решения, помимо приведённых эвристик, могут быть полезны генетические алгоритмы, а для специального случая, когда расстояние между городами равно расстоянию на плоскости, существует полиномиальный алгоритм, находящий маршрут с любой наперёд заданной точностью.<br /> <br /> === Критерии оценки ===<br /> Как уже сказано, есть два пути решения задачи - точный и приближённый.<br /> <br /> Точный путь:<br /> * 4: Алгоритм работает на графе до 20 вершин<br /> * 6: Реализованы 2-opt и 3-opt, алгоритм работает для 50 вершин<br /> * 8: Метод ветвей и границ с линейным программированием<br /> <br /> +1 балл за визуализацию решения. Цель визуализации - чтобы на небольшом примере было понятно, как работает алгоритм.<br /> <br /> +1 балл за сравнение трёх методов на практике с методом локальных оптимизаций: насколько часто локальными оптимизациями не получается добиться точного решения?<br /> <br /> Приближённый путь:<br /> * 4: Алгоритм, который выдаёт какое-нибудь решение и оценку сверху на ошибку<br /> * 6: 2-приближение с помощью эйлерова цикла<br /> * 8: 3/2-приближение с использованием поиска паросочетания<br /> <br /> +1 балл за визуализацию решения. Цель визуализации - чтобы на небольшом примере было понятно, как работает алгоритм.<br /> <br /> +1 балл за сравнение трёх методов на практике с методом локальных оптимизаций: насколько часто локальными оптимизациями не удаётся получить лучшего решения, чем описанные?</div>

Gusakov https://wiki.cs.hse.ru/index.php?title=2048_(%D0%BF%D1%80%D0%BE%D0%B5%D0%BA%D1%82)&diff=679 2014-12-01T12:31:02Z

<p>Gusakov: </p> <hr /> <div>{{Карточка_проекта<br /> |name=2048<br /> |mentor=Алексей Гусаков<br /> |mentor_login={{URLENCODE:{{REVISIONUSER}}|WIKI}}<br /> |semester=Весна 2015<br /> |course=1<br /> |summer=<br /> |categorize=yes<br /> }}<br /> <br /> === Что это за проект? ===<br /> 2048 - игра, известная многим офисным работникам. В неё можно играть онлайн, например, здесь http://go2048.com/<br /> <br /> Цель проекта - создать бота, который будет набирать больше, чем могут люди.<br /> <br /> === Чему вы научитесь? ===<br /> * Переборным решениям для игровых задач<br /> * Альфа-бета отсечениям<br /> * Monte Carlo tree search для оценки позиций<br /> * Делать плагин для браузера, который общается с С++ программой<br /> <br /> === Какие начальные требования? ===<br /> Программирование на C/C++ (в рамках прослушанного курса)<br /> <br /> === Какие будут использоваться технологии? ===<br /> * gtest<br /> * javascript<br /> <br /> === Темы вводных занятий ===<br /> * Основы теории игр<br /> * Перебор с возвратом, альфа-бета отсечения<br /> * Monte Carlo tree search<br /> <br /> === Направления развития ===<br /> * Использование машинного обучения при оценке позиций<br /> * Более серьёзные хаки в джава-скрипте - предсказание последующих ходов сервера<br /> <br /> === Критерии оценки ===<br /> Должен получиться бот, который с неплохой вероятностью (скажем, 10%) получает в одном из квадратов:<br /> <br /> * 4 - 4096<br /> * 6 - 8192<br /> * 8 - 16384<br /> <br /> +1 балл, если вероятность успеха не 10%, а 50%<br /> <br /> +1 балл за попытку использования машинного обучения или за достижение 32768 любым способом</div>

Gusakov https://wiki.cs.hse.ru/index.php?title=2048_(%D0%BF%D1%80%D0%BE%D0%B5%D0%BA%D1%82)&diff=678 2014-12-01T12:30:46Z

<p>Gusakov: </p> <hr /> <div>{{Карточка_проекта<br /> |name=2048<br /> |mentor=Алексей Гусаков<br /> |mentor_login={{URLENCODE:{{REVISIONUSER}}|WIKI}}<br /> |semester=Весна 2015<br /> |course=1<br /> |summer=<br /> |categorize=yes<br /> }}<br /> <br /> === Что это за проект? ===<br /> 2048 - игра, известная многим офисным работникам. В неё можно играть онлайн, например, здесь http://go2048.com/<br /> <br /> Цель проекта - создать бота, который будет набирать больше, чем могут люди.<br /> <br /> === Чему вы научитесь? ===<br /> * Переборным решениям для игровых задач<br /> * Альфа-бета отсечениям<br /> * Monte Carlo tree search для оценки позиций<br /> * Делать плагин для браузера, который общается с С++ программой<br /> <br /> === Какие начальные требования? ===<br /> Программирование на C/C++ (в рамках прослушанного курса)<br /> <br /> === Какие будут использоваться технологии? ===<br /> * gtest<br /> * javascript<br /> <br /> === Темы вводных занятий ===<br /> * Основы теории игр<br /> * Перебор с возвратом, альфа-бета отсечения<br /> * Monte Carlo tree search<br /> <br /> === Направления развития ===<br /> * Использование машинного обучения при оценке позиций<br /> * Более серьёзные хаки в джава-скрипте - предсказание последующих ходов сервера<br /> <br /> === Критерии оценки ===<br /> Должен получиться бот, который с неплохой вероятностью (скажем, 10%) получает в одном из квадратов:<br /> <br /> * 4 - 4096<br /> * 6 - 8192<br /> * 8 - 16384<br /> <br /> +1 балл, если вероятность успеха не 10%, а 50%.<br /> +1 балл за попытку использования машинного обучения или за достижение 32768 любым способом</div>

Gusakov https://wiki.cs.hse.ru/index.php?title=%D0%A3%D1%87%D0%B0%D1%81%D1%82%D0%BD%D0%B8%D0%BA:Gusakov&diff=677 2014-12-01T12:25:31Z

<p>Gusakov: </p> <hr /> <div>[[Файл:Gusakov.png]]<br /> <br /> = Факты =<br /> * Выпускник мехмата МГУ 2010 года<br /> * 2 место на ACM ICPC World Finals 2010<br /> * Работаю в московском гугле<br /> <br /> = Интересы =<br /> * Машинное обучение: ранкинг, deep learning<br /> * Математика: комбинаторная оптимизация, приближённые алгоритмы<br /> * Спорт: борьба, штанга<br /> <br /> = Контакты =<br /> * agusakov@gmail.com<br /> * +7 906 758 92 49</div>

Gusakov https://wiki.cs.hse.ru/index.php?title=%D0%A3%D1%87%D0%B0%D1%81%D1%82%D0%BD%D0%B8%D0%BA:Gusakov&diff=676 2014-12-01T12:25:04Z

<p>Gusakov: </p> <hr /> <div>[[Файл:Gusakov.png]]<br /> <br /> = Факты =<br /> * Выпускник мехмата МГУ 2010 года<br /> * 2 место на ACM ICPC World Finals 2010<br /> * До настоящего дня работаю в московском гугле<br /> <br /> = Интересы =<br /> * Машинное обучение: ранкинг, deep learning<br /> * Математика: комбинаторная оптимизация, приближённые алгоритмы<br /> * Спорт: борьба, штанга<br /> <br /> = Контакты =<br /> * agusakov@gmail.com<br /> * +7 906 758 92 49</div>

Gusakov https://wiki.cs.hse.ru/index.php?title=%D0%A3%D1%87%D0%B0%D1%81%D1%82%D0%BD%D0%B8%D0%BA:Gusakov&diff=675 2014-12-01T12:24:43Z

<p>Gusakov: </p> <hr /> <div>[[Файл:Gusakov.png|500px|центр]]<br /> <br /> = Факты =<br /> * Выпускник мехмата МГУ 2010 года<br /> * 2 место на ACM ICPC World Finals 2010<br /> * До настоящего дня работаю в московском гугле<br /> <br /> = Интересы =<br /> * Машинное обучение: ранкинг, deep learning<br /> * Математика: комбинаторная оптимизация, приближённые алгоритмы<br /> * Спорт: борьба, штанга<br /> <br /> = Контакты =<br /> * agusakov@gmail.com<br /> * +7 906 758 92 49</div>

Gusakov https://wiki.cs.hse.ru/index.php?title=%D0%A3%D1%87%D0%B0%D1%81%D1%82%D0%BD%D0%B8%D0%BA:Gusakov&diff=674 2014-12-01T12:24:15Z

<p>Gusakov: </p> <hr /> <div>[[Файл:Gusakov.png]]<br /> <br /> = Факты =<br /> * Выпускник мехмата МГУ 2010 года<br /> * 2 место на ACM ICPC World Finals 2010<br /> * До настоящего дня работаю в московском гугле<br /> <br /> = Интересы =<br /> * Машинное обучение: ранкинг, deep learning<br /> * Математика: комбинаторная оптимизация, приближённые алгоритмы<br /> * Спорт: борьба, штанга<br /> <br /> = Контакты =<br /> * agusakov@gmail.com<br /> * +7 906 758 92 49</div>

Gusakov https://wiki.cs.hse.ru/index.php?title=%D0%A3%D1%87%D0%B0%D1%81%D1%82%D0%BD%D0%B8%D0%BA:Gusakov&diff=673 2014-12-01T12:23:32Z

<p>Gusakov: </p> <hr /> <div>[[Файл:Gusakov.jpg]]<br /> <br /> = Факты =<br /> * Выпускник мехмата МГУ 2010 года<br /> * 2 место на ACM ICPC World Finals 2010<br /> * До настоящего дня работаю в московском гугле<br /> <br /> = Интересы =<br /> * Машинное обучение: ранкинг, deep learning<br /> * Математика: комбинаторная оптимизация, приближённые алгоритмы<br /> * Спорт: борьба, штанга<br /> <br /> = Контакты =<br /> * agusakov@gmail.com<br /> * +7 906 758 92 49</div>

Gusakov https://wiki.cs.hse.ru/index.php?title=%D0%A3%D1%87%D0%B0%D1%81%D1%82%D0%BD%D0%B8%D0%BA:Gusakov&diff=672 2014-12-01T12:22:57Z

<p>Gusakov: </p> <hr /> <div>[[Файл:Gusakov.jpg|500px|центр]]<br /> <br /> = Факты =<br /> * Выпускник мехмата МГУ 2010 года<br /> * 2 место на ACM ICPC World Finals 2010<br /> * До настоящего дня работаю в московском гугле<br /> <br /> = Интересы =<br /> * Машинное обучение: ранкинг, deep learning<br /> * Математика: комбинаторная оптимизация, приближённые алгоритмы<br /> * Спорт: борьба, штанга<br /> <br /> = Контакты =<br /> * agusakov@gmail.com<br /> * +7 906 758 92 49</div>

Gusakov https://wiki.cs.hse.ru/index.php?title=%D0%A3%D1%87%D0%B0%D1%81%D1%82%D0%BD%D0%B8%D0%BA:Gusakov&diff=671 2014-12-01T12:21:09Z

<p>Gusakov: </p> <hr /> <div>[[Файл:gusakov.jpg|500px|центр]]<br /> <br /> = Факты =<br /> * Выпускник мехмата МГУ 2010 года<br /> * 2 место на ACM ICPC World Finals 2010<br /> * До настоящего дня работаю в московском гугле<br /> <br /> = Интересы =<br /> * Машинное обучение: ранкинг, deep learning<br /> * Математика: комбинаторная оптимизация, приближённые алгоритмы<br /> * Спорт: борьба, штанга<br /> <br /> = Контакты =<br /> * agusakov@gmail.com<br /> * +7 906 758 92 49</div>

Gusakov https://wiki.cs.hse.ru/index.php?title=%D0%A3%D1%87%D0%B0%D1%81%D1%82%D0%BD%D0%B8%D0%BA:Gusakov&diff=670 2014-12-01T12:20:33Z

<p>Gusakov: </p> <hr /> <div>[[Файл:Gusakov.jpg|500px|центр]]<br /> <br /> = Факты =<br /> * Выпускник мехмата МГУ 2010 года<br /> * 2 место на ACM ICPC World Finals 2010<br /> * До настоящего дня работаю в московском гугле<br /> <br /> = Интересы =<br /> * Машинное обучение: ранкинг, deep learning<br /> * Математика: комбинаторная оптимизация, приближённые алгоритмы<br /> * Спорт: борьба, штанга<br /> <br /> = Контакты =<br /> * agusakov@gmail.com<br /> * +7 906 758 92 49</div>

Gusakov https://wiki.cs.hse.ru/index.php?title=%D0%A4%D0%B0%D0%B9%D0%BB:Gusakov.png&diff=669 2014-12-01T12:19:39Z

<p>Gusakov: </p> <hr /> <div></div>

Gusakov https://wiki.cs.hse.ru/index.php?title=%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B0_%D0%BA%D0%BE%D0%BC%D0%BC%D0%B8%D0%B2%D0%BE%D1%8F%D0%B6%D0%B5%D1%80%D0%B0_(%D0%BF%D1%80%D0%BE%D0%B5%D0%BA%D1%82)&diff=668 2014-12-01T12:16:16Z

<p>Gusakov: </p> <hr /> <div>{{Карточка_проекта<br /> |name=Задача коммивояжера<br /> |mentor=Алексей Гусаков<br /> |mentor_login={{URLENCODE:{{REVISIONUSER}}|WIKI}}<br /> |semester=Весна 2015<br /> |course=1<br /> |summer=<br /> |categorize=yes<br /> }}<br /> <br /> === Что это за проект? ===<br /> Задача коммивояжера заключается в отыскании самого выгодного маршрута, проходящего через заданные города с последующим возвратом в исходный город. Для этой простой задачи нет (и скорее всего не будет) решения, правильно работающего за полиномиальное время. Однако, существуют подходы, дающие неплохие практические результаты. Мы изучим два таких подхода: переборный и приближённый. В первом подходе изучим техники, позволяющие быстро находить правильное решение для 50-100 городов, во втором - быстро находить решение, которое доказуемо &quot;не сильно&quot; (в 1.5 раза) отличается от правильного. Результатом работы будет библиотека, реализующая один из двух подходов.<br /> <br /> === Чему вы научитесь? ===<br /> * Основам теории графов<br /> * Основам приближённых алгоритмов<br /> * Как использовать линейное программирование (и что это такое), чтобы оптимизировать перебор<br /> * Писать код без ошибок (ну почти что)<br /> * Визуализировать решение<br /> <br /> === Какие начальные требования? ===<br /> * Программирование на C/C++ (в рамках прослушанного курса)<br /> * Желание разбираться в алгоритмах<br /> <br /> === Какие будут использоваться технологии? ===<br /> * Визуализация на python<br /> * Библиотека Lemon для алгоритмов на графах<br /> * gtest<br /> <br /> === Темы вводных занятий ===<br /> * Основы теории графов (что это такое, базовые алгоритмы: минимальное остовное дерево, Эйлеровы циклы)<br /> * Приближённые алгоритмы, 2-оптимальное решение, паросочетания, 3/2-оптимальное решение<br /> * Алгоритмы: перебор с возвратом, метод ветвей и границ, эвристики 2-opt и 3-opt, линейное программирование<br /> <br /> === Направления развития ===<br /> Поскольку задача имеет некоторую практическую ценность, уже существует великое множество методов, помимо рассмотренных. Так например, для точного решения, помимо приведённых эвристик, могут быть полезны генетические алгоритмы, а для специального случая, когда расстояние между городами равно расстоянию на плоскости, существует полиномиальный алгоритм, находящий маршрут с любой наперёд заданной точностью.<br /> <br /> === Критерии оценки ===<br /> Как уже сказано, есть два пути решения задачи - точный и приближённый.<br /> <br /> Точный путь:<br /> * 4: Алгоритм работает на графе до 20 вершин<br /> * 6: Реализованы 2-opt и 3-opt, алгоритм работает для 50 вершин<br /> * 8: Метод ветвей и границ с линейным программированием<br /> <br /> +1 балл за визуализацию решения. Цель визуализации - чтобы на небольшом примере было понятно, как работает алгоритм.<br /> +1 балл за сравнение трёх методов на практике с методом локальных оптимизаций: насколько часто локальными оптимизациями не получается добиться точного решения?<br /> <br /> Приближённый путь:<br /> * 4: Алгоритм, который выдаёт какое-нибудь решение и оценку сверху на ошибку<br /> * 6: 2-приближение с помощью эйлерова цикла<br /> * 8: 3/2-приближение с использованием поиска паросочетания<br /> <br /> +1 балл за визуализацию решения. Цель визуализации - чтобы на небольшом примере было понятно, как работает алгоритм.<br /> +1 балл за сравнение трёх методов на практике с методом локальных оптимизаций: насколько часто локальными оптимизациями не удаётся получить лучшего решения, чем описанные?</div>

Gusakov https://wiki.cs.hse.ru/index.php?title=%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B0_%D0%BA%D0%BE%D0%BC%D0%BC%D0%B8%D0%B2%D0%BE%D1%8F%D0%B6%D0%B5%D1%80%D0%B0_(%D0%BF%D1%80%D0%BE%D0%B5%D0%BA%D1%82)&diff=667 2014-12-01T12:15:52Z

<p>Gusakov: </p> <hr /> <div>{{Карточка_проекта<br /> |name=Задача коммивояжера<br /> |mentor=Алексей Гусаков<br /> |mentor_login={{URLENCODE:{{REVISIONUSER}}|WIKI}}<br /> |semester=Весна 2015<br /> |course=1<br /> |summer=<br /> |categorize=yes<br /> }}<br /> <br /> === Что это за проект? ===<br /> Задача коммивояжера заключается в отыскании самого выгодного маршрута, проходящего через заданные города с последующим возвратом в исходный город. Для этой простой задачи нет (и скорее всего не будет) решения, правильно работающего за полиномиальное время. Однако, существуют подходы, дающие неплохие практические результаты. Мы изучим два таких подхода: переборный и приближённый. В первом подходе изучим техники, позволяющие быстро находить правильное решение для 50-100 городов, во втором - быстро находить решение, которое доказуемо &quot;не сильно&quot; (в 1.5 раза) отличается от правильного. Результатом работы будет библиотека, реализующая один из двух подходов.<br /> <br /> === Чему вы научитесь? ===<br /> * Основам теории графов<br /> * Основам приближённых алгоритмов<br /> * Как использовать линейное программирование (и что это такое), чтобы оптимизировать перебор<br /> * Писать код без ошибок (ну почти что)<br /> * Визуализировать решение<br /> <br /> === Какие начальные требования? ===<br /> * Программирование на C/C++ (в рамках прослушанного курса)<br /> * Желание разбираться в алгоритмах<br /> <br /> === Какие будут использоваться технологии? ===<br /> * Визуализация на python<br /> * Библиотека Lemon<br /> * gtest<br /> <br /> === Темы вводных занятий ===<br /> * Основы теории графов (что это такое, базовые алгоритмы: минимальное остовное дерево, Эйлеровы циклы)<br /> * Приближённые алгоритмы, 2-оптимальное решение, паросочетания, 3/2-оптимальное решение<br /> * Алгоритмы: перебор с возвратом, метод ветвей и границ, эвристики 2-opt и 3-opt, линейное программирование<br /> <br /> === Направления развития ===<br /> Поскольку задача имеет некоторую практическую ценность, уже существует великое множество методов, помимо рассмотренных. Так например, для точного решения, помимо приведённых эвристик, могут быть полезны генетические алгоритмы, а для специального случая, когда расстояние между городами равно расстоянию на плоскости, существует полиномиальный алгоритм, находящий маршрут с любой наперёд заданной точностью.<br /> <br /> === Критерии оценки ===<br /> Как уже сказано, есть два пути решения задачи - точный и приближённый.<br /> <br /> Точный путь:<br /> * 4: Алгоритм работает на графе до 20 вершин<br /> * 6: Реализованы 2-opt и 3-opt, алгоритм работает для 50 вершин<br /> * 8: Метод ветвей и границ с линейным программированием<br /> <br /> +1 балл за визуализацию решения. Цель визуализации - чтобы на небольшом примере было понятно, как работает алгоритм.<br /> +1 балл за сравнение трёх методов на практике с методом локальных оптимизаций: насколько часто локальными оптимизациями не получается добиться точного решения?<br /> <br /> Приближённый путь:<br /> * 4: Алгоритм, который выдаёт какое-нибудь решение и оценку сверху на ошибку<br /> * 6: 2-приближение с помощью эйлерова цикла<br /> * 8: 3/2-приближение с использованием поиска паросочетания<br /> <br /> +1 балл за визуализацию решения. Цель визуализации - чтобы на небольшом примере было понятно, как работает алгоритм.<br /> +1 балл за сравнение трёх методов на практике с методом локальных оптимизаций: насколько часто локальными оптимизациями не удаётся получить лучшего решения, чем описанные?</div>

Gusakov https://wiki.cs.hse.ru/index.php?title=%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B0_%D0%BA%D0%BE%D0%BC%D0%BC%D0%B8%D0%B2%D0%BE%D1%8F%D0%B6%D0%B5%D1%80%D0%B0_(%D0%BF%D1%80%D0%BE%D0%B5%D0%BA%D1%82)&diff=666 2014-12-01T12:11:49Z

<p>Gusakov: </p> <hr /> <div>{{Карточка_проекта<br /> |name=Задача коммивояжера<br /> |mentor=Алексей Гусаков<br /> |mentor_login={{URLENCODE:{{REVISIONUSER}}|WIKI}}<br /> |semester=Весна 2015<br /> |course=1<br /> |summer=<br /> |categorize=yes<br /> }}<br /> <br /> === Что это за проект? ===<br /> Задача коммивояжера заключается в отыскании самого выгодного маршрута, проходящего через заданные города с последующим возвратом в исходный город. Для этой простой задачи нет (и скорее всего не будет) решения, правильно работающего за полиномиальное время. Однако, существуют подходы, дающие неплохие практические результаты. Мы изучим два таких подхода: переборный и приближённый. В первом подходе изучим техники, позволяющие быстро находить правильное решение для 50-100 городов, во втором - быстро находить решение, которое доказуемо &quot;не сильно&quot; (в 1.5 раза) отличается от правильного. Результатом работы будет библиотека, реализующая один из двух подходов.<br /> <br /> === Чему вы научитесь? ===<br /> * Основам теории графов<br /> * Основам приближённых алгоритмов<br /> * Как использовать линейное программирование (и что это такое), чтобы оптимизировать перебор<br /> * Писать код без ошибок (ну почти что)<br /> * Визуализировать решение<br /> <br /> === Какие начальные требования? ===<br /> * Программирование на C/C++ (в рамках прослушанного курса)<br /> * Желание разбираться в алгоритмах<br /> <br /> === Какие будут использоваться технологии? ===<br /> * Визуализация на python<br /> * Библиотека Lemon<br /> * gtest<br /> <br /> === Темы вводных занятий ===<br /> * Основы теории графов (что это такое, базовые алгоритмы: минимальное остовное дерево, Эйлеровы циклы)<br /> * Приближённые алгоритмы, 2-оптимальное решение, паросочетания, 3/2-оптимальное решение<br /> * Алгоритмы: перебор с возвратом, метод ветвей и границ, эвристики 2-opt и 3-opt, линейное программирование<br /> <br /> === Направления развития ===<br /> Поскольку задача имеет некоторую практическую ценность, уже существует великое множество методов, помимо рассмотренных. Так например, для точного решения, помимо приведённых эвристик, могут быть полезны генетические алгоритмы, а для специального случая, когда расстояние между городами равно расстоянию на плоскости, существует полиномиальный алгоритм, находящий маршрут с любой наперёд заданной точностью.<br /> <br /> === Критерии оценки ===<br /> Как уже сказано, есть два пути решения задачи - точный и приближённый.<br /> <br /> Точный путь:<br /> * 4: Алгоритм работает на графе до 20 вершин<br /> * 6: Реализованы 2-opt и 3-opt, алгоритм работает для 50 вершин<br /> * 8: Метод ветвей и границ с линейным программированием<br /> <br /> +1 балл за визуализацию решения. Цель визуализации - чтобы на небольшом примере было понятно, как работает алгоритм.<br /> <br /> Приближённый путь:<br /> * 4: Алгоритм, который выдаёт какое-нибудь решение и оценку сверху на ошибку<br /> * 6: 2-приближение с помощью эйлерова цикла<br /> * 8: 3/2-приближение с использованием поиска паросочетания<br /> <br /> +1 балл за визуализацию решения. Цель визуализации - чтобы на небольшом примере было понятно, как работает алгоритм.</div>

Gusakov https://wiki.cs.hse.ru/index.php?title=%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B0_%D0%BA%D0%BE%D0%BC%D0%BC%D0%B8%D0%B2%D0%BE%D1%8F%D0%B6%D0%B5%D1%80%D0%B0_(%D0%BF%D1%80%D0%BE%D0%B5%D0%BA%D1%82)&diff=665 2014-12-01T12:11:05Z

<p>Gusakov: </p> <hr /> <div>{{Карточка_проекта<br /> |name=Задача коммивояжера<br /> |mentor=Алексей Гусаков<br /> |mentor_login={{URLENCODE:{{REVISIONUSER}}|WIKI}}<br /> |semester=Весна 2015<br /> |course=1<br /> |summer=<br /> |categorize=yes<br /> }}<br /> <br /> === Что это за проект? ===<br /> Задача коммивояжера заключается в отыскании самого выгодного маршрута, проходящего через заданные города с последующим возвратом в исходный город. Для этой простой задачи нет (и скорее всего не будет) решения, правильно работающего за полиномиальное время. Однако, существуют подходы, дающие неплохие практические результаты. Мы изучим два таких подхода: переборный и приближённый. В первом подходе изучим техники, позволяющие быстро находить правильное решение для 50-100 городов, во втором - быстро находить решение, которое доказуемо &quot;не сильно&quot; (в 1.5 раза) отличается от правильного. Результатом работы будет библиотека, реализующая один из двух подходов.<br /> <br /> === Чему вы научитесь? ===<br /> * Основам теории графов<br /> * Основам приближённых алгоритмов<br /> * Как использовать линейное программирование (и что это такое), чтобы оптимизировать перебор<br /> * Писать код без ошибок (ну почти что)<br /> * Визуализировать решение<br /> <br /> === Какие начальные требования? ===<br /> * Программирование на C/C++ (в рамках прослушанного курса)<br /> * Желание разбираться в алгоритмах<br /> <br /> === Какие будут использоваться технологии? ===<br /> * gtest<br /> * Визуализация на python<br /> <br /> === Темы вводных занятий ===<br /> * Основы теории графов (что это такое, базовые алгоритмы: минимальное остовное дерево, Эйлеровы циклы)<br /> * Приближённые алгоритмы, 2-оптимальное решение, паросочетания, 3/2-оптимальное решение<br /> * Алгоритмы: перебор с возвратом, метод ветвей и границ, эвристики 2-opt и 3-opt, линейное программирование<br /> <br /> === Направления развития ===<br /> Поскольку задача имеет некоторую практическую ценность, уже существует великое множество методов, помимо рассмотренных. Так например, для точного решения, помимо приведённых эвристик, могут быть полезны генетические алгоритмы, а для специального случая, когда расстояние между городами равно расстоянию на плоскости, существует полиномиальный алгоритм, находящий маршрут с любой наперёд заданной точностью.<br /> <br /> === Критерии оценки ===<br /> Как уже сказано, есть два пути решения задачи - точный и приближённый.<br /> <br /> Точный путь:<br /> * 4: Алгоритм работает на графе до 20 вершин<br /> * 6: Реализованы 2-opt и 3-opt, алгоритм работает для 50 вершин<br /> * 8: Метод ветвей и границ с линейным программированием<br /> <br /> +1 балл за визуализацию решения. Цель визуализации - чтобы на небольшом примере было понятно, как работает алгоритм.<br /> <br /> Приближённый путь:<br /> * 4: Алгоритм, который выдаёт какое-нибудь решение и оценку сверху на ошибку<br /> * 6: 2-приближение с помощью эйлерова цикла<br /> * 8: 3/2-приближение с использованием поиска паросочетания<br /> <br /> +1 балл за визуализацию решения. Цель визуализации - чтобы на небольшом примере было понятно, как работает алгоритм.</div>

Gusakov https://wiki.cs.hse.ru/index.php?title=%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B0_%D0%BA%D0%BE%D0%BC%D0%BC%D0%B8%D0%B2%D0%BE%D1%8F%D0%B6%D0%B5%D1%80%D0%B0_(%D0%BF%D1%80%D0%BE%D0%B5%D0%BA%D1%82)&diff=664 2014-12-01T12:08:36Z

<p>Gusakov: </p> <hr /> <div>{{Карточка_проекта<br /> |name=Задача коммивояжера<br /> |mentor=Алексей Гусаков<br /> |mentor_login={{URLENCODE:{{REVISIONUSER}}|WIKI}}<br /> |semester=Весна 2015<br /> |course=1<br /> |summer=<br /> |categorize=yes<br /> }}<br /> <br /> === Что это за проект? ===<br /> Задача коммивояжера заключается в отыскании самого выгодного маршрута, проходящего через заданные города с последующим возвратом в исходный город. Для этой простой задачи нет (и скорее всего не будет) решения, правильно работающего за полиномиальное время. Однако, существуют подходы, дающие неплохие практические результаты. Мы изучим два таких подхода: переборный и приближённый. В первом подходе изучим техники, позволяющие быстро находить правильное решение для 50-100 городов, во втором - быстро находить решение, которое доказуемо &quot;не сильно&quot; (в 1.5 раза) отличается от правильного. Результатом работы будет библиотека, реализующая один из двух подходов.<br /> <br /> === Чему вы научитесь? ===<br /> * Основам теории графов<br /> * Основам приближённых алгоритмов<br /> * Как использовать линейное программирование (и что это такое), чтобы оптимизировать перебор<br /> * Писать код без ошибок (ну почти что)<br /> * Визуализировать решение<br /> <br /> === Какие начальные требования? ===<br /> * Программирование на C/C++ (в рамках прослушанного курса)<br /> * Желание разбираться в алгоритмах<br /> <br /> === Какие будут использоваться технологии? ===<br /> * gtest<br /> * Визуализация на python<br /> <br /> === Темы вводных занятий ===<br /> * Основы теории графов (что это такое, базовые алгоритмы: минимальное остовное дерево, Эйлеровы циклы)<br /> * Приближённые алгоритмы, 2-оптимальное решение, паросочетания, 3/2-оптимальное решение<br /> * Алгоритмы: перебор с возвратом, метод ветвей и границ, эвристики 2-opt и 3-opt, линейное программирование<br /> <br /> === Направления развития ===<br /> Поскольку задача имеет некоторую практическую ценность, уже существует великое множество методов, помимо рассмотренных. Так например, для точного решения, помимо приведённых эвристик, могут быть полезны генетические алгоритмы, а для специального случая, когда расстояние между городами равно расстоянию на плоскости, существует полиномиальный алгоритм, находящий маршрут с любой наперёд заданной точностью.<br /> <br /> === Критерии оценки ===<br /> Как уже сказано, есть два пути решения задачи - точный и приближённый.<br /> <br /> Точный путь:<br /> * 4: Алгоритм работает на графе до 20 вершин<br /> * 6: Реализованы 2-opt и 3-opt, алгоритм работает для 50 вершин<br /> * 8: Метод ветвей и границ с линейным программированием<br /> <br /> Приближённый путь:<br /> * 4: Алгоритм, который выдаёт какое-нибудь решение и оценку сверху на ошибку<br /> * 6: 2-приближение с помощью эйлерова цикла<br /> * 8: 3/2-приближение с использованием поиска паросочетания<br /> <br /> +1 балл за визуализацию решения. Цель визуализации - чтобы на небольшом примере было понятно, как работает алгоритм.</div>

Gusakov https://wiki.cs.hse.ru/index.php?title=%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B0_%D0%BA%D0%BE%D0%BC%D0%BC%D0%B8%D0%B2%D0%BE%D1%8F%D0%B6%D0%B5%D1%80%D0%B0_(%D0%BF%D1%80%D0%BE%D0%B5%D0%BA%D1%82)&diff=663 2014-12-01T12:06:30Z

<p>Gusakov: </p> <hr /> <div>{{Карточка_проекта<br /> |name=Задача коммивояжера<br /> |mentor=Алексей Гусаков<br /> |mentor_login={{URLENCODE:{{REVISIONUSER}}|WIKI}}<br /> |semester=Весна 2015<br /> |course=1<br /> |summer=<br /> |categorize=yes<br /> }}<br /> <br /> === Что это за проект? ===<br /> Задача коммивояжера заключается в отыскании самого выгодного маршрута, проходящего через заданные города с последующим возвратом в исходный город. Для этой простой задачи нет (и скорее всего не будет) решения, правильно работающего за полиномиальное время. Однако, существуют подходы, дающие неплохие практические результаты. Мы изучим два таких подхода: переборный и приближённый. В первом подходе изучим техники, позволяющие быстро находить правильное решение для 50-100 городов, во втором - быстро находить решение, которое доказуемо &quot;не сильно&quot; (в 1.5 раза) отличается от правильного. Результатом работы будет библиотека, реализующая один из двух подходов.<br /> <br /> === Чему вы научитесь? ===<br /> * Основам теории графов<br /> * Основам приближённых алгоритмов<br /> * Как использовать линейное программирование (и что это такое), чтобы оптимизировать перебор<br /> * Писать код без ошибок (ну почти что)<br /> * Визуализировать решение<br /> <br /> === Какие начальные требования? ===<br /> * Программирование на C/C++ (в рамках прослушанного курса)<br /> * Желание разбираться в алгоритмах<br /> <br /> === Какие будут использоваться технологии? ===<br /> * gtest<br /> * Визуализация на python<br /> <br /> === Темы вводных занятий ===<br /> * Основы теории графов (что это такое, базовые алгоритмы: минимальное остовное дерево, Эйлеровы циклы)<br /> * Приближённые алгоритмы, 2-оптимальное решение, паросочетания, 3/2-оптимальное решение<br /> * Алгоритмы: перебор с возвратом, метод ветвей и границ, эвристики 2-opt и 3-opt, линейное программирование<br /> <br /> === Направления развития ===<br /> Поскольку задача имеет некоторую практическую ценность, уже существует великое множество методов, помимо рассмотренных. Так например, для точного решения, помимо приведённых эвристик, могут быть полезны генетические алгоритмы, а для специального случая, когда расстояние между городами равно расстоянию на плоскости, существует полиномиальный алгоритм, находящий маршрут с любой наперёд заданной точностью.<br /> <br /> === Критерии оценки ===<br /> Как уже сказано, есть два пути решения задачи - точный и приближённый.<br /> <br /> Точный путь:<br /> * удв: Алгоритм работает на графе до 20 вершин, с помощью визуализатора можно понять, как всё работает<br /> * хор: Реализованы 2-opt и 3-opt, алгоритм работает для 50 вершин<br /> * отл: Метод ветвей и границ с линейным программированием<br /> <br /> Приближённый путь:<br /> * удв: Алгоритм, который выдаёт какое-нибудь решение и оценку сверху на ошибку + визуализация<br /> * хор: 2-приближение с помощью эйлерова цикла<br /> * отл: 3/2-приближение с использованием поиска паросочетания</div>

Gusakov https://wiki.cs.hse.ru/index.php?title=%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B0_%D0%BA%D0%BE%D0%BC%D0%BC%D0%B8%D0%B2%D0%BE%D1%8F%D0%B6%D0%B5%D1%80%D0%B0_(%D0%BF%D1%80%D0%BE%D0%B5%D0%BA%D1%82)&diff=662 2014-12-01T12:05:07Z

<p>Gusakov: </p> <hr /> <div>{{Карточка_проекта<br /> |name=Задача коммивояжера<br /> |mentor=Алексей Гусаков<br /> |mentor_login={{URLENCODE:{{REVISIONUSER}}|WIKI}}<br /> |semester=Весна 2015<br /> |course=1<br /> |summer=<br /> |categorize=yes<br /> }}<br /> <br /> === Что это за проект? ===<br /> Задача коммивояжера заключается в отыскании самого выгодного маршрута, проходящего через заданные города с последующим возвратом в исходный город. Для этой простой задачи нет (и скорее всего не будет) решения, правильно работающего за полиномиальное время. Однако, существуют подходы, дающие неплохие практические результаты. Мы изучим два таких подхода: переборный и приближённый. В первом подходе изучим техники, позволяющие быстро находить правильное решение для 50-100 городов, во втором - быстро находить решение, которое доказуемо &quot;не сильно&quot; (в 1.5 раза) отличается от правильного. Результатом работы будет библиотека, реализующая один из двух подходов.<br /> <br /> === Чему вы научитесь? ===<br /> * Основам теории графов<br /> * Основам приближённых алгоритмов<br /> * Как использовать линейное программирование (и что это такое), чтобы оптимизировать перебор<br /> * Писать код без ошибок (ну почти что)<br /> * Визуализировать решение<br /> <br /> === Какие начальные требования? ===<br /> * Программирование на C/C++ (в рамках прослушанного курса)<br /> * Желание разбираться в алгоритмах<br /> <br /> === Какие будут использоваться технологии? ===<br /> * git, github<br /> * gtest<br /> <br /> === Темы вводных занятий ===<br /> * Основы теории графов (что это такое, базовые алгоритмы: минимальное остовное дерево, Эйлеровы циклы)<br /> * Приближённые алгоритмы, 2-оптимальное решение, паросочетания, 3/2-оптимальное решение<br /> * Алгоритмы: перебор с возвратом, метод ветвей и границ, эвристики 2-opt и 3-opt, линейное программирование<br /> <br /> === Направления развития ===<br /> Поскольку задача имеет некоторую практическую ценность, уже существует великое множество методов, помимо рассмотренных. Так например, для точного решения, помимо приведённых эвристик, могут быть полезны генетические алгоритмы, а для специального случая, когда расстояние между городами равно расстоянию на плоскости, существует полиномиальный алгоритм, находящий маршрут с любой наперёд заданной точностью.<br /> <br /> === Критерии оценки ===<br /> Как уже сказано, есть два пути решения задачи - точный и приближённый.<br /> <br /> Точный путь:<br /> * удв: Алгоритм работает на графе до 20 вершин, с помощью визуализатора можно понять, как всё работает<br /> * хор: Реализованы 2-opt и 3-opt, алгоритм работает для 50 вершин<br /> * отл: Метод ветвей и границ с линейным программированием<br /> <br /> Приближённый путь:<br /> * удв: Алгоритм, который выдаёт какое-нибудь решение и оценку сверху на ошибку + визуализация<br /> * хор: 2-приближение с помощью эйлерова цикла<br /> * отл: 3/2-приближение с использованием поиска паросочетания</div>

Gusakov https://wiki.cs.hse.ru/index.php?title=2048_(%D0%BF%D1%80%D0%BE%D0%B5%D0%BA%D1%82)&diff=661 2014-12-01T11:59:15Z

<p>Gusakov: </p> <hr /> <div>{{Карточка_проекта<br /> |name=2048<br /> |mentor=Алексей Гусаков<br /> |mentor_login={{URLENCODE:{{REVISIONUSER}}|WIKI}}<br /> |semester=Весна 2015<br /> |course=1<br /> |summer=<br /> |categorize=yes<br /> }}<br /> <br /> === Что это за проект? ===<br /> 2048 - игра, известная многим офисным работникам. В неё можно играть онлайн, например, здесь http://go2048.com/<br /> <br /> Цель проекта - создать бота, который будет набирать больше, чем могут люди.<br /> <br /> === Чему вы научитесь? ===<br /> * Переборным решениям для игровых задач<br /> * Альфа-бета отсечениям<br /> * Monte Carlo tree search для оценки позиций<br /> * Делать плагин для браузера, который общается с С++ программой<br /> <br /> === Какие начальные требования? ===<br /> Программирование на C/C++ (в рамках прослушанного курса)<br /> <br /> === Какие будут использоваться технологии? ===<br /> * gtest<br /> * javascript<br /> <br /> === Темы вводных занятий ===<br /> * Основы теории игр<br /> * Перебор с возвратом, альфа-бета отсечения<br /> * Monte Carlo tree search<br /> <br /> === Направления развития ===<br /> * Использование машинного обучения при оценке позиций<br /> * Более серьёзные хаки в джава-скрипте - предсказание последующих ходов сервера<br /> <br /> === Критерии оценки ===<br /> Должен получиться бот, который с неплохой вероятностью получает в одном из квадратов:<br /> <br /> * 4-5 - 4096<br /> * 6-7 - 8192<br /> * 8-10 - 16384</div>

Gusakov https://wiki.cs.hse.ru/index.php?title=2048_(%D0%BF%D1%80%D0%BE%D0%B5%D0%BA%D1%82)&diff=660 2014-12-01T11:53:56Z

<p>Gusakov: </p> <hr /> <div>{{Карточка_проекта<br /> |name=2048<br /> |mentor=Алексей Гусаков<br /> |mentor_login={{URLENCODE:{{REVISIONUSER}}|WIKI}}<br /> |semester=Весна 2015<br /> |course=1<br /> |summer=<br /> |categorize=yes<br /> }}<br /> <br /> === Что это за проект? ===<br /> 2048 - игра, известная многим офисным работникам. В неё можно играть онлайн, например, здесь http://go2048.com/<br /> <br /> Цель проекта - создать бота, который будет набирать больше, чем могут люди.<br /> <br /> === Чему вы научитесь? ===<br /> * Переборным решениям для игровых задач<br /> * Альфа-бета отсечениям<br /> * Monte Carlo tree search для оценки позиций<br /> * Делать плагин для браузера, который общается с С++ программой<br /> <br /> === Какие начальные требования? ===<br /> Программирование на C/C++ (в рамках прослушанного курса)<br /> <br /> === Какие будут использоваться технологии? ===<br /> * gtest<br /> * javascript<br /> <br /> === Темы вводных занятий ===<br /> * Основы теории игр<br /> * Перебор с возвратом, альфа-бета отсечения<br /> * Monte Carlo tree search<br /> <br /> === Направления развития ===<br /> * Использование машинного обучения при оценке позиций<br /> * Более серьёзные хаки в джава-скрипте - предсказание последующих ходов сервера<br /> <br /> === Критерии оценки ===<br /> Должен получиться бот, который с неплохой вероятностью получает в одном из квадратов:<br /> <br /> * удв - 4096<br /> * хор - 8192<br /> * отл - 16384</div>

Gusakov https://wiki.cs.hse.ru/index.php?title=2048_(%D0%BF%D1%80%D0%BE%D0%B5%D0%BA%D1%82)&diff=659 2014-12-01T11:51:19Z

<p>Gusakov: </p> <hr /> <div>{{Карточка_проекта<br /> |name=2048<br /> |mentor=Алексей Гусаков<br /> |mentor_login={{URLENCODE:{{REVISIONUSER}}|WIKI}}<br /> |semester=Весна 2015<br /> |course=1<br /> |summer=<br /> |categorize=yes<br /> }}<br /> <br /> === Что это за проект? ===<br /> 2048 - игра, известная многим офисным работникам. В неё можно играть онлайн, например, здесь http://go2048.com/<br /> <br /> Цель проекта - создать бота, который будет набирать больше, чем могут люди.<br /> <br /> === Чему вы научитесь? ===<br /> * Переборным решениям для игровых задач<br /> * Альфа-бета отсечениям<br /> * Monte Carlo tree search для оценки позиций<br /> * Делать плагин для браузера, который общается с С++ программой<br /> <br /> === Какие начальные требования? ===<br /> Программирование на C/C++ (в рамках прослушанного курса)<br /> <br /> === Какие будут использоваться технологии? ===<br /> * git, github<br /> * gtest<br /> <br /> === Темы вводных занятий ===<br /> * Основы теории игр<br /> * Перебор с возвратом, альфа-бета отсечения<br /> * Monte Carlo tree search<br /> <br /> === Направления развития ===<br /> * Использование машинного обучения при оценке позиций<br /> * Более серьёзные хаки в джава-скрипте - предсказание последующих ходов сервера<br /> <br /> === Критерии оценки ===<br /> Должен получиться бот, который с неплохой вероятностью получает в одном из квадратов:<br /> <br /> * удв - 4096<br /> * хор - 8192<br /> * отл - 16384</div>

Gusakov https://wiki.cs.hse.ru/index.php?title=2048_(%D0%BF%D1%80%D0%BE%D0%B5%D0%BA%D1%82)&diff=417 2014-11-19T11:31:20Z

<p>Gusakov: /* Направления развития */</p> <hr /> <div>{{Карточка_проекта<br /> |name=2048<br /> |mentor=Алексей Гусаков<br /> |mentor_login={{URLENCODE:{{REVISIONUSER}}|WIKI}}<br /> |semester=Весна 2015<br /> |course=1<br /> |summer=<br /> |categorize=yes<br /> }}<br /> <br /> === Что это за проект? ===<br /> 2048 - игра, известная многим офисным работникам. В неё можно играть онлайн, например, здесь http://go2048.com/<br /> <br /> Цель проекта - создать бота, который будет набирать больше, чем могут люди.<br /> <br /> === Чему вы научитесь? ===<br /> * Переборным решениям для игровых задач<br /> * Альфа-бета отсечениям<br /> * Monte Carlo tree search для оценки позиций<br /> * Хакать javascript<br /> <br /> === Какие начальные требования? ===<br /> Программирование на C/C++ (в рамках прослушанного курса)<br /> <br /> === Какие будут использоваться технологии? ===<br /> * git, github<br /> * gtest<br /> <br /> === Темы вводных занятий ===<br /> * Основы теории игр<br /> * Перебор с возвратом, альфа-бета отсечения<br /> * Monte Carlo tree search<br /> <br /> === Направления развития ===<br /> * Использование машинного обучения при оценке позиций<br /> * Более серьёзные хаки в джава-скрипте - предсказание последующих ходов сервера<br /> <br /> === Критерии оценки ===<br /> Должен получиться бот, который с неплохой вероятностью получает в одном из квадратов:<br /> <br /> * удв - 4096<br /> * хор - 8192<br /> * отл - 16384</div>

Gusakov https://wiki.cs.hse.ru/index.php?title=2048_(%D0%BF%D1%80%D0%BE%D0%B5%D0%BA%D1%82)&diff=416 2014-11-19T11:25:12Z

<p>Gusakov: /* Критерии оценки */</p> <hr /> <div>{{Карточка_проекта<br /> |name=2048<br /> |mentor=Алексей Гусаков<br /> |mentor_login={{URLENCODE:{{REVISIONUSER}}|WIKI}}<br /> |semester=Весна 2015<br /> |course=1<br /> |summer=<br /> |categorize=yes<br /> }}<br /> <br /> === Что это за проект? ===<br /> 2048 - игра, известная многим офисным работникам. В неё можно играть онлайн, например, здесь http://go2048.com/<br /> <br /> Цель проекта - создать бота, который будет набирать больше, чем могут люди.<br /> <br /> === Чему вы научитесь? ===<br /> * Переборным решениям для игровых задач<br /> * Альфа-бета отсечениям<br /> * Monte Carlo tree search для оценки позиций<br /> * Хакать javascript<br /> <br /> === Какие начальные требования? ===<br /> Программирование на C/C++ (в рамках прослушанного курса)<br /> <br /> === Какие будут использоваться технологии? ===<br /> * git, github<br /> * gtest<br /> <br /> === Темы вводных занятий ===<br /> * Основы теории игр<br /> * Перебор с возвратом, альфа-бета отсечения<br /> * Monte Carlo tree search<br /> <br /> === Направления развития ===<br /> Использование машинного обучения при оценке позиций<br /> Более серьёзные хаки в джава-скрипте - предсказание последующих ходов сервера<br /> <br /> === Критерии оценки ===<br /> Должен получиться бот, который с неплохой вероятностью получает в одном из квадратов:<br /> <br /> * удв - 4096<br /> * хор - 8192<br /> * отл - 16384</div>

Gusakov https://wiki.cs.hse.ru/index.php?title=2048_(%D0%BF%D1%80%D0%BE%D0%B5%D0%BA%D1%82)&diff=415 2014-11-19T11:23:59Z

<p>Gusakov: </p> <hr /> <div>{{Карточка_проекта<br /> |name=2048<br /> |mentor=Алексей Гусаков<br /> |mentor_login={{URLENCODE:{{REVISIONUSER}}|WIKI}}<br /> |semester=Весна 2015<br /> |course=1<br /> |summer=<br /> |categorize=yes<br /> }}<br /> <br /> === Что это за проект? ===<br /> 2048 - игра, известная многим офисным работникам. В неё можно играть онлайн, например, здесь http://go2048.com/<br /> <br /> Цель проекта - создать бота, который будет набирать больше, чем могут люди.<br /> <br /> === Чему вы научитесь? ===<br /> * Переборным решениям для игровых задач<br /> * Альфа-бета отсечениям<br /> * Monte Carlo tree search для оценки позиций<br /> * Хакать javascript<br /> <br /> === Какие начальные требования? ===<br /> Программирование на C/C++ (в рамках прослушанного курса)<br /> <br /> === Какие будут использоваться технологии? ===<br /> * git, github<br /> * gtest<br /> <br /> === Темы вводных занятий ===<br /> * Основы теории игр<br /> * Перебор с возвратом, альфа-бета отсечения<br /> * Monte Carlo tree search<br /> <br /> === Направления развития ===<br /> Использование машинного обучения при оценке позиций<br /> Более серьёзные хаки в джава-скрипте - предсказание последующих ходов сервера<br /> <br /> === Критерии оценки ===<br /> Должен получиться бот, который с неплохой вероятностью получает в одном из квадратов:<br /> <br /> * удв - 4096<br /> * хор - 8192<br /> * отл - 16348</div>

Gusakov https://wiki.cs.hse.ru/index.php?title=2048_(%D0%BF%D1%80%D0%BE%D0%B5%D0%BA%D1%82)&diff=414 2014-11-19T11:21:49Z

<p>Gusakov: Новая страница, с помощью формы Новый_проект</p> <hr /> <div>{{Карточка_проекта<br /> |name=2048<br /> |mentor=Алексей Гусаков<br /> |mentor_login={{URLENCODE:{{REVISIONUSER}}|WIKI}}<br /> |semester=Весна 2015<br /> |course=1<br /> |summer=<br /> |categorize=yes<br /> }}<br /> <br /> === Что это за проект? ===<br /> 2048 - игра, известная многим офисным работникам. В неё можно играть онлайн, например, здесь http://go2048.com/<br /> <br /> Цель проекта - создать бота, который будет набирать больше, чем могут люди.<br /> <br /> === Чему вы научитесь? ===<br /> * Переборным решениям для игровых задач<br /> * Альфа-бета отсечениям<br /> * Monte Carlo tree search для оценки позиций<br /> * Хатать javascript<br /> <br /> === Какие начальные требования? ===<br /> Программирование на C/C++ (в рамках прослушанного курса)<br /> <br /> === Какие будут использоваться технологии? ===<br /> * git, github<br /> * gtest<br /> <br /> === Темы вводных занятий ===<br /> * Основы теории игр<br /> * Перебор с возвратом, альфа-бета отсечения<br /> * Monte Carlo tree search<br /> <br /> === Направления развития ===<br /> Использование машинного обучения при оценке позиций<br /> Более серьёзные хаки в джава-скрипте - предсказание последующих ходов сервера<br /> <br /> === Критерии оценки ===<br /> Должен получиться бот, который с неплохой вероятностью получает в одном из квадратов:<br /> <br /> * удв - 4096<br /> * хор - 8192<br /> * отл - 16348</div>

Gusakov https://wiki.cs.hse.ru/index.php?title=%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B0_%D0%BA%D0%BE%D0%BC%D0%BC%D0%B8%D0%B2%D0%BE%D1%8F%D0%B6%D0%B5%D1%80%D0%B0_(%D0%BF%D1%80%D0%BE%D0%B5%D0%BA%D1%82)&diff=383 2014-11-17T08:00:16Z

<p>Gusakov: /* Критерии оценки */</p> <hr /> <div>{{Карточка_проекта<br /> |name=Задача коммивояжера<br /> |mentor=Алексей Гусаков<br /> |mentor_login={{URLENCODE:{{REVISIONUSER}}|WIKI}}<br /> |semester=Весна 2015<br /> |course=1<br /> |summer=<br /> |categorize=yes<br /> }}<br /> <br /> === Что это за проект? ===<br /> Задача коммивояжера заключается в отыскании самого выгодного маршрута, проходящего через заданные города с последующим возвратом в исходный город. Для этой простой задачи нет (и скорее всего не будет) решения, правильно работающего за полиномиальное время. Однако, существуют подходы, дающие неплохие практические результаты. Мы изучим два таких подхода: переборный и приближённый. В первом подходе изучим техники, позволяющие быстро находить правильное решение для 50-100 городов, во втором - быстро находить решение, которое доказуемо &quot;не сильно&quot; (в 1.5 раза) отличается от правильного. Результатом работы будет библиотека, реализующая один из двух подходов.<br /> <br /> === Чему вы научитесь? ===<br /> * Основам теории графов<br /> * Основам приближённых алгоритмов<br /> * Как использовать линейное программирование (и что это такое), чтобы оптимизировать перебор<br /> * Писать код без ошибок (ну почти что)<br /> * Визуализировать решение<br /> <br /> === Какие начальные требования? ===<br /> * Программирование на C/C++ (в рамках прослушанного курса)<br /> * Желание разбираться в алгоритмах<br /> <br /> === Какие будут использоваться технологии? ===<br /> * git, github<br /> * gtest<br /> <br /> === Темы вводных занятий ===<br /> * Основы теории графов (что это такое, базовые алгоритмы: минимальное остовное дерево, Эйлеровы циклы)<br /> * Приближённые алгоритмы, 2-оптимальное решение, паросочетания, 3/2-оптимальное решение<br /> * Алгоритмы: перебор с возвратом, метод ветвей и границ, эвристики 2-opt и 3-opt, линейное программирование<br /> <br /> === Направления развития ===<br /> Поскольку задача имеет некоторую практическую ценность, уже существует великое множество методов, помимо рассмотренных. Так например, для точного решения, помимо приведённых эвристик, могут быть полезны генетические алгоритмы, а для специального случая, когда расстояние между городами равно расстоянию на плоскости, существует полиномиальный алгоритм, находящий маршрут с любой наперёд заданной точностью.<br /> <br /> === Критерии оценки ===<br /> Как уже сказано, есть два пути решения задачи - точный и приближённый.<br /> Точный путь:<br /> * удв: Алгоритм работает на графе до 20 вершин, с помощью визуализатора можно понять, как всё работает<br /> * хор: Реализованы 2-opt и 3-opt, алгоритм работает для 50 вершин<br /> * отл: Метод ветвей и границ с линейным программированием<br /> <br /> Приближённый путь:<br /> * удв: Алгоритм, который выдаёт какое-нибудь решение и оценку сверху на ошибку + визуализация<br /> * хор: 2-приближение с помощью эйлерова цикла<br /> * отл: 3/2-приближение с использованием поиска паросочетания</div>

Gusakov https://wiki.cs.hse.ru/index.php?title=%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B0_%D0%BA%D0%BE%D0%BC%D0%BC%D0%B8%D0%B2%D0%BE%D1%8F%D0%B6%D0%B5%D1%80%D0%B0_(%D0%BF%D1%80%D0%BE%D0%B5%D0%BA%D1%82)&diff=382 2014-11-17T07:59:37Z

<p>Gusakov: </p> <hr /> <div>{{Карточка_проекта<br /> |name=Задача коммивояжера<br /> |mentor=Алексей Гусаков<br /> |mentor_login={{URLENCODE:{{REVISIONUSER}}|WIKI}}<br /> |semester=Весна 2015<br /> |course=1<br /> |summer=<br /> |categorize=yes<br /> }}<br /> <br /> === Что это за проект? ===<br /> Задача коммивояжера заключается в отыскании самого выгодного маршрута, проходящего через заданные города с последующим возвратом в исходный город. Для этой простой задачи нет (и скорее всего не будет) решения, правильно работающего за полиномиальное время. Однако, существуют подходы, дающие неплохие практические результаты. Мы изучим два таких подхода: переборный и приближённый. В первом подходе изучим техники, позволяющие быстро находить правильное решение для 50-100 городов, во втором - быстро находить решение, которое доказуемо &quot;не сильно&quot; (в 1.5 раза) отличается от правильного. Результатом работы будет библиотека, реализующая один из двух подходов.<br /> <br /> === Чему вы научитесь? ===<br /> * Основам теории графов<br /> * Основам приближённых алгоритмов<br /> * Как использовать линейное программирование (и что это такое), чтобы оптимизировать перебор<br /> * Писать код без ошибок (ну почти что)<br /> * Визуализировать решение<br /> <br /> === Какие начальные требования? ===<br /> * Программирование на C/C++ (в рамках прослушанного курса)<br /> * Желание разбираться в алгоритмах<br /> <br /> === Какие будут использоваться технологии? ===<br /> * git, github<br /> * gtest<br /> <br /> === Темы вводных занятий ===<br /> * Основы теории графов (что это такое, базовые алгоритмы: минимальное остовное дерево, Эйлеровы циклы)<br /> * Приближённые алгоритмы, 2-оптимальное решение, паросочетания, 3/2-оптимальное решение<br /> * Алгоритмы: перебор с возвратом, метод ветвей и границ, эвристики 2-opt и 3-opt, линейное программирование<br /> <br /> === Направления развития ===<br /> Поскольку задача имеет некоторую практическую ценность, уже существует великое множество методов, помимо рассмотренных. Так например, для точного решения, помимо приведённых эвристик, могут быть полезны генетические алгоритмы, а для специального случая, когда расстояние между городами равно расстоянию на плоскости, существует полиномиальный алгоритм, находящий маршрут с любой наперёд заданной точностью.<br /> <br /> === Критерии оценки ===<br /> Как уже сказано, есть два пути решения задачи - точный и приближённый.<br /> Точный путь:<br /> * удв: Алгоритм работает на графе до 20 вершин, с помощью визуализатора можно понять, как всё работает<br /> * хор: Реализованы 2-opt и 3-opt, алгоритм работает для 50 вершин<br /> * отл: Метод ветвей и границ с линейным программированием<br /> <br /> Приближённый путь:<br /> * удв: Алгоритм, который выдаёт какое-нибудь решение и оценку сверху на ошибку<br /> * хор: 2-приближение с помощью эйлерова цикла<br /> * отл: 3/2-приближение с использованием поиска паросочетания</div>

Gusakov https://wiki.cs.hse.ru/index.php?title=%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B0_%D0%BA%D0%BE%D0%BC%D0%BC%D0%B8%D0%B2%D0%BE%D1%8F%D0%B6%D0%B5%D1%80%D0%B0_(%D0%BF%D1%80%D0%BE%D0%B5%D0%BA%D1%82)&diff=381 2014-11-17T07:58:03Z

<p>Gusakov: Новая страница, с помощью формы Новый_проект</p> <hr /> <div>{{Карточка_проекта<br /> |name=Задача коммивояжера<br /> |mentor=Алексей Гусаков<br /> |mentor_login={{URLENCODE:{{REVISIONUSER}}|WIKI}}<br /> |semester=Весна 2015<br /> |course=1<br /> |summer=<br /> |categorize=yes<br /> }}<br /> <br /> === Что это за проект? ===<br /> Задача коммивояжера заключается в отыскании самого выгодного маршрута, проходящего через заданные города с последующим возвратом в исходный город. Для этой простой задачи нет (и скорее всего не будет) решения, правильно работающего за полиномиальное время. Однако, существуют подходы, дающие неплохие практические результаты. Мы изучим два таких подхода: переборный и приближённый. В первом подходе изучим техники, позволяющие быстро находить правильное решение для 50-100 городов, во втором - быстро находить решение, которое доказуемо &quot;не сильно&quot; (в 1.5 раза) отличается от правильного. Результатом работы будет библиотека, реализующая один из двух подходов.<br /> <br /> === Чему вы научитесь? ===<br /> * Основам теории графов<br /> * Основам приближённых алгоритмов<br /> * Как использовать линейное программирование (и что это такое), чтобы оптимизировать перебор<br /> * Писать код без ошибок (ну почти что)<br /> * Визуализировать решение<br /> <br /> === Какие начальные требования? ===<br /> * Программирование на C/C++ (в рамках прослушанного курса)<br /> * Желание разбираться в алгоритмах<br /> <br /> === Какие будут использоваться технологии? ===<br /> * git, github<br /> * gtest<br /> <br /> === Темы вводных занятий ===<br /> * Основы теории графов (что это такое, базовые алгоритмы: минимальное остовное дерево, Эйлеровы циклы)<br /> * Приближённые алгоритмы, 2-оптимальное решение, паросочетания, 3/2-оптимальное решение<br /> * Алгоритмы: перебор с возвратом, метод ветвей и границ, эвристики 2-opt и 3-opt, линейное программирование<br /> <br /> === Направления развития ===<br /> Поскольку задача имеет некоторую практическую ценность, уже существует великое множество методов, помимо рассмотренных. Так например, для точного решения, помимо приведённых эвристик, могут быть полезны генетические алгоритмы, а для специального случая, когда расстояние между городами равно расстоянию на плоскости, существует полиномиальный алгоритм, находящий маршрут с любой наперёд заданной точностью.<br /> <br /> === Критерии оценки ===<br /> Как уже сказано, есть два пути решения задачи - точный и приближённый.<br /> Точный путь:<br /> * удв: Алгоритм работает на графе до 20 вершин, с помощью визуализатора можно понять, как всё работает<br /> * хор: Реализованы 2-opt и 3-opt, алгоритм работает для 50 вершин<br /> * отл: Метод ветвей и границ с линейным программированием<br /> <br /> Приближённый путь:<br /> * удв: Алгоритм, который выдаёт какое-нибудь решение и оценку сверху на ошибку<br /> * хор: 2-приближение с помощью эйлерова цикла<br /> * отл: 3/2-приближение с использованием паросочетания</div>

Gusakov https://wiki.cs.hse.ru/index.php?title=%D0%A3%D1%87%D0%B0%D1%81%D1%82%D0%BD%D0%B8%D0%BA:Gusakov&diff=380 2014-11-17T06:35:47Z

<p>Gusakov: /* Биография */</p> <hr /> <div>= Факты =<br /> * Выпускник мехмата МГУ 2010 года<br /> * 2 место на ACM ICPC World Finals 2010<br /> * До настоящего дня работаю в московском гугле<br /> <br /> = Интересы =<br /> * Машинное обучение: ранкинг, deep learning<br /> * Математика: комбинаторная оптимизация, приближённые алгоритмы<br /> * Спорт: борьба, штанга<br /> <br /> = Контакты =<br /> * agusakov@gmail.com<br /> * +7 906 758 92 49</div>

Gusakov https://wiki.cs.hse.ru/index.php?title=%D0%A3%D1%87%D0%B0%D1%81%D1%82%D0%BD%D0%B8%D0%BA:Gusakov&diff=379 2014-11-17T06:35:22Z

<p>Gusakov: </p> <hr /> <div>= Биография =<br /> * Выпускник мехмата МГУ 2010 года<br /> * 2 место на ACM ICPC World Finals 2010<br /> * До настоящего дня работаю в московском гугле<br /> <br /> = Интересы =<br /> * Машинное обучение: ранкинг, deep learning<br /> * Математика: комбинаторная оптимизация, приближённые алгоритмы<br /> * Спорт: борьба, штанга<br /> <br /> = Контакты =<br /> * agusakov@gmail.com<br /> * +7 906 758 92 49</div>

Gusakov https://wiki.cs.hse.ru/index.php?title=%D0%A3%D1%87%D0%B0%D1%81%D1%82%D0%BD%D0%B8%D0%BA:Gusakov&diff=378 2014-11-17T06:28:39Z

<p>Gusakov: </p> <hr /> <div>= Биография =<br /> * Выпускник мехмата МГУ 2010 года<br /> * 2 место на ACM ICPC World Finals 2010<br /> * До настоящего дня работаю в московском гугле</div>

Gusakov https://wiki.cs.hse.ru/index.php?title=%D0%A3%D1%87%D0%B0%D1%81%D1%82%D0%BD%D0%B8%D0%BA:Gusakov&diff=377 2014-11-17T06:28:19Z

<p>Gusakov: Новая страница: «= Биография = Выпускник мехмата МГУ 2010 года 2 место на ACM ICPC World Finals 2010 До настоящего дня раб…»</p> <hr /> <div>= Биография =<br /> Выпускник мехмата МГУ 2010 года<br /> 2 место на ACM ICPC World Finals 2010<br /> До настоящего дня работаю в московском гугле</div>

Gusakov