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

Преподаватели