Сайт в процессе наполнения. Архив всех прошедших курсов доступен на старой версии сайта по адресу old.compsciclub.ru
Город: Санкт-Петербург Казань Язык: Русский English

Параметризованные алгоритмы
Осень 2015, посмотреть все семестры

Запишитесь на курс, чтобы получать уведомления и иметь возможность сдавать домашние задания. Для записи требуется регистрация на сайте.
Перейти к регистрации Войти

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

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

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