Дополнительные главы алгоритмов, часть 1

Санкт-Петербург, весна 2013

Описание

Часть 1. Продвинутые структуры данных

  • Приоритетные очереди, сливаемые кучи, фибоначчиевы кучи, тонкие кучи, кучи Бродала-Окасаки
  • Cплей-деревья, оптимальность, обобщенная модель BST, нижние границы на число операций, AS-множества, TANGO-деревья
  • Cтруктуры для позиционирования точек на плоскости. Деревья отрезков, многомерные деревья отрезков. Использование персистентного ДО совместно со сканирующей прямой
  • Идеальное хеширование
  • Хранение целочисленных данных, деревья Ван Эмде Боаса
  • Fusion Trees

Часть 2. Комбинаторная оптимизация

  • Задача о максимальном потоке
  • Продвинутые алгоритмы решения задачи о максимальном потоке
  • Задача о глобальном разрезе
  • Задача о потоке минимальной стоимости
  • Алгоритм отмены циклов отрицательного веса (сильно полиномиальный алгоритм для задачи о потоке минимальной стоимости)

Отчетность

  • Практическая работа по структурам данных
  • Теоретическое домашнее задание по структурам данных
  • Практическое задание по алгоритмам комбинаторной оптимизации

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

Список лекций

Приоритетные очереди

Приоритетные очереди

Деревья поиска
  • Splay-деревья [Self Adjusting BST], [Wikipedia]
  • Амортиризированная оценка O(log W/w(x)) на splay
  • Оптимальное статическое дерево поиска, построение с помощью ДП
  • Статическая оптимальность splay-деревьев
  • Оптимальность splay-деревьев относительно локальных запросов
  • Геометрическое представление работы с BST, Arborally-satisfied sets
  • TANGO-деревья [Dynamic Optimality—Almost], [Wikipedia]
Деревья поиска (продолжение)

См также [Лекции MIT]

Персистентные структуры данных
  • Персистентные структуры данных, уровни персистентности
  • Использование персистентности для перехода от offline-задачи к online-задаче
  • Частичная персистентность, методы Fat Node, Path Copying, Node Copying [Википедия]
  • Список с поддержкой запроса о порядке [Two Simplified Algorithms for Maintaining Order in a List]
  • Полная персистентность с помощью Node Copying и List Order Maintanence
  • Персистентный дек
  • Сливаемый персистентный стекью [Simple Confluently Persistent Catenable Lists]
Запросы в многомерных прямоугольниках
  • Одномерный случай. Решение двоичным поиском.
  • Дерево отрезков.
  • Двумерное дерево отрезков. Сжатое двумерное дерево отрезков.
  • Многомерное дерево отрезков.
  • Решение двумерной задачи с помощью персистентного дерево отрезков.
  • Запрос в сжатом двумерном дереве отрезков за O(log n) с помощью дополнительных ссылок вниз.
  • Fractional Cascading. Двоичный поиск одновременно в k списках.
  • Динамическая задача. Использование BB-alpha деревьев.
  • Поиск списка точек в параллелепипеде в 3D.

Рекомендованный материал: лекции MIT, лекции 3 и 4.