В курсе будут рассмотрены красивые идеи построения алгоритмов для NP–трудных задач — от классических до недавних результатов. Предварительный список тем: точные алгоритмы (расщепление, локальный поиск, умный перебор, сведение к простой задаче), fixed parameter tractable алгоритмы (kernelization, color coding, алгоритмы, основанные на матричном умножении и формуле включений–исключений), приближённые алгоритмы (алгоритмы, основанные на линейном и полуопределённом программировании).
Ссылки по теме:
| Дата и время | Занятие | Место | Материалы |
|---|---|---|---|
| 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-алгоритмы, Лекция | ПОМИ РАН | слайды, видео, файлы |
