Алгоритмы дискретной оптимизации (ЕНС)
Адрианов Н.М., Иванов А.Б.
(весенний семестр)
В весеннем семестре 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
- Лекция 1 Введение.
- Лекция 2 Машины Тьюринга. Классы P и NP.
- Лекция 3 NP-полнота. Теорема Кука-Левина.
Первоапрельская статья М.Гарднера, png с картой и файл с описанием графа