Дополнительные главы алгоритмов
Санкт-Петербург / весна 2013, посмотреть все семестры

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

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

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

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

Отчетность

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