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

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

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

We will consider some interesting ideas of designing algorithms for NP–hard problems — from classical to recent ones. Preliminary program: exact algorithms (splitting, local search, clever enumeration, reduction to an easy problem), fixed parameter tractable algorithms (kernelization, color coding, algorithms based on matrix multiplication and inclusion–exclusion principle), approximation algorithms (algorithms based on linear and semidefinite programming).

Links

Дата и время Название Место Материалы
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-алгоритмы, лекция ПОМИ РАН слайдывидео, файлы