Дискретная математика и теория графов

Цели и задачи дисциплины
Цель дисциплины: ознакомление с основными понятиями дискретной оптимизации. Задачи дисциплины: формирование представлений о теории сложности вычислений; развитие способности понимать, совершенствовать и применять современный математический аппарат; овладение методами решения задач дискретной оптимизации, развитие понимания условий их применения.
Краткое содержание дисциплины
Минимаксные теоремы Теоремы Форда – Фалкерсона, Холла, Кенига – Эгервари, Дилворта. Задача о назначениях и другие задачи о двудольных графах. Нахождение наибольшего паросочетания и наименьшего вершинного покрытия в двудольном графе. Венгерский алгоритм. Задача о назначениях на узкое место. Матроиды. Жадный алгоритм Определения и примеры. Двойственность. Представимые матроиды. Ранговая функция. Жадный алгоритм. Задача планирования эксперимента. Общие трансверсали. Сложность задач Задача выбора. Варианты задачи оптимизации. Классы P NP. Полиномиальная сводимость. NP-полные задачи. Структура класса NP. Приближенные алгоритмы Определения. Приближённый алгоритм Кристофидеса решения метрической задачи коммивояжёра.
Компетенции обучающегося, формируемые в результате освоения дисциплины
Выпускник должен обладать:
  • ОПК-1 Способен консультировать и использовать фундаментальные знания в области математического анализа, комплексного и функционального анализа алгебры, аналитической геометрии, дифференциальной геометрии и топологии, дифференциальных уравнений, дискретной математики и математической логики, теории вероятностей, математической статистики и случайных процессов, численных методов, теоретической механики в профессиональной деятельности
You are reporting a typo in the following text:
Simply click the "Send typo report" button to complete the report. You can also include a comment.