Алгоритмы и структуры данных, часть 2

Санкт-Петербург, весна 2016

Описание

Будем продолжать изучать базовые алгоритмы.

Узнаем

  • метод динамического программирования,
  • алгоритмы на строках (z-функция, КМП, Ахо-Корасик, суффиксное дерево, суффиксный массив, неточный поиск), * сбалансированные деревья (АВЛ, сплей, декартово),
  • задачи RMQ и LCA,
  • быстрое преобразование Фурье,
  • теорию NP-полноты.

Преподаватели

Список лекций

Деревья поиска (BST)
  • AVL-Tree (вставка, удаление, Th: на добавление не более одного вращения)

  • Treap (Split, Merge, оценка средней глубины)

  • Персистентность (определение, описание того, как дерево можно сделать персистентным)

Деревья поиска (BST) - 2
  • Неявный ключ (implicit key)

  • RB-Tree (а так же B-Tree, 2-3-Tree, AA-Tree)

  • Splay-Tree (док-во времени, теорема о статической оптимальность, примеры)

RMQ, LCA
  • 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, Heavy-Light декомпозиция

Задача поиска предка на уровне (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)$
Строки. Начало.
  1. Prefix функция

  2. Z функция

  3. Полиномиальный хеш.

Строки: бор и Ахо-Корасик
  • Бор. Использование для хранения множества строк
  • Суффиксные ссылки.
  • Поиск множества строк с помощью бора и суффиксных ссылок
  • Алгоритм Ахо-Корасик, связь с КМП
Суффиксный массив
  • Суфф массив за $O(n \log n)$

  • LCP за $O(n)$. Алгоритм Касаи.

Суффиксное дерево
  • Дерево палиндромов

  • Суффиксное дерево: Маккрейт и Укконен!

Паросочетания
  • Лемма о дополняющем пути

  • Алгоритм Куна

  • Теорема Кёнига, поиск минимального вершинного покрытия

  • Связь: вершинное покрытие, независимое множество, клика

  • Лемма Холла, существование совершенного паросочетания в регулярном двудольном графе

Потоки
  • Определения. Форд-Фалкерсон. Теорема и алгоритм.
  • Поиск min разреза.
  • Декомпозиция (поиск k непересекающихся путей в орграфе)
  • Эдмондс-Карп и существования max потока (не следует из ФФ!)
  • Scaling (Масштабирование потока)
Mincost потоки
  • Mincost flow через Форд-Беллмана

  • Mincost flow через Дейкстру

  • Mincost flow через отрицательные циклы (алгоритм Клейна)

Игры на графах
  • Игры на ацикличных графах

  • Ретроанализ

  • Функция гранди, сумма игр

Фурье

Быстрое дискретное преобразование Фурье и умножение длинных чисел