Дополнительные главы алгоритмов, часть 1
Санкт-Петербург, осень 2014
Описание
В рамках курса будут рассмотрены продвинутые
алгоритмы и структуры данных, как правило, не покрываемые курсом базовых алгоритмов. Отчетность: задача по программированию, теоропрос в конце курса. Правила получения зачёта.
Список планируемых тем, порядок может поменяться:
- Персистентные структуры данных
- Ортогональные запросы в K-мерных пространствах (дерево отрезков, fractional cascading)
- MST и запросы на пути дерева (min, sum на пути дерева за \( O(1) \), рандомизированный алгоритм для поиска MST за \( O(E) \))
- Алгоритмы без использования дополнительной памяти (rotate, \( d \)-куча, minmax-куча, merge, стабильная сортировка BlockSort)
Кучи (куча Фибоначчи, Leftist, Skew, Pairing, Weak, Radix, алгоритм Дейкстры за \( O(m + n\sqrt{\log C}) \))
Поиск на плоскости (локализация точки в планарном графе в offline и online)
Неортогональные запросы на плоскости (число точек в полуплоскости, в треугольнике в online за \( O(n^{0.44}) \), где n − число исходных точек)
Вычисления и структуры данных во внешней памяти, cache-oblivious вычисления
LCA, RMQ, LA
Euler-Tour trees, Heavy-Light декомпозиция, Link-Cut trees, Динамическая связность графов в online
Динамическая связность и 2-связность в offline; задача о поиске MST: \( \max w - \min w = \min \)
Потоки и разрезы (глобальный разрез за \( O(V^3) \) и \( O(V^2\log V) \), preflow push & global relabeling, поток за \( O(VE + V^2\log U) \))
Графы (stable marriage problem, поток минимальной стоимости за полином, цикл минимального среднего веса, кратчайший путь за \( E\sqrt V \))
Метод четырех русских (число единичных бит, умножение булевых матриц за \( O(n^3/log^2n) \), НОП за \( O(n^2/log^2n) \), построение схемы по булевой функции)
Последние три темы (потоки, графы, метод четырех русских) мы скорее всего не успеем рассмотреть за 12 пар.
Преподаватели
Список лекций
Сравнение разных сортировок (heap, merge, quick, introsort, insertion, selection)
reverse за \(O(n)\), rotate за \(O(n)\), sort за \(O(nlogn)\), stable sort за \(O(n^2)\).
inplace-merge: стабильный за \(O(n+m^{1+eps})\), стабильный за \(O(nlogn)\), нестабильный за \(O(n)\)
merge-sort: нерекурсивная версия за \(O(nlogn)\), inplace версия за \(O(nlog^2n)\)
BlockSort: buffer extraction + sort blocks + local merges
Обзор структур данных без доп.памяти: heap, k-heap, min-max-heap, fenwick-tree, beap
Pointer Machine model
Структуры данных. Операции на запрос (query) и изменение (update)
Персистентность. Частичная и полная
Функциональные структуры данных
Функциональный стек, BST
Общий метод для частично персистентных с дополнительным \(\log V\) на операцию
Частично персистентный связный список за O(1)
Частично персистентное дерево за O(1)
Общий метод построения частично персистентных структур
Общий метод построения полностью персистентных структур
Leftist Heap (левацкая куча), Skew Heap (кривая куча)
Общее ускорение, bootstrapping: вставка и слияние произвольных сливаемых куч за O(1)
Pairing Heap (спаривающаяся куча). На лекции была допущена серьезная ошибка.
Правильная версия pairing(l): return merge(merge(l[0], l[1]), pairing(l[2.. ])))Weak Heap (слабая куча)
(Оставшуюся часть не успели, обсудим в следующий раз)
Binomial Heap (биномиальная куча), Fibonacci Heap (куча фибоначчи)
Radix Heap
MinMax Heap
Ортогональные запросы
- 1D статическая задача. Массив + бинпоиск.
- 1D динамическая задача. BST.
- 2D статическая задача за \(\log^2 n\). 2D дерево.
- 2D статическая задача за \(\log n\). Бинпоиск + переход по ссылкам.
- 2D динамическая задача за \(\log^2 n\). Балансировка по весу.
- Обобщение для больших размерностей. Просто добавь деревьев.
- 3D статическая задача за \(\log n\). Fractional cascading.
Нахождение многоугольника по точке
- Offline задача. Сканирующая прямая.
- Online задача. Персистентное дерево.
- Сложность по времени и памяти.
- Fractional Cascading
- запросы в \(R^3\) за \(\log n\)
Вычисления во внешней памяти
- Почему нужна внешняя память. Время доступа
- Модель внешней памяти
- Базовые алгоритмы: Scan, Sort
- Транспонирование матрицы
- Разворачивание списка
Структуры данных
- Стек, очередь, список
- B-дерево
- Буфферное дерево
- Куча
Исправления в Pairing Heap. Доказательство \(O(\sqrt{n})\) в Pairing Heap.
Binomial Heap (биномиальная куча)
Fibonacci Heap (куча фибоначчи)
Radix Heap
MinMax Heap
- Связность. Ребра только добавляются. СНМ (DSU)
- Корневая оптимизация, решение за \(O((n+k)\sqrt{n})\) в offline
- Решение для Connectivity за \(O((k+n)\log k)\) в offline
- Двухсвязность. Ребра только добавляются
- Решение для 2-Connectivity за \(O((k+n)\log k)\) в offline
- Решение задачи про MST: \(\max w - \min w \rightarrow \min\)
Задача про связность
- Как работает кэш. Стратегии кэширования. Идеальный кэш
- Модель cache oblivious вычислений
- Scan, транспонирование матрицы
- Дерево отрезков, Van Emde Boas layout
- Дерево поиска
- Есть удаления, но всегда лес. Euler Tour trees.
- Динамическая связность на графе
Можно освежить и восполнить знания по курсу.
Мы в ПОМИ, в 402!