Курс посвящен теории алгоритмов в общем и алгоритмам оптимизации на графах в частности.
Примерное содержание курса:
1. Простые алгоритмы и структуры данных. Асимптотическая сложность алгоритмов. Сортировка, поиск, динамическое программирование, жадные алгоритмы. Основные структуры данных: стек, очередь, список, дек. Вектор, амортизационный анализ. Очереди с приоритетами. СНМ. Деревья поиска.
2. Простые алгоритмы на графах. Основные определения и некоторые теоремы теории графов. Хранение графов в памяти. Обход графа: DFS, BFS. Топологическая сортировка. Поиск компонент сильной связности.
3. Полиномиально разрешимые задачи на графах и алгоритмы их решения. Кратчайшие пути. Минимальное остовное дерево. Максимальный поток, минимальный разрез, дерево Гомори-Ху. Поток минимальной стоимости. Сведение задач к потоковым, максимальное паросочетание.
4. NP-сложные задачи на графах. Основные определения теории сложности вычислений (языки, сводимость, классы P и NP). Vertex Cover, Set Cover, Dominating Set. TSP и методы её решения. Задача о дереве Штейнера. Приближенные алгоритмы (примеры и методы построения). Параметризованные алгоритмы (FPT, кернелизация).
5. Модели математического программирования для задач на графах. Формулировка графовых задач в виде задач целочисленного программирования. Релаксация переменных. Оценки нижних границ на значение целевой функции.
6. Формулировка оптимизационных задач в виде MAX-SAT. Состояние современных SAT-солверов. Использование MAX-SAT солверов для решения задач оптимизации.
Домашние задания: теоретические (алгоритмические) и контесты по пройденым алгоритмам.