Город: Санкт-Петербург Новосибирск Казань Язык: Русский English

Параметризованные алгоритмы
Санкт-Петербург / осень 2015, посмотреть все семестры

Запишитесь на курс, чтобы получать уведомления и иметь возможность сдавать домашние задания. Для записи требуется регистрация на сайте.
Перейти к регистрации Войти
TBA
Дата и время Занятие Место Материалы
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, Лекция ПОМИ РАН видео