====== Алгоритмы дискретной оптимизации (ЕНС) ======
=== Адрианов Н.М., Иванов А.Б. ===

(весенний семестр)

**В весеннем семестре 2023 г. занятия по спецкурсу начнутся 11 февраля.**

**Когда**: суббота, 16:50

**Где**: **ауд.802 2й ГУМ**

Канал в telegram для организационных вопросов: [[https://t.me/+4_rmZcjFj8YzZjAy]]

**Темы спецкурса**

1. Линейное программирование. Двойственность в линейном программировании. Симплекс-метод.

2. Целочисленное линейное программирование. Метод ветвей и границ. Метод Гомори. Применение ILP-солверов для решения комбинаторных задач.

3. NP-задачи - задачи поиска и задачи оптимизации. Сведение и NP-полные задачи. NP-полнота задачи SAT.

4. Алгоритмы SAT-солверов (DPLL, CDCL). Применение SAT-солверов для решения промышленных и математических задач.

5. Доказательство NP-полноты разных задач (клика, вершинное покрытие, раскраска графа, 3-дольное сочетание, ILP, рюкзак, коммивояжер, ...).

6. Приближенные методы решения NP-полных задач. Сведение к ILP, релаксация и округление. Рандомизированное округление. Результаты о границах приближенных алгоритмов для разных задач.

7. Эвристические алгоритмы: локальный поиск и генетические алгоритмы.

8. Компьютер играет в шахматы, го, ... AlphaZero: Monte-Carlo Tree Search и обучение с подкреплением. Применение идей AlphaZero в задаче раскраски графа.

----

== Материалы лекций 2024 ==
  * {{:algo:discrete2024:01_intro.pdf | Лекция 1}} Введение.
  * {{ :algo:discrete2024:02_turing_machines.pdf | Лекция 2}} Машины Тьюринга. Классы P и NP.
  * {{ :algo:discrete2024:03_cook_theorem.pdf | Лекция 3}} NP-полнота. Теорема Кука-Левина.

----

{{ :algo:disc_opt.pdf | Задания по темам спецкурса }}

{{ :algo:colors.zip | Первоапрельская статья М.Гарднера, png с картой и файл с описанием графа }}

{{ :algo:karp_1972.pdf | Статья Карпа про 21 NP-полную задачу }}