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

Алгоритмы для NP-трудных задач
Санкт-Петербург / осень 2009, посмотреть все семестры

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

В курсе будут рассмотрены красивые идеи построения алгоритмов для NP–трудных задач — от классических до недавних результатов. Предварительный список тем: точные алгоритмы (расщепление, локальный поиск, умный перебор, сведение к простой задаче), fixed parameter tractable алгоритмы (kernelization, color coding, алгоритмы, основанные на матричном умножении и формуле включений–исключений), приближённые алгоритмы (алгоритмы, основанные на линейном и полуопределённом программировании).

Ссылки по теме:

Видео курса: https://www.lektorium.tv/course/22758?id=22758
Дата и время Занятие Место Материалы
13 сентября
10:00–11:30
Обзор, Лекция ПОМИ РАН слайды,  видеофайлы
13 сентября
11:40–13:10
Обзор, Лекция ПОМИ РАН слайды,  видеофайлы
25 октября
10:20–11:50
NP-полные задачи, Лекция ПОМИ РАН слайды,  видеофайлы
25 октября
11:40–13:10
Вероятностные алгоритмы, Лекция ПОМИ РАН слайды,  видеофайлы
01 ноября
10:30–12:00
Приближенные алгоритмы, Лекция ПОМИ РАН слайды,  видеофайлы
01 ноября
12:10–13:40
Приближенные алгоритмы, Лекция ПОМИ РАН слайды,  видеофайлы
01 ноября
14:00–15:30
Приближенные алгоритмы, Лекция ПОМИ РАН слайды,  видеофайлы
08 ноября
10:35–12:05
Алгоритмы расщепления, Лекция ПОМИ РАН слайды,  видеофайлы
08 ноября
10:40–12:10
Алгоритмы расщепления, Лекция ПОМИ РАН слайды,  видеофайлы
29 ноября
10:45–12:15
Точные и FPT-алгоритмы, Лекция ПОМИ РАН слайды,  видеофайлы
06 декабря
10:50–12:20
FPT-алгоритмы, Лекция ПОМИ РАН слайды,  видеофайлы