Алгоритмы для NP трудных задач осень 2017

Преподаватель: Близнец Иван Анатольевич (iabliznets@gmail.com)

Лекции

• 13 сентября. Метод расщепления.
• 20 сентября. Динамическое программирование.
• 27 сентября. Метод включения-исключения.
• 4 октября. Измеряй и побеждай.
• 11 октября. Применение полиномиальных алгоритмов для построения точных экспоненциальных алгоритмов. Конволюция подмножеств.
• 18 октября. Конволюция подмножеств(продолжение).
• 25 октября. Древесное и путевое разложение. Динамическое программирование на основе древесного разложения.
• 1 ноября. Путевая ширина субкубических графов.
• 8 ноября. Вычисление древесной ширины используя полиномиальную память.
• 15 ноября. Динамическое программирование для задачи о дереве Штейнера на основе динамического разложения.
• 22 ноября. Метод локального поиска.
• 29 ноября. Метод монотонного локального поиска.
• 13 декабря. Компромиcc между памятью и временем. Меморизация.
• 20 декабря. ETH и SETH гипотезы.

Литература

• Cygan et al., Parameterized algorithms. скачать
• Fedor Fomin and Stefan Kratsch, Exact Exponential Algorithms. скачать
• Fomin et al., Exact Algorithms via Monotone Local Search. скачать
• Bodlaender et al., On exact algorithms for treewidth. скачать

Практика

Результаты практики

• 13 сентября, "Метод расщепления"
• 13 сентября, "Метод расщепления (ДЗ)"

Крайний срок сдачи 20 сентября.

• 19 сентября, "Динамическое программирование"
• 19 сентября, "Динамическое программирование (ДЗ)"

Крайний срок сдачи 27 сентября до начала занятия.

• 26 сентября, "Метод включения-исключения (ДЗ)"

Крайний срок сдачи 07 октября 21:00.

• 4 октября, "Измеряй и побеждай (ДЗ)"

Крайний срок сдачи 11 октября.

• 11 октября, "Применение полиномиальных алгоритмов для построения точных экспоненциальных алгоритмов. Конволюция подмножеств.(ДЗ)"

Крайний срок сдачи 18 октября.

• 18 октября, "Конволюция подмножеств.(ДЗ)"

Крайний срок сдачи 25 октября.

• 25 октября, "Древесное разложение"
• 25 октября, "Древесное разложение (ДЗ)"

Крайний срок сдачи 1 ноября до начала занятия.

• 1 ноября, "Древесное разложение II(ДЗ)"

Крайний срок сдачи 8 ноября до начала занятия.

• 8 ноября, "Древесное разложение III(ДЗ)"

Крайний срок сдачи 15 ноября до начала занятия.

• 15 ноября, "Древесное разложение IV(ДЗ)"

Крайний срок сдачи 22 ноября до начала занятия.

• 22 ноября, "Метод локального поиска(ДЗ)"

Крайний срок сдачи 13 декабря до начала занятия.

• 13 декабря, "Меморизация и монотонный локальный поиск"

Крайний срок сдачи 20 декабря до начала занятия.