Дополнительные главы алгоритмов

Общая информация
ЛекторП. Ю. Маврин
Семестросень 2014
Дата начала14.09.2014
Количество пар12
Язык курсарусский
Вопросы к экзамену
Видеоhttp://www.lektorium.tv/course/24388
Аннотация Лекторы: Сергей Копелиович и Павел Маврин. В рамках курса будут рассмотрены "продвинутые" алгоритмы и структуры данных, как правило, не покрываемые курсом базовых алгоритмов. Отчетность: задача по программированию, теоропрос в конце курса. Список планируемых тем, порядок может поменяться:
  1. Персистентные структуры данных
  2. Ортогональные запросы в K-мерных пространствах (дерево отрезков, fractional cascading)
  3. MST и запросы на пути дерева (min, sum на пути дерева за $ O(1) $, рандомизированный алгоритм для поиска MST за $ O(E) $)
  4. Алгоритмы без использования дополнительной памяти (rotate, $ d $-куча, minmax-куча, merge, стабильная сортировка BlockSort)
  5. Кучи (куча Фибоначчи, Leftist, Skew, Pairing, Weak, Radix, алгоритм Дейкстры за $ O(m + n\sqrt{\log C}) $)

  6. Поиск на плоскости (локализация точки в планарном графе в offline и online)
  7. Неортогональные запросы на плоскости (число точек в полуплоскости, в треугольнике в online за $ O(n^{0.44}) $, где n − число исходных точек)

  8. Вычисления и структуры данных во внешней памяти, cache-oblivious вычисления
  9. LCA, RMQ, LA
  10. Euler-Tour trees, Heavy-Light декомпозиция, Link-Cut trees, Динамическая связность графов в online
  11. Динамическая связность и 2-связность в offline; задача о поиске MST: $ \max w - \min w = \min $

  12. Потоки и разрезы (глобальный разрез за $ O(V^3) $ и $ O(V^2\log V) $, preflow push & global relabeling, поток за $ O(VE + V^2\log U) $)
  13. Графы (stable marriage problem, поток минимальной стоимости за полином, цикл минимального среднего веса, кратчайший путь за $ E\sqrt V $)
  14. Метод четырех русских (число единичных бит, умножение булевых матриц за $ O(n^3/log^2n) $, НОП за $ O(n^2/log^2n) $, построение схемы по булевой функции)
Последние три темы (потоки, графы, метод четырех русских) мы скорее всего не успеем рассмотреть за 12 пар.
Лекции Подсказка: слайды, видеозапись и другие материалы лекции доступны со страницы лекции, попасть на которую можно, нажав на её название.

1. Алгоритмы без использования дополнительной памяти (Сергей Копелиович)
(14.09.2014 - 13:00 - 14:35)

  • Сравнение разных сортировок (heap, merge, quick, introsort, insertion, selection)
  • reverse за $ O(n) $, rotate за $ O(n) $, sort за $ O(n{\log}n) $, stable sort за $ O(n^2) $.
  • inplace-merge: стабильный за $ O(n+m^{1+\varepsilon}) $, стабильный за $ O(n{\log}n) $, нестабильный за $ O(n) $
  • merge-sort: нерекурсивная версия за $ O(n{\log}n) $, inplace версия за $ O(n{\log}^2n) $
  • BlockSort: buffer extraction + sort blocks + local merges
  • Обзор структур данных без доп.памяти: heap, k-heap, min-max-heap, fenwick-tree, beap
2. Персистентные структуры данных (Павел Маврин)
(05.10.2014 - 13:00 - 14:35)

  • Pointer Machine model
  • Структуры данных. Операции на запрос (query) и изменение (update)
  • Персистентность. Частичная и полная
  • Функциональные структуры данных
  • Функциональный стек, BST
  • Общий метод для частично персистентных с дополнительным $ \log V $ на операцию
  • Частично персистентный связный список за O(1)
  • Частично персистентное дерево за O(1)
  • Общий метод построения частично персистентных структур
  • Общий метод построения полностью персистентных структур
http://www.youtube.com/watch?v=8TD_olemcwY#t=79
3. Heaps
(12.10.2014 - 13:00 - 14:35)

  • 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
  • http://www.youtube.com/watch?v=_ogNdxt8uf4
    4. Поиск на плоскости
    (19.10.2014 - 13:00 - 14:35)

    1. Ортогональные запросы
      • 1D статическая задача. Массив + бинпоиск.
      • 1D динамическая задача. BST.
      • 2D статическая задача за $ \log^2 n $. 2D дерево.
      • 2D статическая задача за $ \log n $. Бинпоиск + переход по ссылкам.
      • 2D динамическая задача за $ \log^2 n $. Балансировка по весу.
      • Обобщение для больших размерностей. Просто добавь деревьев.
      • 3D статическая задача за $ \log n $. Fractional cascading.
    2. Нахождение многоугольника по точке
      • Offline задача. Сканирующая прямая.
      • Online задача. Персистентное дерево.
      • Сложность по времени и памяти.
    http://www.youtube.com/watch?v=K8f8OeL65_E
    5. Fractional Cascading
    (09.11.2014 - 13:00 - 14:35)

    • Fractional Cascading
    • запросы в $ R^3 $ за $ \log n $
    http://www.youtube.com/watch?v=3enDEVa3JPc
    6. Вычисления и структуры данных во внешней памяти
    (23.11.2014 - 13:00 - 14:35)

    1. Вычисления во внешней памяти
    • Почему нужна внешняя память. Время доступа
    • Модель внешней памяти
    • Базовые алгоритмы: Scan, Sort
    • Транспонирование матрицы
    • Разворачивание списка
    2. Структуры данных
    • Стек, очередь, список
    • B-дерево
    • Буфферное дерево
    • Куча
    http://www.youtube.com/watch?v=Y3EEUlWacWc
    7. Heaps (окончание)
    (30.11.2014 - 12:00 - 13:35)

    • Исправления в Pairing Heap. Доказательство $ O(\sqrt{n}) $ в Pairing Heap.
    • Binomial Heap (биномиальная куча)
    • Fibonacci Heap (куча фибоначчи)
    • Radix Heap
    • MinMax Heap
    http://www.youtube.com/watch?v=2Ce8T-123y4
    8. Динамическая связность offline
    (07.12.2014 - 13:00 - 14:30)

    • Связность. Ребра только добавляются. СНМ (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 $
    https://www.youtube.com/watch?v=EQ3CiNWMgvo
    9. Cache-oblivious вычисления
    (14.12.2014 - 11:15 - 12:50)

    • Как работает кэш. Стратегии кэширования. Идеальный кэш
    • Модель cache oblivious вычислений
    • Scan, транспонирование матрицы
    • Дерево отрезков, Van Emde Boas layout
    • Дерево поиска
    https://www.youtube.com/watch?v=0hJWyHAPLoA
    10. Динамическая связность online
    (14.12.2014 - 13:00 - 14:35)

    • Есть удаления, но всегда лес. Euler Tour trees.
    • Динамическая связность на графе
    11. Теорзачет
    (20.12.2014 - 11:00 - 15:00)

    Возможность убедиться в своих знаниях, освежить их, восполнить пробелы.
    Мы в ПОМИ, в 402!
    Ваша оценка: Пусто Средняя: 4.2 (5 votes)
    Share |