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

О курсе

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

Пререквизиты Необходимо владеть языком C++ на уровне, достаточном для решения задач уровня регионального и заключительного этапа РОИ, а также знать алгоритмы на уровне параллели В кружков Яндекса/Т-Образования.

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

Неделя	Лекции/семинары
1	Введение. Понятие эффективности алгоритма: общеизвестные подходы, “парадокс Merge Sort”; формальные определения: O-нотация (O-, \Theta-, \Omega-). Решение асимптотических уравнений. Мастер-теорема.
2	Амортизационный анализ: вариации: “в среднем”; метод бухгалтерского учета; метод потенциалов. Примеры амортизированных структур данных и анализа их эффективности. очередь на двух стеках; вектор. Персистентность как пример ситуации, когда амортизация не работает. Персистентная очередь на “шести” стеках.
3	Сортировки: квадратичные сортировки: вставками, выбором, пузырьком; сортировка в различных моделях. Нижняя оценка в модели камушков. Дерево решений; сортировка слиянием как пример оптимальной сортировки; алгоритм слияния двух отсортированных массивов за линейное время с использованием O(1) дополнительной памяти;
4	Сортировки: Сортировка кучей: двоичная куча: внутреннее устройство, методы SiftUp, SiftDown, Insert, GetMin, ExtractMin, Delete; построение кучи из n элементов за O(n); сортировка кучей. Оценки времени и памяти. быстрая сортировка: общая реализация; различные способы выбора pivot-а: детерминированные, случайный; поиск К-ой порядковой статистики. Алгоритм Флойда - Блюма - Пратта - Ривеста - Тарьяна.
5	Сортировки: основы RAM-модели, целочисленных алгоритмов. Kirkpatrick sort; “линейные” сортировки: сортировка подсчетом; поразрядная сортировка: MSD, LSD; сортировка строк.
6	Сортировки: TimSort (сортировка Тима Петерса). Оценка времени работы; внешняя сортировка. Устройство жёсткого диска. Метод k-путевого слияния;
7	Сливаемые кучи, их методы, оценки эффективности: биномиальная: левацкая; косая; Фибоначчи;
8	Сливаемые кучи, их методы, оценки эффективности: Soft Heap: точный инвариант; примеры использования: К-я порядковая статистика за O(n), near-sort за O(n log 1/eps); внутреннее устройство, доказательство инварианта, оценка времени работы методов. Целочисленные алгоритмы и структуры данных: Atomic Heap: сведение к Q-heap.
9	Сбалансированные двоичные деревья поиска: понятие двоичного дерева поиска, “”базовая” реализация методов Search, Insert, Erase; методы балансировки: “Честные”: АВЛ-дерево, красно-черное дерево, B-дерево. Сравнение по времени (“константе”), по памяти; Амортизированный: Splay-tree: Асимптотика в терминах произвольно заданных положительных весов вершин
10	Сбалансированные двоичные деревья поиска: методы балансировки: Вероятностный: декартово дерево: Построение дерева по заданным n отсортированным ключам и приоритетам за O(n); Двоичные деревья “по неявному ключу” для всех вышеперечисленных деревьев: операции Split/Merge; вставка/удаление элемента по позиции, циклический сдвиг; технология отложенных операций: присваивание/прибавление на подотрезке, разворот подотрезка.
11	Задачи RSQ/RMQ и их аналоги для различных функций: static RSQ: префиксные суммы; static RMQ: разреженная таблица; Disjoint sparse table для неидемпотентных функций; Метод четырех русских: алгоритм Фарах-Колтона и Бендера асимптотически оптимального решение задач static RMQ и static LCA. решение задачи static RMQ без сведения к static LCA.
12	Задачи RSQ/RMQ и их аналоги для различных функций: изменение в точке: дерево отрезков: “тупые” решения, возможность их применения; применение SQRT-декомпозиции; SQRT-декомпозиция с k слоями; дерево отрезков как предельная версия SQRT-декомпозиции; операции “снизу” в дереве отрезков; дерево Фенвика: классическая версия для коммутативной ассоциативной обратимой операции; встречное дерево Фенвика для НЕкоммутативной НЕассоциативной операции; прибавление на отрезке для дерева Фенвика; применения: “Фенвик Фенвиков”, “казахский Фенвик”.
13	Задачи RSQ/RMQ и их аналоги для различных функций: Многомерные RSQ/RMQ: многомерные Static RSQ/RMQ; Изменение в точке для многомерных RSQ/RMQ; технология прибавлений на подпараллелепипеде для многомерных RSQ на базе дерева Фенвика или дерева отрезков с операцией снизу; kD-дерево, присваивание на подпараллелепипеде;
14	Задачи RSQ/RMQ и их аналоги для различных функций: Технология отложенных операций в дереве отрезков с операциями “сверху”: классические применения: присваивание/прибавление на отрезке; отложенное создание вершин: динамическое дерево отрезков; сливаемые деревья отрезков: задача о сортировке на подотрезках; Segment Tree Beats: %= C на отрезке, сумма на отрезке, изменение в точке; min= на отрезке, сумма на отрезке, изменение в точке. Усложения: присваивание на отрезке, прибавление на отрезке. прибавление на отрезке, исторический максимум в точке; изменение в точке, сумма максимумов на префиксах на подотрезке;
15	Алгоритмы и структуры данных на деревьях: структура дерева: понятие диаметра, центра, центроида. Единственность центра. Поиск диаметра, центра, центроидов; Задача об изоморфизме деревьев, ее решение за O(n log n) без использования хэшей;
16	Алгоритмы и структуры данных на деревьях: Задача Level Ancestor Queries: метод двоичных подъемов для задачи LCA и LAQ; альтернативные методы решения LAQ: longest path decomposition; ladder decomposition; их комбинация за O(n log n)/O(1); Метод четырех русских: решение задачи LAQ за O(n)/O(1).
17	Алгоритмы и структуры данных на деревьях: Центроидная декомпозиция: задачи о поиске пути длины k во взвешенном дереве с помощью центроидной декомпозиции и с помощью “переливайки”. решение задачи о “присваивании в радиусе” на взвешенном дереве.
18	Алгоритмы и структуры данных на деревьях: Задача RSQ/RMQ с массовыми операциями на дереве: Heavy-light decomposition: классическая версия с деревом отрезков за O(log^2); различные реализации; ускорение до O(log n): “честного” времени: балансировка по весу поддеревьев; “амортизированного”: splay-дерево Link-cut tree: добавление операции изменения структуры дерева, его корня: общая структура, O(log^2 n) на операцию с использованием произвольного дерева поиска; Достижение O(log n) с использованием splay-дерева.

Критерии оценивание и формы контроля успеваемости

Домашние задания в формате задач трёх типов:

1. Теоретические: нужно решить математическую задачу / доказать какой-то факт по теме.

1. Практические: нужно придумать и реализовать на языке C++ алгоритм, решающий определённую задачу и укладывающийся в ограничения по времени и памяти.

Домашних работ обычно 5–7, каждая из которых, кроме последней, рассчитана на одну, полторы или две недели.