О курсе
Курс посвящён изучению алгоритмов и структур данных, а также стоящих за ними теоретически-математических основ и способов их эффективной реализации на языке 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-дерева.
|
Критерии оценивание и формы контроля успеваемости
Домашние задания в формате задач трёх типов:
- Теоретические: нужно решить математическую задачу / доказать какой-то факт по теме.
- Практические: нужно придумать и реализовать на языке C++ алгоритм, решающий определённую задачу и укладывающийся в ограничения по времени и памяти.
Домашних работ обычно 5–7, каждая из которых, кроме последней, рассчитана на одну, полторы или две недели.