Дискретная оптимизация 2018 — различия между версиями

Версия 01:52, 5 июня 2018

О курсе

Курс читается для студентов 3-го курса ПМИ ФКН ВШЭ в 4 модуле.

Лектор: Игнат Колесниченко

Лекции ПМИ проходят по вторникам, 13:40 - 15:00, ауд. 622.

Полезные ссылки

Канал в телеграм для объявлений: https://t.me/joinchat/AAAAAFD1-ZdchZS1FoOduA

Таблица с оценками: TODO

Оставить отзыв на курс: TODO

Семинары

Консультации

Консультации с преподавателями и учебными ассистентами (если иное не оговорено на странице семинаров конкретной группы) по курсу проводятся по предварительной договорённости ввиду невостребованности регулярных консультаций.

Правила выставления оценок

В курсе предусмотрено 3 домашних задания – 2 практических и 1 теоретическое. За каждое домашнее задание выставляется оценка по 10-бальной шкале, правила получения оценки будут оговариваться при публикации домашнего задания.

Итоговая оценка вычисляется исходя из оценок за домашние задания

O_{итоговая} = 0.33 * O_ДЗ1 + 0.33 * О_ДЗ2 + 0.34 * О_ДЗ3

Также на семинарах иногда будут выдаваться небольшие домашние задания. Их решение будет засчитываться как доп. баллы в домашних заданиях (доп. баллы к исходной оценке в ДЗ, а не к результирующей).

Правила сдачи заданий

Дедлайны по всем домашним заданиям являются жёсткими, то есть после срока работы не принимаются.

При обнаружении плагиата оценки за домашнее задание обнуляются всем задействованным в списывании студентам, а также подаётся докладная записка в деканат. Следует помнить, что при повторном списывании деканат имеет право отчислить студента.

При наличии уважительной причины дедлайн по домашнему заданию может быть перенесён. Дедлайн по домашнему заданию переносится на количество дней, равное продолжительности уважительной причины. Решение о том, является ли причина уважительной, принимает исключительно учебный офис.

Лекции

Лекция 1 (3 апреля). Метод Branch&Bound решения оптимизационных задач. Задача о рюкзаке: 2-приближение, динамическое программирование по весам и по стоимостям.

Семинары

Семинар 1 (2-7 апреля). Напоминание о линейном и целочисленном программирование. Построение двойственных программ. Задача о поиске максимального паросочетания в двудольном графе.

Домашние задания

Домашнее задание 1 (практика)

Дедлайн: 14 мая 23:59

В домашнем задании требуется решить три практических задачи, архив с условием: https://yadi.sk/d/t9yrhBy-3UiVgA

Контест для сдачи задач: https://contest.yandex.ru/contest/8104/

Грейдер для задачи о рюкзаке: http://akhmedov.me:50010/knapsack

Задание следует отправлять на почту discret.opt.hse@gmail.com. В заголовке письма с решением указывайте "[Название группы] ФИО Домашнее задание 1". В случае вопроса добавляйте в заголовок письма слово "вопрос".

Критерий оценки задачи о рюкзаке

Оценивание производилось на закрытых тестах. Оценка ставится в зависимости от отличия вашего решения и оптимального решения. Также в случае отсутствия отчета или плохо написанного отчета семинарист вправе снять еще до 1 балла.

Суммарная ошибка 0 – 6 баллов.

Суммарная ошибка <200 – 5 баллов.

Суммарная ошибка <1500 – 4 балла.

Суммарная ошибка <5000 – 3 балла.

Суммарная ошибка <15000 – 2 балла.

Суммарная ошибка <21000 – 1 балл.

Последняя граница выбрана исходя из того, что стандартное жадное решение имеет ошибку примерно 20800)

Домашнее задание 2 (теория)

Дедлайн: 2 июня 23:59

В домашнем задании требуется решить 5 теоретических задач, условия: https://yadi.sk/i/o4gtEhpA3VywLM

В качестве решения в каждой задачи должно быть подробное доказательство требуемого факта/описание работы алгоритма/структуры данных с оценкой времени его работы. При выполнении этого домашнего задания можно использовать все алгоритмы и теоремы, которые были разобраны и доказаны на лекциях и семинарах. Однако, следует подробно объяснить к чему и как они применяются.

Решения настоятельно рекомендуется записывать в latex-е.

Оценка будет выставлять по формуле min(10, баллы за решение + баллы за семинар 1 + баллы за семинар 2)

Задание следует отправлять на почту discret.opt.hse@gmail.com. В заголовке письма с решением указывайте "[Название группы] ФИО Домашнее задание 2". В случае вопроса добавляйте в заголовок письма слово "вопрос".

Полезные материалы

Рекомендуемая литература

 * "B.Korte, J.Vygen – Combinatorial optimization" – подробная книга по теории комбинаторной оптимизации (http://www.or.uni-bonn.de/~vygen/co.html).
 * "V. Vazirani – Approximation Algorithms" – одна из лучших книг по приближенным алгоритмам.
 * "H. Papadimitriou – Combinatorial Optimization: Algorithms and Complexity" – классический учебник по комбинаторной оптимизации. 
 * "Where are the hard knapsack problems?" [David Pisinger] - интересные рассуждения по поводу того, как генерировать сложные тесты для задачи о рюкзаке.
 * ["Heuristics for the Traveling Salesman Problem" [Christian Nilsson]]  - краткое но насыщенное описание эвристик для задачи о коммивояжёре.
 * "Handbook of Constraint Programming" [F. Rossi, P. van Beek and T. Walsh] - справочник по программированию в ограничениях.
 * "Handbook of Metaheuristics" [Michel Gendreau, Jean-Yves Potvin] - справочник с описанием эвристических алгоритмов оптимизации.

Полезные ссылки

 * [Визуализатор маршрута коммивояжёра] (вершины подаются в 0-индексации)
 * Курс по дискретной оптимизации на [Coursera]. Содержит хорошие видео-лекции по Constraint Programming и Local Search.

Библиотеки для решения задач оптимизации

 *  [Google Optimization Tools] (C++, Python, Java, C#) - фреймворк для решения задач дискретной оптимизаций. Позволяет программировать в парадигме Constraint Programming. Содержит инструменты для решения задач линейного программирования. ([Более полная документация])
 * [Numberjack] (Python)
 * [Choco] (Java)
 * [Gecode] (C++)
 * [MiniZinc] (MiniZinc) - Довольно выразительный язык для CP. Есть ((http://www.hakank.org/minizinc/ много примеров)).