Цели и задачи дисциплины
Цель дисциплины: ознакомление с основными понятиями дискретной оптимизации.
Задачи дисциплины:
• формирование представлений о теории сложности вычислений;
• развитие способности понимать, совершенствовать и применять современный математический аппарат;
• овладение методами решения задач дискретной оптимизации, развитие понимания условий их применения.
Краткое содержание дисциплины
Минимаксные теоремы
Теоремы Форда – Фалкерсона, Холла, Кенига – Эгервари, Дилворта.
Задача о назначениях и другие задачи о двудольных графах
Нахождение наибольшего паросочетания и наименьшего вершинного покрытия в двудольном графе. Венгерский алгоритм. Задача о назначениях на узкое место.
Матроиды. Жадный алгоритм
Определения и примеры. Двойственность. Представимые матроиды. Ранговая функция. Жадный алгоритм. Задача планирования эксперимента. Общие трансверсали.
Сложность задач
Задача выбора. Варианты задачи оптимизации. Классы P NP. Полиномиальная сводимость. NP-полные задачи. Структура класса NP.
Приближенные алгоритмы
Определения. Приближённый алгоритм Кристофидеса решения метрической задачи коммивояжёра.