Параметризованные алгоритмы

Общая информация
ЛекторИ. А. Близнец
Семестросень 2015
Дата начала09.09.2015
Количество пар14
Язык курсарусский
Аннотация

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

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

Лекции Подсказка: слайды, видеозапись и другие материалы лекции доступны со страницы лекции, попасть на которую можно, нажав на её название.

1. Введение
(09.09.2015 - 18:00 - 19:30)

Введение. FPT алгоритм. Связь FPT алгоритмов с другими типами алгоритмов. Кернелизация. Простейшие примеры. Вершинное покрытие (Vertex Cover). Feedback Vertex Set.
2. Метод расщепления
(16.09.2015 - 18:00 - 19:30)

Метод расщепления (Bounded Search Trees, DPLL-algorithms). Вершинное покрытие $ 1.47^k $ (Vertex Cover). Задача о разрезании контуров $ (3k)^k \cdot poly(n) $ (Feedback Vertex Set). Ближайшая строка $ O^*((d+1)^d) $ (Closest String).
3. Лекция
(23.09.2015 - 18:00 - 19:30)

4. Лекция
(30.09.2015 - 18:00 - 19:30)

5. Лекция
(07.10.2015 - 18:00 - 19:30)

6. Лекция
(14.10.2015 - 18:00 - 19:30)

7. Лекция
(21.10.2015 - 18:00 - 19:30)

8. Лекция
(28.10.2015 - 18:00 - 19:30)

9. Лекция
(04.11.2015 - 18:00 - 19:30)

10. Лекция
(11.11.2015 - 18:00 - 19:30)

11. Лекция
(18.11.2015 - 18:00 - 19:30)

12. Лекция
(25.11.2015 - 18:00 - 19:30)

13. Лекция
(02.12.2015 - 18:00 - 19:30)

Ваша оценка: Пусто Средняя: 4 (4 голосов)
Share |