Алгоритмы для NP трудных задач осень 2017 — различия между версиями
Материал из SEWiki
Bliznets (обсуждение | вклад) |
Bliznets (обсуждение | вклад) (→Лекции) |
||
| (не показано 26 промежуточных версий 2 участников) | |||
| Строка 1: | Строка 1: | ||
Преподаватель: Близнец Иван Анатольевич ([mailto:iabliznets@gmail.com iabliznets@gmail.com]) | Преподаватель: Близнец Иван Анатольевич ([mailto:iabliznets@gmail.com 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. [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 скачать] | ||
| + | * 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 скачать] | ||
== Практика == | == Практика == | ||
| + | [https://docs.google.com/spreadsheets/d/1uazdRP-EL5jpRGw9l4LEk5HqIJ3dRytfOcjIpWF0lsU/edit#gid=0 Результаты практики] | ||
*[[Медиа:NP-class-1.pdf|13 сентября, "Метод расщепления"]] | *[[Медиа:NP-class-1.pdf|13 сентября, "Метод расщепления"]] | ||
*[[Медиа:NP-home-1.pdf|13 сентября, "Метод расщепления (ДЗ)"]] | *[[Медиа:NP-home-1.pdf|13 сентября, "Метод расщепления (ДЗ)"]] | ||
| − | Крайний срок сдачи | + | Крайний срок сдачи 20 сентября. |
| + | *[[Медиа:NP-class-2.pdf|19 сентября, "Динамическое программирование"]] | ||
| + | *[[Медиа:NP-home-2.pdf|19 сентября, "Динамическое программирование (ДЗ)"]] | ||
| + | Крайний срок сдачи 27 сентября до начала занятия. | ||
| + | *[[Медиа:NP-home-3.pdf|26 сентября, "Метод включения-исключения (ДЗ)"]] | ||
| + | Крайний срок сдачи 07 октября 21:00. | ||
| + | *[[Медиа:NP-home-4.pdf|4 октября, "Измеряй и побеждай (ДЗ)"]] | ||
| + | Крайний срок сдачи 11 октября. | ||
| + | *[[Медиа:NP-home-5.pdf|11 октября, "Применение полиномиальных алгоритмов для построения точных экспоненциальных алгоритмов. Конволюция подмножеств.(ДЗ)"]] | ||
| + | Крайний срок сдачи 18 октября. | ||
| + | *[[Медиа:NP-home-6.pdf|18 октября, "Конволюция подмножеств.(ДЗ)"]] | ||
| + | Крайний срок сдачи 25 октября. | ||
| + | *[[Медиа:NP-class-7.pdf|25 октября, "Древесное разложение"]] | ||
| + | *[[Медиа:NP-home-7.pdf|25 октября, "Древесное разложение (ДЗ)"]] | ||
| + | Крайний срок сдачи 1 ноября до начала занятия. | ||
| + | *[[Медиа:NP-home8.pdf|1 ноября, "Древесное разложение II(ДЗ)"]] | ||
| + | Крайний срок сдачи 8 ноября до начала занятия. | ||
| + | *[[Медиа:NP-home9.pdf|8 ноября, "Древесное разложение III(ДЗ)"]] | ||
| + | Крайний срок сдачи 15 ноября до начала занятия. | ||
| + | *[[Медиа:NP-home10.pdf|15 ноября, "Древесное разложение IV(ДЗ)"]] | ||
| + | Крайний срок сдачи 22 ноября до начала занятия. | ||
| + | *[[Медиа:NP-home11.pdf|22 ноября, "Метод локального поиска(ДЗ)"]] | ||
| + | Крайний срок сдачи 13 декабря до начала занятия. | ||
| + | *[[Медиа:NP-home12.pdf|13 декабря, "Меморизация и монотонный локальный поиск"]] | ||
| + | Крайний срок сдачи 20 декабря до начала занятия. | ||
Текущая версия на 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 декабря до начала занятия.
