City: Saint Petersburg Novosibirsk Kazan Language: Русский English

Parameterized Algorithms
Saint Petersburg / autumn 2015, посмотреть все семестры

Enroll in the course to get notifications and to be able to submit home assignments.
Register to enroll now Login

Курс будет посвящен одному из направлений построения эффективных алгоритмов для NP-трудных задач, а именно построению FPT-алгоритмов (fixed paramater tractable). По сравнению с другими направлениями, такими как построение приближенных алгоритмов, эвристик и точных алгоритмов, построение FPT алгоритмов достаточно новое направление, но при этом уже завоевавшее достаточную популярность. В курсе будет дан обзор идей и методов, использующихся при построении и анализе FPT алгоритмов, а также связь FPT алгоритмов с эвристическими, приближенными и точными алгоритмами. Первые лекции будут посвящены следующим методам: дерево расщеплений, итеративное сжатие, кернелизация. В курсе также будет рассмотрены вопросы о доказательстве нижних оценок на вычислительную сложность некоторых задач в предположении гипотезы ETH.

Курс входит в магистерскую программу Академического университета и открыт для всех желающих.

Date and time Class|Name Venue|short Materials
09 September
18:00–19:30
Введение, Lecture ПОМИ РАН video
16 September
18:00–19:30
Метод расщепления, Lecture ПОМИ РАН video
23 September
18:00–19:30
Кернелизация, Lecture ПОМИ РАН video
30 September
18:00–19:30
Метод итеративного сжатия, Lecture ПОМИ РАН video
07 October
18:00–19:30
Вероятностные методы при построении параметризованных алгоритмов , Lecture ПОМИ РАН video
14 October
18:00–19:30
Вероятностный метод и дерандомизация , Lecture ПОМИ РАН slides,  video
21 October
18:00–19:30
Динамическое программирование. Целочисленное линейное программирование. Теорема Робертсона-Сеймура, Lecture ПОМИ РАН video
28 October
18:00–19:30
Древесное разложение (tree decomposition) и древесная ширина (treewidth), Lecture ПОМИ РАН video
11 November
18:00–19:30
Древесное разложение (продолжение), Lecture ПОМИ РАН video
18 November
18:00–19:30
Построение приближенного древесного разложения, Lecture ПОМИ РАН video
25 November
18:00–19:30
Теорема Курселя. Win/win подход, Lecture ПОМИ РАН slides,  video
02 December
18:00–19:30
Метод сдвига, Lecture ПОМИ РАН video
09 December
18:00–19:30
Нижние оценки. Класс W[1], Lecture ПОМИ РАН slides,  video
16 December
18:00–19:30
Доказательство нижних оценок с помощью гипотезы ETH, Lecture ПОМИ РАН video