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