Алгоритмы для NP трудных задач осень 2017 — различия между версиями
Материал из SEWiki
Bliznets (обсуждение | вклад) (→Лекции) |
Bliznets (обсуждение | вклад) (→Лекции) |
||
| Строка 15: | Строка 15: | ||
* 22 ноября. Метод локального поиска. | * 22 ноября. Метод локального поиска. | ||
* 29 ноября. Метод монотонного локального поиска. | * 29 ноября. Метод монотонного локального поиска. | ||
| − | * 13 декабря. | + | * 13 декабря. Компромиcc между памятью и временем. Меморизация. |
* 20 декабря. ETH и SETH гипотезы. | * 20 декабря. ETH и SETH гипотезы. | ||
'''Литература''' | '''Литература''' | ||
| − | * Cygan et | + | * Cygan et al., Parameterized algorithms. [http://parameterized-algorithms.mimuw.edu.pl/parameterized-algorithms.pdf скачать] |
* Fedor Fomin and Stefan Kratsch, Exact Exponential Algorithms. [http://www.ii.uib.no/~fomin/BookEA/BookEA.pdf скачать] | * Fedor Fomin and Stefan Kratsch, Exact Exponential Algorithms. [http://www.ii.uib.no/~fomin/BookEA/BookEA.pdf скачать] | ||
| + | * Fomin et al., Exact Algorithms via Monotone Local Search. [https://arxiv.org/pdf/1512.01621.pdf скачать] | ||
| + | * Bodlaender et al., On exact algorithms for treewidth. [https://dspace.library.uu.nl/bitstream/handle/1874/22183/2006-032.pdf?sequence=1 скачать] | ||
== Практика == | == Практика == | ||
Текущая версия на 01:57, 25 декабря 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. скачать
Практика
Крайний срок сдачи 20 сентября.
Крайний срок сдачи 27 сентября до начала занятия.
Крайний срок сдачи 07 октября 21:00.
Крайний срок сдачи 11 октября.
Крайний срок сдачи 18 октября.
Крайний срок сдачи 25 октября.
Крайний срок сдачи 1 ноября до начала занятия.
Крайний срок сдачи 8 ноября до начала занятия.
Крайний срок сдачи 15 ноября до начала занятия.
Крайний срок сдачи 22 ноября до начала занятия.
Крайний срок сдачи 13 декабря до начала занятия.
Крайний срок сдачи 20 декабря до начала занятия.
