Алгоритмы и структуры данных III. Продвинутый поток 2026

О курсе

Программа курса с 2025 года, в течении сентября будут изменения

Курс посвящён изучению продвинутых алгоритмов и структур данных для решения сложных задач на графах, строках, геометрии и комбинаторных структурах. Основное внимание уделяется не только знанию алгоритмов, но и пониманию их математических основ, доказательству корректности и оценке вычислительной сложности.

В курсе рассматриваются алгоритмы максимального потока и минимальной стоимости, задачи о паросочетаниях и разрезах, современные алгоритмы обработки строк, вычислительная геометрия, вероятностные алгоритмы, а также быстрые алгоритмы для графовых задач. Отдельное внимание уделяется построению алгоритмов с оптимальными или близкими к оптимальным оценками времени работы.

Программа курса

форма контроля: экзамен

№	Тема
1	Потоки в сетях. Определение сети и потока. Величина потока и разрезы. Остаточная сеть и дополняющие пути. Теорема и метод Форда–Фалкерсона. Поиск минимального разреза.
2	Алгоритмы максимального потока. Алгоритмы Эдмондса–Карпа и Диница. Слоистые сети и блокирующие потоки. Масштабирование потоков. Единичные сети. Теоремы Карзанова.
3	Предпотоки и потоки минимальной стоимости. Метод проталкивания предпотока, операции Push и Relabel, функция Discharge, алгоритм «поднять-в-начало». Минимальная циркуляция и максимальный поток минимальной стоимости. Метод Клейна. Потенциалы Джонсона.
4	Паросочетания, пути и разрезы. Максимальное паросочетание и алгоритм Куна. Сведение паросочетания к задаче о потоке. Алгоритм Хопкрофта–Карпа. Теоремы Данилюка, Менгера, Уитни, Кёнига и Дилворта. Максимальное паросочетание минимального веса и венгерский алгоритм.
5	Минимальные разрезы и плотные подграфы. Глобальный минимальный разрез. Алгоритм Штор–Вагнера. Дерево Гомори–Ху и его построение. Задача о подграфе максимальной плотности.
6	Основы алгоритмов обработки строк. Префикс-функция и алгоритм Кнута–Морриса–Пратта. Z-функция и её применения. Алгоритм Манакера. Поиск подстроки за линейное время. Алгоритм Галила–Сейфераса и декомпозиция строки.
7	Боры и алгоритмы поиска множества строк. Структура данных «бор». Способы хранения детей. Суффиксные ссылки и их построение. Алгоритм Ахо–Корасик. Сжатые суффиксные ссылки. Дерево палиндромов и линейный алгоритм его построения.
8	Суффиксные структуры. Суффиксный массив и его построение. Алгоритм Арикавы–Аримуры–Касаи–Ли–Парка. Суффиксные деревья и сжатые суффиксные деревья. Алгоритм Укконена. Суффиксный автомат, правые контексты, классы эквивалентности подстрок и линейное построение.
9	Основы вычислительной геометрии. Точки, прямые и отрезки. Векторы и скалярное и векторное произведения. Ориентация и коллинеарность. Пересечение прямых, отрезков, окружности и прямой. Ориентированная площадь многоугольника и площадь пересечения многоугольника и круга.
10	Выпуклая геометрия. Проверка принадлежности точки многоугольнику. Работа с выпуклыми многоугольниками. Касательные. Выпуклая оболочка: алгоритмы Джарвиса, Грэхема, Эндрю, Киркпатрика и Чена. Пара ближайших точек. Минимальный периметр треугольника. Диаметр множества точек.
11	Операции над выпуклыми объектами и геометрические структуры. Сумма Минковского. Пересечение и расстояние между выпуклыми многоугольниками. Минимальные охватывающие прямоугольники. Задачи о движении робота и препятствиях. Сканирующая прямая. Площадь объединения прямоугольников. Пересечение полуплоскостей.
12	Вероятностные алгоритмы. Случайный QuickSort и поиск порядковой статистики. Анализ среднего и худшего времени работы. Вероятностная оценка игровых деревьев. Алгоритм Каргера для поиска минимального разреза. Алгоритм Каргера–Штайна.
13	Вероятностные и быстрые алгоритмы на графах. Алгоритмы поиска минимального остовного дерева: Борувка и Каргер–Клейн–Тарьян. Средние и худшие оценки времени работы. Задачи APD и APSP. Быстрое булево умножение матриц и алгоритмы на его основе.
14	Дополнительные структуры и алгоритмы. Полиномиальные хэши строк и алгоритм Рабина–Карпа. Дерандомизация: метод условных вероятностей и малых пространств событий. Персистентные структуры данных. Онлайн-обработка геометрических задач. KD-деревья и статический поиск точек в прямоугольниках.
15	Продвинутая вычислительная геометрия и оптимизация. Поиск граней связного плоского графа. Диаграмма Вороного и её построение. Триангуляция Делоне и её свойства. Выпуклая оболочка в 3D. Convex Hull Trick и дерево Ли–Чао. Тернарный поиск и его применения.

Материалы курса

программа экзамена