Алгоритмы для NP трудных задач осень 2017 — различия между версиями
Материал из SEWiki
Bliznets (обсуждение | вклад) (→Практика) |
Bliznets (обсуждение | вклад) (→Лекции) |
||
| Строка 1: | Строка 1: | ||
Преподаватель: Близнец Иван Анатольевич ([mailto:iabliznets@gmail.com iabliznets@gmail.com]) | Преподаватель: Близнец Иван Анатольевич ([mailto:iabliznets@gmail.com iabliznets@gmail.com]) | ||
| − | + | = Лекции = | |
* 13 сентября. Метод расщепления. | * 13 сентября. Метод расщепления. | ||
| Строка 8: | Строка 8: | ||
* 4 октября. Измеряй и побеждай. | * 4 октября. Измеряй и побеждай. | ||
* 11 октября. Применение полиномиальных алгоритмов для построения точных экспоненциальных алгоритмов. Конволюция подмножеств. | * 11 октября. Применение полиномиальных алгоритмов для построения точных экспоненциальных алгоритмов. Конволюция подмножеств. | ||
| + | * 18 октября. Конволюция подмножеств(продолжение). | ||
| + | * 25 октября. Древесное и путевое разложение. Динамическое программирование на основе древесного разложения. | ||
| + | * 1 ноября. Путевая ширина субкубических графов. | ||
| + | * 8 ноября. Вычисление древесной ширины используя полиномиальную память. | ||
| + | * 15 ноября. Динамическое программирование для задачи о дереве Штейнера на основе динамического разложения. | ||
| + | * 22 ноября. Метод локального поиска. | ||
| + | * 29 ноября. Метод монотонного локального поиска. | ||
| + | * 13 декабря. Компромиии между памятью и временем. Меморизация. | ||
| + | * 20 декабря. ETH и SETH гипотезы. | ||
| + | |||
| + | |||
| + | |||
| + | == Литература == | ||
== Практика == | == Практика == | ||
Версия 01:43, 25 декабря 2017
Преподаватель: Близнец Иван Анатольевич (iabliznets@gmail.com)
Лекции
- 13 сентября. Метод расщепления.
- 20 сентября. Динамическое программирование.
- 27 сентября. Метод включения-исключения.
- 4 октября. Измеряй и побеждай.
- 11 октября. Применение полиномиальных алгоритмов для построения точных экспоненциальных алгоритмов. Конволюция подмножеств.
- 18 октября. Конволюция подмножеств(продолжение).
- 25 октября. Древесное и путевое разложение. Динамическое программирование на основе древесного разложения.
- 1 ноября. Путевая ширина субкубических графов.
- 8 ноября. Вычисление древесной ширины используя полиномиальную память.
- 15 ноября. Динамическое программирование для задачи о дереве Штейнера на основе динамического разложения.
- 22 ноября. Метод локального поиска.
- 29 ноября. Метод монотонного локального поиска.
- 13 декабря. Компромиии между памятью и временем. Меморизация.
- 20 декабря. ETH и SETH гипотезы.
Литература
Практика
Крайний срок сдачи 20 сентября.
Крайний срок сдачи 27 сентября до начала занятия.
Крайний срок сдачи 07 октября 21:00.
Крайний срок сдачи 11 октября.
Крайний срок сдачи 18 октября.
Крайний срок сдачи 25 октября.
Крайний срок сдачи 1 ноября до начала занятия.
Крайний срок сдачи 8 ноября до начала занятия.
Крайний срок сдачи 15 ноября до начала занятия.
Крайний срок сдачи 22 ноября до начала занятия.
Крайний срок сдачи 13 декабря до начала занятия.
Крайний срок сдачи 20 декабря до начала занятия.
