Алгоритмы и структуры данных

Адрианов Н.М., Иванов А.Б.

В весеннем семестре 2023 г. занятия по спецкурсу начнутся 11 февраля.

Когда: суббота, 15:00

Где: ауд.802 2УК

Канал в telegram для организационных вопросов: https://t.me/+4_rmZcjFj8YzZjAy

Программа

Литература

Спецкурс «Алгоритмы и структуры данных» - годовой по выбору кафедры. Можно сдать в виде двух полугодовых: «Введение в алгоритмы и структуры данных» и «Алгоритмы и структуры данных: дополнительные главы».

Теория алгоритмов и структур данных является необходимой составляющей багажа современного разработчика программного обеспечения. Из практики программирования возникли интересные математические задачи, при решении которых используются методы дискретной математики, алгебры и теории вероятностей. Несмотря на большой интерес к теории алгоритмов, бурное развитие и большое количество публикаций, многие проблемы остаются открытыми до сих пор. В курсе излагаются методы построения алгоритмов: «разделяй и властвуй», жадные алгоритмы, динамическое и линейное программирование. Рассматриваются методы сортировки, хеширования и поиска, методы решения задач на графах, планирования, обработки текста, сжатия данных и NP-задач. В курсе будут предложены практические задания по реализации и использованию эффективных алгоритмов и структур данных.

Программа
  1. Сложность алгоритмов, бинарный поиск, сортировка выбором и вставками
  2. Сортировка слиянием. Основная теорема для метода «разделяй и властвуй».
  3. Алгоритм Карацубы умножения чисел, алгоритм Штрассена умножения матриц. Быстрое преобразование Фурье.
  4. Оценка снизу количества сравнений при сортировке, быстрая сортировка Хоара, сложность в среднем и в худшем. Задача Дейкстры о голландском флаге, 3х-частное разбиение, эвристики выбора опорного элемента.
  5. Алгоритмы нахождения k-й порядковой статистики - вероятностный и детерминированный. Метод сортировки TimSort.
  6. Абстрактные типы данных, интерфейс и реализация, стек и очередь - реализация связанным списком и массивом.
  7. Ассоциативные массивы, бинарные деревья поиска.
  8. Сбалансированные деревья, 2-3 и красно-черные деревья.
  9. B-деревья, геометрические приложения бинарных деревьев поиска.
  10. Хеш-таблицы, реализация методом цепочек и открытой адресацией.
  11. Распределенные хеш-таблицы. Фильтр Блума.
  12. Графы, способы представления в программе. Поиск в глубину и поиск в ширину.
  13. Топологическая сортировка. Алгоритм Косарайю поиска сильносвязанных компонент.
  14. Очередь с приоритетами, реализация с помощью бинарной кучи. Пирамидальная сортировка. Алгоритм Дейкстры.
  15. Минимальные остовные деревья. Алгоритмы Прима и Крускала.
  16. Система непересекающихся множеств, (union-find), примитивная реализация, версия со взвешиванием и сокращением путей.
  17. Жадные алгоритмы. Задача о расписании, задача о кэшировании, выбор непересекающихся интервалов. Оптимальные беспрефиксные коды, алгоритм Хаффмана.
  18. Задача о рюкзаке. Задача о покрытии множествами. Оценка точности решения, получаемого с помощью жадного алгоритма.
  19. Поиск кратчайших путей в графе из одной вершины. Алгоритм Дейкстры. Алгоритм Беллмана-Форда.
  20. Поиск кратчайших путей в графе из всех вершин. Алгоритм Флойда. Алгоритм избавления от ребер отрицательной длины.
  21. Динамическое программирование. Задача о максимальном независимом множестве в деревьях. Задача о наибольшей возрастающей последовательности. Расстояние редактирования и алгоритм Левенштейна.
  22. Алгоритм динамического программирования в задаче о рюкзаке и задаче коммивояжёра. Задача о произведении матриц. Оптимальные бинарные деревья поиска. Динамика по профилю.
  23. Максимальное паросочетание. Алгоритм Форда-Фалкерсона. Алгоритм Куна.
  24. Потоки в сетях. Теорема Форда-Фалкерсона. Алгоритм Эдмондса-Карпа.
  25. Поразрядная сортировка. Сортировка строк. Tries.
  26. Конечные автоматы. Регулярные выражения.
  27. Поиск подстроки. Алгоритм Кнута-Морриса-Пратта. Алгоритм Ахо-Корасика. Алгоритм Бойера-Мура.
  28. Суффиксные массивы и суффиксные деревья.
  29. Линейное программирование. Стандартная форма. Двойственность. Симплекс-метод. Эвристики выбора входящей переменной.
  30. Приложения линейного программирования. Траспортная задача, задача о паросочетании.
  31. Целочисленное линейное программирование. Метод ветвей и границ. Метод отсечений. Сведение комбинаторных задач к задачам целочисленного линейного программирования.
  32. Классы P и NP. Сведение задач. NP-полнота. 3-SAT, поиск гамильтонова пути, задача коммивояжёра, задача о рюкзаке, минимальное вершинное покрытие, уравнения в нулях и единицах.
  33. Доказательство NP-полноты задач SAT, 3-SAT, о трехдольном сочетании, уравнений в нулях и единицах, о рюкзаке, целочисленного линейного программирования, о гамильтоновом цикле, коммивояжёра.
  34. Приближенные методы решения NP-полных задач. Полиномиальный алгоритм решения задачи о рюкзаке с точностью (1-ε). Метод локального поиска при решении NP-задач.
Литература
Веб-ресурсы
Материалы лекций 2023/2024
Материалы лекций
Задачи