Бакалавриат
2024/2025
Комбинаторная оптимизация
Статус:
Курс по выбору (Прикладная математика и информатика)
Направление:
01.03.02. Прикладная математика и информатика
Кто читает:
Базовая кафедра Яндекс
Где читается:
Факультет компьютерных наук
Когда читается:
3-й курс, 3, 4 модуль
Формат изучения:
без онлайн-курса
Охват аудитории:
для своего кампуса
Преподаватели:
Ферник Тома Клеман
Язык:
русский
Кредиты:
6
Программа дисциплины
Аннотация
В рамках курса будут изучены различные задачи дискретной оптимизации (например, задача о рюкзаке, поиск паросочетаний в двудольных графах, в том числе взвешенных и пр.), также будут изучены основные техники решения NP-трудных комбинаторных задач, такие как метод ветвей и границ, метод программирования с ограничениями, методы локального поиска. Кроме того, будет изучены понятия линейных и целочисленных программ и вытекающие отсюда способы решения задач дискретной оптимизации
Цель освоения дисциплины
- Целями освоения дисциплины является получение студента основ дискретной оптимизации, освоение методов формулирования задач в виде задачи дискретной оптимизации, а также освоение базовых методов и инструментов для эффективного решения таких задач
Планируемые результаты обучения
- Знать и уметь применять методы решения линейных программ.
- Знать приемы, применяемые для решения следующих задач: задача о рюкзаке, поиск взвешенных паросочетаний в двудольном графе, задача покрытия множества, цикруляции минимальной стоимости в графах.
- Применять прямо-двойственный метод.
- Применять различные инструменты для решения задач дискретной оптимизации.
- Строить линейные программа и двойственные к ним.
- Уметь формулировать оптимизационные задачи в виде задач дискретной оптимизации.
- Формулировать задачи в виде задач программирования с ограничениями и уметь применять инструменты для решения таких задач.
Содержание учебной дисциплины
- Метод ветвей и границ для решения задач комбинарторной оптимизации.
- Задача о рюкзаке
- Программирование с ограничения
- Линейное программирование
- Поиск кратчайших путей с помощью прямо-двойственного метода
- Задача о взвешенных паросочетаниях в двудольных графах. Её решение с помощью прямо-двойственного метода.
- Метод эллипсоидов для решения задач линейного программирования. Метод отсекающих плоскостей.
- Локальный поиск, примеры его использования в разных задачах. Различные стратегии поиска (метод отжига и пр.).
- Задача о цикле минимальной средней стоимости. Алгоритм Карпа
- Циркуляции минимальной стоимости. Остаточные сети. Проталкивание вдоль циклов минимальной средней стоимости. Сильно полиномиальный алгоритм.
Промежуточная аттестация
- 2024/2025 4th module0.15 * Проект 1 + 0.15 * Проект 1 + 0.15 * Проект 2 + 0.15 * Проект 2 + 0.2 * Экзамен + 0.2 * Экзамен
Список литературы
Рекомендуемая основная литература
- Седжвик, Р. Алгоритмы на С++ : учебное пособие / Р. Седжвик. — 2-е изд. — Москва : ИНТУИТ, 2016. — 1772 с. — Текст : электронный // Лань : электронно-библиотечная система. — URL: https://e.lanbook.com/book/100565 (дата обращения: 00.00.0000). — Режим доступа: для авториз. пользователей.
Рекомендуемая дополнительная литература
- Дискретная оптимизация. Модели, методы, алгоритмы решения прикладных задач: Учебное пособие / Струченков В.И. - М.:СОЛОН-Пр., 2016. - 192 с.: ISBN 978-5-91359-181-4