Дополнительные главы алгоритмов
Курс Хит
Часть 1. Продвинутые структуры данных
- Приоритетные очереди, сливаемые кучи, фибоначчиевы кучи, тонкие кучи, кучи Бродала-Окасаки
- Cплей-деревья, оптимальность, обобщенная модель BST, нижние границы на число операций, AS-множества, TANGO-деревья
- Cтруктуры для позиционирования точек на плоскости. Деревья отрезков, многомерные деревья отрезков. Использование персистентного ДО совместно со сканирующей прямой
- Идеальное хеширование
- Хранение целочисленных данных, деревья Ван Эмде Боаса
- Fusion Trees
Часть 2. Комбинаторная оптимизация
- Задача о максимальном потоке
- Продвинутые алгоритмы решения задачи о максимальном потоке
- Задача о глобальном разрезе
- Задача о потоке минимальной стоимости
- Алгоритм отмены циклов отрицательного веса (сильно полиномиальный алгоритм для задачи о потоке минимальной стоимости)
Отчетность
- Практическая работа по структурам данных
- Теоретическое домашнее задание по структурам данных
- Практическое задание по алгоритмам комбинаторной оптимизации
Страница курса на сайте Computer Science Center
Лекции курса
14