Дополнительные главы алгоритмов, часть 1
Санкт-Петербург, весна 2013
Описание
Часть 1. Продвинутые структуры данных
- Приоритетные очереди, сливаемые кучи, фибоначчиевы кучи, тонкие кучи, кучи Бродала-Окасаки
- Cплей-деревья, оптимальность, обобщенная модель BST, нижние границы на число операций, AS-множества, TANGO-деревья
- Cтруктуры для позиционирования точек на плоскости. Деревья отрезков, многомерные деревья отрезков. Использование персистентного ДО совместно со сканирующей прямой
- Идеальное хеширование
- Хранение целочисленных данных, деревья Ван Эмде Боаса
- Fusion Trees
Часть 2. Комбинаторная оптимизация
- Задача о максимальном потоке
- Продвинутые алгоритмы решения задачи о максимальном потоке
- Задача о глобальном разрезе
- Задача о потоке минимальной стоимости
- Алгоритм отмены циклов отрицательного веса (сильно полиномиальный алгоритм для задачи о потоке минимальной стоимости)
Отчетность
- Практическая работа по структурам данных
- Теоретическое домашнее задание по структурам данных
- Практическое задание по алгоритмам комбинаторной оптимизации
Преподаватели
Список лекций
Приоритетные очереди
Приоритетные очереди
- Двоичная куча
- Левосторонняя куча (leftist heap), [Wikipedia]
- Биномиальная куча
- Куча Фибоначчи
- Тонкая куча [Thin heaps, Thick heaps]
- Куча Бродала-Окасаки [Optimal Purely Functional Priority Queues]
Деревья поиска
- Splay-деревья [Self Adjusting BST], [Wikipedia]
- Амортиризированная оценка O(log W/w(x)) на splay
- Оптимальное статическое дерево поиска, построение с помощью ДП
- Статическая оптимальность splay-деревьев
- Оптимальность splay-деревьев относительно локальных запросов
- Геометрическое представление работы с BST, Arborally-satisfied sets
- TANGO-деревья [Dynamic Optimality—Almost], [Wikipedia]
Деревья поиска (продолжение)
- Дерево Ван-Эмде-Боаса [Википедия]
- Цифровой бор
- X-fast trie [Википедия]
- Y-fast trie [Википедия]
- Fusion tree [Википедия]
См также [Лекции 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.