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

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

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

В курсе будет дан обзор идей и методов, использующихся при построении и анализе алгоритмов для NP-трудных задач. Несмотря на то что эффективных алгоритмов для таких задач до сих пор неизвестно, NP-трудные задачи часто возникают на практике. Мы рассмотрим приближённые алгоритмы (позволяющие эффективно находить решение, которое гарантированно не сильно хуже оптимального), точные алгоритмы с доказуемыми верхними оценками (которые более интересны с теоретической точки зрения) и эвристики (алгоритмы, хорошо работающие на практике, но не имеющие теоретических гарантий на время работы и ошибку приближения).

Отдельное внимание будет уделено открытым задачам данной области.

Курс предполагает знакомство слушателей лишь с базовыми алгоритмическими идеями.

Основная литература:

  • Книги:
    1. [FK10] Fedor V. Fomin and Dieter Kratsch. Exact Exponential Algorithms. Springer. 2010. [official]
    2. [V01] Vijay V. Vazirani. Approximation Algorithms. Springer. 2001. [official], [PDF]
    3. [WS11] David P. Williamson and David B. Shmoys. The Design of Approximation Algorithms. Cambridge University Press. 2011. [official], [PDF]
    4. [DPV06] Sanjoy Dasgupta, Christos Papadimitriou, Umesh Vazirani. Algorithms. McGraw-Hill. 2006. [official], [PDF]
    5. [CLR01] Томас Х. Кормен, Чарльз И. Лейзерсон, Рональд Л. Ривест. Алгоритмы: построение и анализ. Издательство МЦНМО. 2001.
  • Обзоры:
    1. [W03] Gerhard J. Woeginger. Exact algorithms for NP-hard problems: a survey. Combinatorial optimization - Eureka, you shrink! Springer. 2003. [official], [PDF]
    2. [FK13] Fedor V. Fomin, Petteri Kaski. Exact exponential algorithms. Communications of the ACM. 2013. [official], [PDF]
    3. [YWHL13] Dongxiao Yu, Yuexuan Wang, Qiang-Sheng Hua, Francis C.M. Lau. Faster and Space Efficient Exact Exponential Algorithms: Combinatorial and Algebraic Approaches. Handbook of Combinatorial Optimization, Springer. 2013, pp 1249-1291. [official], [PDF]
  • Lecture notes:
    1. [A09] AGAPE Spring School on Fixed Parameter and Exact Algorithms. [PDF]

Дата и время Занятие Место Материалы
15 сентября
11:15–12:50
Введение, Лекция ПОМИ РАН видео
22 сентября
11:15–13:00
NP-полные задачи, Лекция ПОМИ РАН видео
22 сентября
13:00–14:35
Точные алгоритмы для задачи коммивояжёра и задачи о гамильтоновом цикле, Лекция ПОМИ РАН видео
06 октября
11:15–12:50
Приближённые алгоритмы для задачи коммивояжёра, Лекция ПОМИ РАН видео
13 октября
11:15–12:50
Приближённые алгоритмы для задачи коммивояжёра (продолжение), Лекция ПОМИ РАН видео
13 октября
13:00–14:35
Точные алгоритмы для задачи о максимальном разрезе и задачи максимальной 2-выполнимости, Лекция ПОМИ РАН видео
27 октября
11:15–12:50
Эвристики для задачи коммивояжёра, алгоритмы для задачи о надстроке, Лекция ПОМИ РАН Нет
27 октября
13:00–14:35
Точные алгоритмы для задачи раскраски графа, Лекция ПОМИ РАН видео,  файлы
10 ноября
11:15–12:50
Алгоритмы для задачи выполнимости: локальный поиск, Лекция ПОМИ РАН видео,  файлы
10 ноября
13:00–14:35
Алгоритмы для задачи выполнимости: метод расщепления, Лекция ПОМИ РАН видео
17 ноября
11:15–12:50
Приближённые алгоритмы, Лекция ПОМИ РАН видео
17 ноября
13:00–14:35
Приближённые алгоритмы, Лекция ПОМИ РАН видео