Алгоритмы и структуры данных, часть 2
Санкт-Петербург, весна 2017
Описание
Продолжение изучения базовых алгоритмов, продолжение курса Алгоритмы и структуры данных 1
.
Узнаем
- Деревья поиска
- Алгоритмы на подвешенных деревьях
- Алгоритмы на строках
- Паросочетания, потоки
- что-нибудь еще
Критерии оценки по курсу
Всего в курсе будет 5 домашних заданий, в задании \(i\) есть \(a_i\) обязательных задач. Пусть вы решили \(p_i\) задач в \(i\)-ом задании, тогда ваша оценка будет равна \(S = \lceil\sum_{i=1}^5 \frac{p_i}{a_i}\rceil\).
Преподаватели
Список лекций
- Дерево поиска, основные операции
- АВЛ-дерево
- Декартово дерево (Treap)
- Персистентные деревья
- Дерево поиска по неявному ключу. Rope
- Примеры других сбалансированных деревьев
- Splay-дерево. Статическая оптимальность, динамическая оптимальность
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)]
Heavy-Light декомпозиция
- Поиск минимума на пути в дереве
- Статическая задача: двоичные подъемы
- Тяжелые и легкие ребра
- Разбиение на тяжелые пути
- Оценка \(log(n)\) на число легких ребер
- Финальная оценка \(log^2(n)\)
Link-Cut деревья
- Операции link и cut
- Использование деревьев по неявному ключу
- Амортизированная оценка \(log^2(n)\)
- Использование splay-деревьев для улучшения времени до \(log(n)\)
- Prefix функция
- Z функция
- Полиномиальный хеш.
- Бор. Использование для хранения множества строк
- Суффиксные ссылки.
- Поиск множества строк с помощью бора и суффиксных ссылок
- Алгоритм Ахо-Корасик, связь с КМП
Суффиксный массив. Определение, свойства, применение.
Построение суффиксного массива за \(O(n \log n)\)
LCP за \(O(n)\). Алгоритм Касаи.
Лемма о дополняющем пути
Алгоритм Куна
Теорема Кёнига, поиск минимального вершинного покрытия
Связь: вершинное покрытие, независимое множество, клика
Лемма Холла, существование совершенного паросочетания в регулярном двудольном графе
- Определения. Форд-Фалкерсон. Теорема и алгоритм
- Поиск минимального разреза
- Декомпозиция (поиск k непересекающихся путей в орграфе)
- Эдмондс-Карп и существования максимального потока
- Масштабирование потока
Игры на ацикличных графах
Ретроанализ
Функция гранди, сумма игр