Не рассматривается (пересечение с курсами и т.п.)

Графы и структуры данных

1. Графы: определения и примеры. Упорядоченный граф
2. Представления графов: матрица инциденций, матрица смежности, список пар, структура смежности (списки инцидентности)

Остовные деревья

1. Задача о связности графа и остовный лес
2. Минимальное остовное дерево. Теорема “о минимальном ребре”:
   • Жадный алгоритм (Краскал)
   • Алгоритм “ближайшего соседа” (Ярник, Прим, Дейкстра)
   • Алгоритм Борувки (О(m*log n))

Задачи связности

1. Связные компоненты
2. Алгоритм нахождения сильно связных компонент (Косарайю)

Потоки в графах

1. Алгоритм Форда-Фалкерсона
2. Алгоритм Гольдберга (проталкивания предпотока)

Кратчайшие пути. Дейкстра

1. Кратчайшие пути от фиксированной вершины
2. Случай неотрицательных весов: алгоритм Дейкстры
3. Алгоритм Флойда-Уоршелла вычисления расстояний между всеми парами вершин, одновременное построение путей

Паросочетания

1. Понятия вершинных и рёберных покрытий
2. Теорема Галлаи
3. Алгоритм Куна поиска паросочетания в двудольном графе

Клики

1. Полные подграфы, клики
2. Применения и сложность задачи построения клик графа
3. Алгоритм нахождения клик на основе поиска с возвращением.

Алгоритм Рабина-Карпа

1. Идея использования хешей для решения задачи точного поиска образца в строке
2. Полиномиальные хеши для строк
3. Алгоритм быстрого вычисления всех хешей текста длины образца
4. Алгоритм Рабина-Карпа

Задачи выполнимости

1. Локальный поиск
2. Метод расщепления
3. Сведения