Видеотека
RUS  ENG    ЖУРНАЛЫ   ПЕРСОНАЛИИ   ОРГАНИЗАЦИИ   КОНФЕРЕНЦИИ   СЕМИНАРЫ   ВИДЕОТЕКА   ПАКЕТ AMSBIB  
Видеотека
Архив
Популярное видео

Поиск
RSS
Новые поступления






Летняя школа «Современная математика» имени Виталия Арнольда, 2018
22 июля 2018 г. 15:30–16:45, г. Дубна, Московская область, г. Дубна, дом отдыха «Ратмино»
 


NP-полные задачи, занятие 1

Н. М. Адрианов
Видеозаписи:
MP4 944.6 Mb
MP4 2,080.4 Mb

Количество просмотров:
Эта страница:539
Видеофайлы:211

Н. М. Адрианов



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

Website: https://www.mccme.ru/dubna/2018/courses/adrianov.html
Цикл лекций
 
  Обратная связь:
 Пользовательское соглашение  Регистрация посетителей портала  Логотипы © Математический институт им. В. А. Стеклова РАН, 2024