Сайт в процессе наполнения. Архив всех прошедших курсов доступен на старой версии сайта по адресу old.compsciclub.ru
Город: Санкт-Петербург Казань Язык: Русский 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-алгоритмы, лекция ПОМИ РАН слайдывидео, файлы