Алгоритмы для NP-трудных задач

Общая информация
ЛекторА. С. Куликов
Семестросень 2009
Дата начала13.09.2009
Количество пар12
Язык курсарусский
Видеоhttp://lektorium.tv/course/?id=22758
Аннотация В курсе будут рассмотрены красивые идеи построения алгоритмов для NP–трудных задач — от классических до недавних результатов. Предварительный список тем: точные алгоритмы (расщепление, локальный поиск, умный перебор, сведение к простой задаче), fixed parameter tractable алгоритмы (kernelization, color coding, алгоритмы, основанные на матричном умножении и формуле включений–исключений), приближённые алгоритмы (алгоритмы, основанные на линейном и полуопределённом программировании).

Ссылки по теме
Слайды первой лекции
Лекции Подсказка: слайды, видеозапись и другие материалы лекции доступны со страницы лекции, попасть на которую можно, нажав на её название.

1. Обзор
(13.09.2009 - 10:00)

P и NP неформально. Точные алгоритмы. $ \sqrt{3}^n $ алгоритм, основанный на локальном поиске, для задачи выполнимости. $ 1.732^n $ алгоритм для задачи о максимальном разрезе, использующий быстрое умножение матриц для нахождения треугольников. http://video.yandex.ru/users/pdmicsclub/view/1/?cauthor=pdmicsclub&cid=1
2. Обзор
(13.09.2009 - 10:15)

FPT алгоритмы. Kernelization. $ k(k+1) $ ядро для задачи о покрытии точек прямыми. $ k(k+1) $ ядро для задачи о вершинном покрытии, основанное на простых правилах упрощениях, и $ 4k $ ядро, основанное на crown decomposition lemma. Приближённые алгоритмы. 2-оптимальный алгоритм для задачи о вершинном покрытии. 2-оптимальный алгоритм для задачи о коммивояжере в метрическом пространстве. http://video.yandex.ru/users/pdmicsclub/view/8/?cauthor=pdmicsclub&cid=1
3. NP-полные задачи
(25.10.2009 - 10:20)

Задачи поиска, NP-полные задачи, сведения. http://video.yandex.ru/users/pdmicsclub/view/29/
4. Вероятностные алгоритмы
(25.10.2009 - 10:25)

$ 1.5^n $ алгоритм для задачи о 3-раскрашиваемости графа. $ \log(2n) $-приближенный алгоритм для задачи о минимальном множестве представителей. FPT-алгоритм для задачи о пути длины $ k $. $ 2^{2n/3} $ алгоритм для 3-SAT. http://video.yandex.ru/users/pdmicsclub/view/28/
5. Приближенные алгоритмы
(01.11.2009 - 10:30)

$ \log{n} $-приближенный алгоритм для задачи о покрытии множествами, $ 2\log{n} $-приближенный алгоритм для задачи о кратчайшей надпоследовательности. http://video.yandex.ru/users/pdmicsclub/view/32/
6. Приближенные алгоритмы
(01.11.2009 - 10:35)

$ 3/2 $-приближенный алгоритм для задачи о коммивояжере в метрическом пространстве, неприближаемость задачи о коммивояжере, полностью полиномиальная приближенная схема для задачи о рюкзаке. http://video.yandex.ru/users/pdmicsclub/view/30/
7. Приближенные алгоритмы
(01.11.2009 - 10:45)

Приближенные алгоритмы, основанные на решении задачи полуопределенного программирования. $ 0.87 $-приближенный алгоритм для задачи о максимальном разрезе, раскраска вершин $ 3 $-раскрашиваемого графа в $ O(d^{0.631}) $ цветов, где $ d $ - средняя степень вершин графа. http://video.yandex.ru/users/pdmicsclub/view/50/
8. Алгоритмы расщепления
(08.11.2009 - 10:35)

Оценка времени работы алгоритмов расщепления, правила упрощения, простой $ 1.415^K $, где $ K $ - количество клозов, алгоритм, основанный на методе расщепления, для задачи выполнимости, автоматический анализ времени работы. http://video.yandex.ru/users/pdmicsclub/view/43/
9. Алгоритмы расщепления
(08.11.2009 - 10:40)

Комбинированные меры сложности, верхняя оценка $ 2^{K/5.5} $ для задачи максимальной 2-выполнимости, запоминание дизъюнктов, решение задачи выполнимости формул константной плотности быстрее чем за $ 2^n $ шагов. http://video.yandex.ru/users/pdmicsclub/view/47/
10. Точные и FPT-алгоритмы
(29.11.2009 - 10:45)

Формула включений-исключений. Задача о гамильтоновом пути, задача о количестве совершенных паросочетаний. Сведение к простой задаче. Задача о сумме подмножества, задача максимальной 2-выполнимости.
11. FPT-алгоритмы
(06.12.2009 - 10:50)

Лемма о подсолнухе. Задача о минимальном множестве представителей. Динамическое программирование. Задача о дереве Штайнера. Итеративное сжатие. Задача об удалении нечетных циклов.
Ваша оценка: Пусто Средняя: 3.7 (3 голосов)
Share |
Александр Куликов и студенты CS-клуба