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

Общие сведения о курсе

• Формат: очный.
• Форма контроля: дифференцированный зачет, экзамен.

• Руководитель курса: Рухович Филипп Дмитриевич.
• Лектор, семинарист: Рухович Филипп Дмитриевич.
• Учебные ассистенты: Никита Погадаев, Михаил Сазанович.

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

В рамках курса изучаются следующие темы:

• Поиск кратчайших расстояний в графе:

BFS, 1-K-BFS, 0-1-BFS, [A-2A]-BFS, алгоритм Дейкстры, обобщенный алгоритм Дейкстры;

• Работа с отрицательными ребрами: алгоритмы Флойда, Форда-Беллмана.
• Теория игр:

Понятие равноправной игры на графе, примеры игр. Понятия выигрышной, проигрышной и ничейной игр. Решение игры методом ретроанализа. Игра Ним. Эквивалентность произвольной ациклической игры игре Ним, функция Шпрага-Гранди. Сумма ациклических игр, ее функция Шпрага-Гранди. Полная классификация равноправных игр. Теорема Смита-Френкеля.

• Структура данных EVAL-LINK-UPDATE и ее применения.
• Поиск в глубину и его применения:
• Классификация ребер: ребра дерева(леса) DFS, прямые, обратные, перекрестные, их свойства для ориентированных и неориентированных графов. Простые применения: поиск компонент связности, цикла, топологической сортировки.
• Метод Тарьяна поиска мостов, точек сочленения, компонент реберной и вершинной двусвязностей в неориентированном графе. Методы Тарьяна и Косарайю поиска компонент сильной связности в ориентированном графе.
• Дерево доминаторов, быстрый алгоритм его построения с помощью структуры EVAL-LINK-UPDATE.
• Поиск минимального остова в неориентированном графе:
• Свойства: лемма о безопасном ребре, критерий минимальности остовного дерева, единственность минимального остова в предположении попарно различных весов.
• Поиск минимального остова: алгоритмы Борувки, Прима, Краскала, Фредмана-Тарьяна.
• Dynamic Connectivity Problem и его друзья: решение за O((n+q)log^2 n), за O((n+q)log n), динамический поиск мостов за O((n+q)log n).
• Быстрое преобразование Фурье (FFT):
• Определение FFT, использование FFT для быстрого умножения многочленов и длинных чисел;
• Деление многочленов по модулю x^m и с остатком; деление длинных чисел с помощью метода Ньютона;
• Использование FFT: поиск подстрок в строке с “джокером”, решение линейных рекуррент за O(s log s log n), быстрое вычисление многочлена в n точках, быстрая интерполяция многочлена;
• Многомерное преобразование Фурье; свертка Уолша-Адамара и её друзья как модификации многомерного преобразования Фурье.
• Работа со степенными рядами: логарифмирование/экспоненцирование, обращение. Принцип Теллегена.
• Динамическое программирование:
• Решение задачи о наибольшей возрастающей подпоследовательности за O(n log n) с помощью дерева отрезков и с помощью бинарного поиска;
• Алгоритм Хиршберга для восстановления ответа в задачах о поиске НОП и о рюкзаке с использованием O(W) памяти;

Задача “Total LCS”;

• Оптимизации динамического программирования: Convex Hull Trick (версия с динамической выпуклой оболочкой, с деревом Ли-Чао), оптимизация Кнута, оптимизация “разделяй-и-властвуй”.

Домашние задания

Предполагается 5-8 домашних заданий, время выполнения которых - от 1 до 2 недель. Каждое задание представляет собой набор задач одного из трех типов: Теоретическая: нужно доказать какое-то математическое утверждение по курсу лекций; проверка осуществляется вручную. Практическая: нужно придумать и реализовать на С++ алгоритм, удовлетворяющий определенным требованиям; проверка осуществляется с использованием автоматической тестирующей системы. Практическая с code review: такая же, как и практическая, но дополнительно код проверяется вручную на предмет того, удовлетворяет ли код критериям code style.

Критерии оценивания и отчетность по курсу

Оценка за дифференцированный зачет целиком базируется на решении домашних заданий. Каждая из задач стОит какое-то количество баллов. Оценка за семестр вычисляется по формуле floor(S/X), где S - это суммарное число баллов за решенные в семестре студентом задачи, а X - некоторая определяемая преподавателем величина. Экзамен же по курсу является чисто теоретическим. По результатам ответа на экзамене, студент получает оценку от 0 до 7 и может попробовать вытянуть “билет на отл” из числа самых сложных алгоритмов курса, получив за него от -2 до 3 баллов. Также за особо успешное решение ДЗ (если оценка окажется больше 8 или даже больше 10) студент может получить дополнительные баллы и на экзамене.

Материалы

• Видеолекции курса youtube.com/@lectorium_fpmi ; там же можно найти записи лекций по курсу за предыдущие годы и семестры.