Алгоритмы и структуры данных 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 и дерево Ли–Чао. Тернарный поиск и его применения. |