Николай Михайлович Адрианов
NP-полные задачи
Н. М. Адрианов планирует провести 4 занятия.
Доступны 4 видеозаписи курса.
В этом курсе мы познакомимся с замечательной теорией NP-полных задач. Проблема (не)равенства классов P и NP - одна из "задач тысячелетия", за каждую из которых объявлен приз в миллион долларов. Мы разберемся в определении класса NP и научимся доказывать NP-полноту различных комбинаторных задач (классические теоремы Кука-Левина и Карпа).
Особое внимание уделим задаче выполнимости булевых формул SAT. Мы поиграем с программами, решающими эту задачу, разберем какие алгоритмы они используют, как результатом их работы может быть доказательство, допускающее автоматическую проверку. Научимся сводить логические головоломки и математические задачи к SAT, поговорим о судоку, задачах теории Рамсея, недавнем продвижении в задаче о хроматическом числе плоскости и о "самом большом математическом доказательстве".
Для других NP-задач мы обсудим несколько алгоритмов — как точных (переборных и на основе динамического программирования), так и приближенных. Довольно неожиданно разные NP-полные задачи (полиномиально эквивалентные с точки зрения точных алгоритмов) оказывается ведут себя совершенно по-разному с точки зрения приближенных.
Курс не требует от слушателей специальной подготовки.
Материалы
Organization Committee e-mail:
dubna@mccme.ru