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