Разработка и анализ алгоритмов

Лекции.

01. Введение. Сложность программ. Абстракции. Амортизационный анализ.

02. Предподсчёт. Рекурсия. Автоматы. Два указателя.

03. Сортировка. Квадратичные, субквадратичные и логарифмические сортировки. Задача разбиения.

04. Сортировка. Сортирующие сети. Сортировка чётно-нечётным слиянием Бэтчера. Сортировка подсчётом. radix-sort. Внешняя сортировка.

05. Поиск. Простой, с сужением области, распределяющий. Жадные алгоритмы. Матроиды. Алгоритм Радо-Эдмондса. Алгоритм Хаффмена.

06. Бинарная куча. Приоритетная очередь. Heap-sort.

07. Слияние бинарных куч. Биномиальная куча. Левацкая куча.

08. Хеширование. Хеш-функции и их применение. Дедупликация. Фильтр Блума. Алгоритм Карпа-Рабина.

09. Хеш-таблицы. Закрытая и открытая адресации. Рехаширование. Cuckoo-хеширование. Хеш-таблицы и деревья. Хеш-таблицы во внешней памяти.

10. Списки с пропусками. Бинарные деревья поиска. Виды вставок. Вращение. Рандомизированные деревья поиска. Декартовы деревья.

11. Слияние деревьев. Деревья по неявному ключу. Splay-деревья. AVL-деревья. B-деревья.

12. 2-3-4 деревья. Красно-чёрные деревья. Дерево отрезков. Операции снизу-вверх.

13. Дерево отрезков. Операции сверху-вниз. Двоичный спуск. Отложенные операции. Поиск в поддиапазоне на отрезке. Персистентное дерево отрезков. Задача RMQ. Разреженные таблицы.

14. Деревья Фенвика. Многомерные варианты. Обратное дерево Фенвика. Фенвик Фенвиков. Частичное каскадирование.