Алгоритмы и структуры данных, часть 2
Санкт-Петербург, весна 2015
Описание
Общая информация по курсу
Правила и дедлайны сдачи курса
Codereview:
- распределение задач
- условия
- Если вас нет в распределении задач, пишите на Burunduk30@gmail.com
Преподаватели
Список лекций
Задачи поиска ближайшего общего предка (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)$ дополнением символов в конец строки
- Оптимизация размера дерева с помощью сжатия путей
- Переход по суффиксной ссылке в сжатом дереве
- Автоматическое продление листов
- Итоговая линейная оценка
Паросочетания
- Паросочетание. Определение
- Паросочетание в двудольном графе
- Теорема о дополняющем пути
- Поиск дополняющего пути
- Алгоритм Куна
- Нахождение минимального вершинного покрытия
- Нахождение минимального реберного покрытия
Потоки
- Поток
- Разрез, лемма о потоке через разрез
- Дополняющая сеть, дополняющий путь
- Алгоритм Форда-Фалкерсона, реализация с помощью поиска в глубину
- Алоритм Эдмондса-Карпа
Потоки минимальной стоимости
- Стоимость потока
- Теорема о дополняющем пути минимального веса
- Построение потока с помощью Форда-Беллмана
- Потенциалы Джонсона
Дополнительно: * Алгоритм Диница
Игры на графах
- Игры на графах. Выигрышные, проигрышные, ничейные позиции
- Ациклические графы
- Графы с циклами. Ретроспективный анализ
- Сумма игр
- Функция Гранди