Алгоритмы и структуры данных, часть 2
Санкт-Петербург, весна 2016
Описание
Будем продолжать изучать базовые алгоритмы.
Узнаем
- метод динамического программирования,
- алгоритмы на строках (z-функция, КМП, Ахо-Корасик, суффиксное дерево, суффиксный массив, неточный поиск), * сбалансированные деревья (АВЛ, сплей, декартово),
- задачи RMQ и LCA,
- быстрое преобразование Фурье,
- теорию NP-полноты.
Преподаватели
Список лекций
AVL-Tree (вставка, удаление, Th: на добавление не более одного вращения)
Treap (Split, Merge, оценка средней глубины)
Персистентность (определение, описание того, как дерево можно сделать персистентным)
Неявный ключ (implicit key)
RB-Tree (а так же B-Tree, 2-3-Tree, AA-Tree)
Splay-Tree (док-во времени, теорема о статической оптимальность, примеры)
Sparse-Table: RMQ за [O(nlogn), O(1)], за [O(n), O(loglogn)], за [O(nloglogn), O(1)]
Двоичные подъёмы: LCA, минимум на пути
Эйлеров Обход: LCA -> RMQ, функция на поддереве
Фарах-Колтон-Бендер: LCA -> RMQ±1; RMQ и LCA за [O(n), O(1)]
Задача поиска предка на уровне (Level Ancestor Problem)
- Двоичные подъемы: O(log n) на запрос + O(N log N) предпосчет
- Лесенки: O(log n) на запрос + O(N) предпосчет
- Двоичные подъемы + Лесенки: O(1) на запрос + O(N log N) предпосчет
- Идея уменьшить число прыжковых вершин до O(N / log N)
- Микро-макро эвристика
Heavy-Light декомпозиция
- Поиск минимума на пути в дереве
- Статическая задача: двоичные подъемы
- Тяжелые и легкие ребра
- Разбиение на тяжелые пути
- Оценка \(log(n)\) на число легких ребер
- Финальная оценка \(log^2(n)\)
Prefix функция
Z функция
Полиномиальный хеш.
- Бор. Использование для хранения множества строк
- Суффиксные ссылки.
- Поиск множества строк с помощью бора и суффиксных ссылок
- Алгоритм Ахо-Корасик, связь с КМП
Суфф массив за \(O(n \log n)\)
LCP за \(O(n)\). Алгоритм Касаи.
Дерево палиндромов
Суффиксное дерево: Маккрейт и Укконен!
Лемма о дополняющем пути
Алгоритм Куна
Теорема Кёнига, поиск минимального вершинного покрытия
Связь: вершинное покрытие, независимое множество, клика
Лемма Холла, существование совершенного паросочетания в регулярном двудольном графе
- Определения. Форд-Фалкерсон. Теорема и алгоритм.
- Поиск min разреза.
- Декомпозиция (поиск k непересекающихся путей в орграфе)
- Эдмондс-Карп и существования max потока (не следует из ФФ!)
- Scaling (Масштабирование потока)
Mincost flow через Форд-Беллмана
Mincost flow через Дейкстру
Mincost flow через отрицательные циклы (алгоритм Клейна)
Игры на ацикличных графах
Ретроанализ
Функция гранди, сумма игр
Быстрое дискретное преобразование Фурье и умножение длинных чисел