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

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

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

Задачи поиска ближайшего общего предка (LCA) и минимума на отрезке (RMQ)
  • Задачи на поддеревьях
    • Дерево. Поддеревья, листья, отношение предок-потомок, корень
    • Эйлеров обход дерева. Время входа и выхода
    • Двоичные подъемы
    • Задачи LCA и LA
  • Задача RMQ
    • Формулировка, варианты решения. Разреженные таблицы
  • Алгоритм Фарах-Колтона и Бендера
    • Сведение LCA к RMQ+-1
    • Решения RMQ+-1 за O(1) с предпосчетом за O(N)
  • Сведение RMQ к LCA
Задача поиска предка на уровне (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)
  • Микро-макро эвристика

http://courses.csail.mit.edu/6.851/spring14/scribe/lec15.pdf

Heavy-Light декомпозиция
  • Поиск минимума на пути в дереве
  • Статическая задача: двоичные подъемы
  • Тяжелые и легкие ребра
  • Разбиение на тяжелые пути
  • Оценка \(log(n)\) на число легких ребер
  • Финальная оценка \(log^2(n)\)
  • Off-topic: амортизационный анализ
    • амортизационное время. определение
    • метод потенциалов
    • метод предоплаты
Строки. Поиск подстрок
  • Строки. Основные определения.
  • Хеширование строк с помощью полиномиальных хешей
  • Алгоритм Рабина--Карпа
  • Префикс-функция и КМП
  • Алгоритм Бойера--Мура
  • Z-функция
Строки: бор и Ахо-Корасик
  • Бор. Использование для хранения множества строк
  • Суффиксные ссылки.
  • Поиск множества строк с помощью бора и суффиксных ссылок
  • Алгоритм Ахо-Корасик, связь с КМП
Строки: суффиксный массив
  • Суффиксное дерево. Определение. Примеры использования.
  • Суффиксный массив. Построение с помощью сортировки.
  • Ускорение сортировки с помощью хешей.
  • Алгоритм построения за O(N log N)
  • Алгоритм Касаи
  • Примеры использования.
    • нахождение подстроки
    • нахождение наибольшего общего префикса
    • подсчет числа различных подстрок
    • нахождение наибольшей общей подстроки
Строки: суффиксное дерево, алгоритм Укконена
  • Суффиксное дерево. Основные свойства
  • Итеративный алгоритм построения за \(O(N^2)\) дополнением символов в конец строки
  • Оптимизация размера дерева с помощью сжатия путей
  • Переход по суффиксной ссылке в сжатом дереве
  • Автоматическое продление листов
  • Итоговая линейная оценка
Паросочетания
  • Паросочетание. Определение
  • Паросочетание в двудольном графе
  • Теорема о дополняющем пути
  • Поиск дополняющего пути
  • Алгоритм Куна
  • Нахождение минимального вершинного покрытия
  • Нахождение минимального реберного покрытия
Потоки
  • Поток
  • Разрез, лемма о потоке через разрез
  • Дополняющая сеть, дополняющий путь
  • Алгоритм Форда-Фалкерсона, реализация с помощью поиска в глубину
  • Алоритм Эдмондса-Карпа
Потоки минимальной стоимости
  • Стоимость потока
  • Теорема о дополняющем пути минимального веса
  • Построение потока с помощью Форда-Беллмана
  • Потенциалы Джонсона

Дополнительно: * Алгоритм Диница

Игры на графах
  • Игры на графах. Выигрышные, проигрышные, ничейные позиции
  • Ациклические графы
  • Графы с циклами. Ретроспективный анализ
  • Сумма игр
  • Функция Гранди