Экзаменационная программа по дискретному анализу (осенний семестр 2013/14 уч. год)

  1. Недостижимость линейной оценки времени для алгоритмов сортировок, основанных на сравнениях элементов.
  2. Сортировки за линейное время. Сортировка посдчётом.
  3. Сортировки за линейное время. Поразрядная сортировка.
  4. Сортировки за линейное время. Карманная сортировка.
  5. Деревья поиска. Сбалансированные деревья. АВЛ-деревья. Вставка нового узла в АВЛ-дерево.
  6. Деревья поиска. Сбалансированные деревья. АВЛ-деревья. Удаление узла из АВЛ-дерева.
  7. Деревья поиска. Сбалансированные деревья. Красно-черные деревья. Вставка нового узла в красно-черное дерево.
  8. Деревья поиска. Сбалансированные деревья. Красно-черные деревья. Удаление узла из красно-черного дерева.
  9. Сильноветвящиеся деревья, B-деревья. Вставка элемента в B-дерево.
  10. Сильноветвящиеся деревья, B-деревья. Удаление элемента из B-дерева.
  11. Рандомизированные деревья поиска. Декартовы деревья. Вставка нового узла в декартово дерево.
  12. Рандомизированные деревья поиска. Декартовы деревья. Удаление узла из декартова дерева.
  13. Дерево ключей. Дерево PATRICIA. Вставка нового элемента в дерево PATRICIA.
  14. Дерево ключей. Дерево PATRICIA. Удаление элемента из дерева PATRICIA.
  15. Поиск образца в строке. Основной алгоритм предварительной обработки образца. Использование Z-блоков для поиска образца в строке.
  16. Алгоритм Кнута-Мориса-Пратта. Построение функций sp и sp' на основе Z-блоков. Вариант алгоритма Кнута-Мориса-Пратта реального времени.
  17. Алгоритм Кнута-Мориса-Пратта. Построение функций sp и sp' «классическим» способом.
  18. Множественный поиск образцов в строке. Алгоритм Ахо-Корасик.
  19. Построение связей неудач для дерева ключей. Поиск в строке образца с мета-символами («джокерами»).
  20. Алгоритм Бойера-Мура. Правило плохого символа, расширенное правило плохого символа. Предварительная обработка образца с использованием Z-блоков. Реализация алгоритма Бойера-Мура.
  21. Алгоритм Апостолико-Джанкарло с линейной оценкой времени.
  22. Суффиксные деревья. Наивный алгоритм построения суффиксного дерева. Примеры использования суффиксных деревьев.
  23. Обобщенное суффиксное дерево для набора строк. Трудности использования суффиксных деревьев для алфавитов большой размерности.
  24. Суффиксные деревья. Приложения суффиксных деревьев: поиск образца в строке, множественный поиск образцов в строке.
  25. Суффиксные деревья. Приложения суффиксных деревьев: Решение задачи о наибольшей общей подстроке для двух строк; для большого количества строк; линеариазация циклической строки.
  26. Суффиксные массивы. Бинарный поиск образца в суффиксном массиве. Уменьшение времени поиска до O(n + logm).
  27. Суффиксные массивы. Алгоритм построения за O(n logn) без использования суффиксных деревьев.