Алгоритмы для NP-трудных задач
Один из ключевых открытых вопросов компьютерных наук – равенство классов P и NP: если корректность решения можно проверить за полиномиальное время, можно ли столь же эффективно его найти? NP-трудные задачи находятся в центре этого вопроса и задают фундаментальные ограничения для алгоритмов во многих практических областях — от оптимизации и планирования до анализа графов и вычислительной логики.
В курсе рассматриваются NP-трудные задачи и основные подходы к работе с ними: точные экспоненциальные алгоритмы, приближённые методы, параметризованные алгоритмы и решения для частных случаев. Классические задачи, такие как 3-раскраска графа, используются как базовые примеры для понимания общих принципов и границ применимости алгоритмических методов.
Пререквизиты: базовый курс по алгоритмам.
Занятия
12 лекцийЛекция 1
Введение в курс. 5 алгоритмов для задачи Vertex Cover
Лекция 2
Линейные ядра для Vertex Cover, Color Coding для -пути
Лекция 3
Алгоритмы для задач о Гамильтоновом пути и ориентированном -пути
Лекция 4
Алгоритм для -пути в неориентированных графах
Лекция 5
Агоритм Кристофидеса-Сердюкова
Лекция 6
Точные алгоритмы для Max Cut
Лекция 7
Приближенные алгоритмы для Max Cut. Задача о раскраске
Лекция 8
Задача о хроматическом числе
Лекция 9
Приближенный алгоритм для 3-раскраски графа. Локальный поиск для 3-SAT
Лекция 10
Monotone Local Search
Лекция 11
Max-SAT: нижние оценки и алгоритмы поверх них
Лекция 12
Гипотезы и нижние оценки
