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

  1. Длинная арифметика. Классические алгоритмы сложения, вычитания, умножения и возведения в степень длинных чисел.
  2. Длинная арифметика. Классический алгоритм деления длинных чисел.
  3. Быстрое умножение длинных чисел: алгоритм Карацубы и его сложность.
  4. Полниомы, коэффициентное и интерполяционное представление полиномов. Операции над полиномами. Дискретное преобразование Фурье.
  5. Алгоритм быстрого преобразования Фурье. Прямое и обратное БПФ. Использование БПФ для перемножения полиномов.
  6. Динамическое программирование. Перекрытие подзадач, построение оптимального решения. Применение динамического программирования для решения задачи о расписании работы конвейера.
  7. Динамическое программирование. Перекрытие подзадач, построение оптимального решения. Применение динамического программирования для решения задачи о перемножении цепочки матриц.
  8. Динамическое программирование. Перекрытие подзадач, построение оптимального решения. Задача о максимальном совпадении двух строк и поиске самой длинной общей подпоследовательности. Расстояние Левенштейна.
  9. Жадные алгоритмы, связь с динамическим программированием. Свойство жадного выбора и элементы жадной стратегии. Решение задачи о выборе процессов.
  10. Жадные алгоритмы. Свойство жадного выбора и элементы жадной стратегии. Понятие о префиксных кодах, коды Хаффмана, их построение. Корректность алгоритма Хаффмана.
  11. Жадные алгоритмы. Поиск максимальной возрастающей подпоследовательности.
  12. Жадные алгоритмы. Сведение задачи о максимальной совпадающей подпоследовательности к задаче о максимальной возрастающей подпоследовательности. Максимальная совпадающая подпоследовательность более чем для двух строк.
  13. Базовые понятия теории вероятностей. Наивный байесовский классификатор.
  14. Коды Хаффмана. Неоднозначность кодов Хаффмана. Адаптивные коды Хаффмана.
  15. Канонические коды Хаффмана. Эффективное кодирование и декодирование с использованием канонических кодов Хаффмана.
  16. Канонические коды Хаффмана. Быстрое вычисление длин кодов Хаффмана.
  17. Арифметическое кодирование. Реализация с использование чисел фиксированной точности.
  18. Символьные модели сжатия текстов. Преобразование Барроуза-Уиллера. Использование преобразования Барроуза-Уиллера для сжатия текстов, связь с суффиксными деревьями. Кодирование методом Move-To-Front.
  19. Символьные модели сжатия текстов. Предсказание по частичному совпадению, различные варианты метода.
  20. Словарные методы сжатия. Алгоритм LZ77. Реализация LZ77 в программе gzip.
  21. Словарные методы сжатия. Алгоритм LZ77. Реализация LZ77 с использованием суффиксных деревьев.
  22. Суффиксные деревья. Алгоритм Укконена. Использование суффиксных связей и прыжка по счетчику. Ускорение с O(n^3) до O(n^2).
  23. Суффиксные деревья. Алгоритм Укконена. Сжатие дуговых меток, ускорение до O(n). Доказательство линейности работы.