Дополнительные главы алгоритмов, часть 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)

  • Общий метод построения частично персистентных структур

  • Общий метод построения полностью персистентных структур

Heaps
  • 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

Поиск на плоскости
  1. Ортогональные запросы

    • 1D статическая задача. Массив + бинпоиск.
    • 1D динамическая задача. BST.
    • 2D статическая задача за \(\log^2 n\). 2D дерево.
    • 2D статическая задача за \(\log n\). Бинпоиск + переход по ссылкам.
    • 2D динамическая задача за \(\log^2 n\). Балансировка по весу.
    • Обобщение для больших размерностей. Просто добавь деревьев.
    • 3D статическая задача за \(\log n\). Fractional cascading.
  2. Нахождение многоугольника по точке

    • Offline задача. Сканирующая прямая.
    • Online задача. Персистентное дерево.
    • Сложность по времени и памяти.
Fractional Cascading
  • Fractional Cascading
  • запросы в \(R^3\) за \(\log n\)
Вычисления и структуры данных во внешней памяти
  1. Вычисления во внешней памяти

    • Почему нужна внешняя память. Время доступа
    • Модель внешней памяти
    • Базовые алгоритмы: Scan, Sort
    • Транспонирование матрицы
    • Разворачивание списка
  2. Структуры данных

    • Стек, очередь, список
    • B-дерево
    • Буфферное дерево
    • Куча
Heaps (окончание)
  • Исправления в Pairing Heap. Доказательство \(O(\sqrt{n})\) в Pairing Heap.

  • Binomial Heap (биномиальная куча)

  • Fibonacci Heap (куча фибоначчи)

  • Radix Heap

  • MinMax Heap

Динамическая связность offline
  • Связность. Ребра только добавляются. СНМ (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\)

Задача про связность

http://www.e-olimp.com/en/problems/1881

Cache-oblivious вычисления
  • Как работает кэш. Стратегии кэширования. Идеальный кэш
  • Модель cache oblivious вычислений
  • Scan, транспонирование матрицы
  • Дерево отрезков, Van Emde Boas layout
  • Дерево поиска
Динамическая связность online
  • Есть удаления, но всегда лес. Euler Tour trees.
  • Динамическая связность на графе
Теорзачет (мы в ПОМИ, в 402!)

Можно освежить и восполнить знания по курсу.

Мы в ПОМИ, в 402!