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

Лекции.

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

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

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

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

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

06. Приоритетная очередь. Бинарная куча. Пирамидальная сортировка.

07. Биномиальные кучи. Левацкие кучи.

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

09. Хеш-таблицы – прямая, закрытая, открытая. Cuckoo hash. Хеш-таблицы во внешней памяти.

10. Структура данных SkipList. Деревья. Обход деревьев. Деревья поиска. Рандомизированные деревья. Декартовы деревья.

11. Деревья. Операции split и merge. Деревья по неявному ключу. Splay-деревья. AVL-деревья. B-деревья.

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

13. Деревья отрезков. Ленивые обновления. Деревья отрезков с указателями. Персистентные деревья отрезков. Разреженные таблицы.

14. Деревья Фенвика – прямое, многомерное, обратное. Фенвик Фенвиков. Частичное каскадирование.

Контесты.

Структуры данных на Си

Базовые алгоритмы и структуры данных.

Сортировка и поиск

Поисковые структуры – хеш-таблицы и деревья поиска.

Специальные деревья – Декартово, отрезков, Фенвика. Sparse table, fractional cascading.

Задачи для решения на семинарах.

Семинары

Исходные коды программ для семинаров.