Алексей Владыкин

Вопросы к экзамену (весенний семестр)

  1. Вектор, стек, очередь, дек. Применение и способы реализации.

  2. Очередь с приоритетом. Применение и способы реализации.

  3. Хеширование. Хеш-функции. Фильтр Блума. Контроль целостности данных.

  4. Множество и отображение. Применение и реализация на основе хеш-таблиц.

  5. Деревья. Разновидности, свойства, способы записи.

  6. Деревья. Обход, представление в программе. Деревья поиска.

  7. Самобалансирующиеся деревья. АВЛ-дерево.

  8. Самобалансирующиеся деревья. Красно-чёрное дерево.

  9. Самобалансирующиеся деревья. B-дерево.

  10. Динамическое программирование. Задача о наибольшей общей подпоследовательности. Задача о редакционном расстоянии.

  11. Динамическое программирование. Целочисленная задача о рюкзаке. Задача о перемножении набора матриц.

  12. Динамическое программирование. Задача о триангуляции выпуклого многоугольника. Задача о замощении площадки костяшками домино.

  13. Графы. Определения. Свойства. Представление в программе.

  14. Обход графа. Топологическая сортировка.

  15. Кратчайшие пути в графе. Алгоритм Дейкстры.

  16. Кратчайшие пути в графе. Алгоритм Беллмана-Форда.

  17. Кратчайшие пути в графе. Алгоритм Флойда-Уоршелла.

  18. Минимальное остовное дерево графа. Теорема о разрезе. Алгоритм Прима. Алгоритм Крускала.

  19. Системы непересекающихся множеств. Применение и способы реализации.

  20. Кодирование и сжатие данных. Алфавитное кодирование. Префиксный код. Код Хаффмена.

  21. Алгоритмы семейства LZ: LZ77, LZ78, LZW, DEFLATE.

  22. Преобразование Барроуза-Уилера. Использование для сжатия данных.