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

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

1 и 8 мая 2021 г., в связи с праздниками, занятий по спецкурсу не будет. Следующее занятие - 15 мая.

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

Где: 802 2 Уч. корпус занятия по спецкурсу проходят дистанционно через Zoom.

Ссылка на конференцию ZOOM: https://us04web.zoom.us/j/5099893290?pwd=VnJBUE4xdDBnMU5jWUIvcFowVEliQT09 пароль 1XYQyb

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

Экзамен 29 мая https://forms.gle/xCAQcmuJ8BWX422x8

Программа

Литература


Теория алгоритмов и структур данных является необходимой составляющей багажа современного разработчика программного обеспечения. Из практики программирования возникли интересные математические задачи, при решении которых используются методы дискретной математики, алгебры и теории вероятностей. Несмотря на большой интерес к теории алгоритмов, бурное развитие и большое количество публикаций, многие проблемы остаются открытыми до сих пор. В курсе излагаются методы построения алгоритмов: «разделяй и властвуй», жадные алгоритмы, динамическое и линейное программирование. Рассматриваются методы сортировки, хеширования и поиска, методы решения задач на графах, планирования, обработки текста, сжатия данных и 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-задач.
Литература
  • Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн «Алгоритмы. Построение и анализ», Вильямс, 2013
  • Р. Седжвик, К. Уэйн «Алгоритмы на Java», Вильямс, 2012
  • С. Дасгупта, Х. Пападимитриу, У. Вазирани «Алгоритмы», МЦНМО, 2014
Веб-ресурсы
Материалы лекций
  • Лекция 1. Сложность алгоритмов, бинарный поиск, сортировка выбором и вставками, сортировка слиянием.
  • Лекция 2. Сортировки. Оценка снизу сложности сортировки, использующей сравнения. QuickSort. Задача о голландском флаге и 3-частное разбиение. Timsort.
  • Лекция 3. Абстрактные структуры данных. Реализация стека списком и массивом изменяемого размера. Ассоциативные массивы. Бинарные деревья поиска.
  • Лекция 4. 2-3 деревья. Черно-красные деревья. Геометрические приложения.
  • Лекция 5. Хеш-таблицы. Распределенные хеш-таблицы.
  • Лекция 6. Графы. Поиск в глубину и поиск в ширину. Топологическая сортировка. Сильносвязанные компоненты в ориентированном графе. Алгоритм Косарайю.
  • Лекция 9. Алгоритм Дейкстры. Очередь с приоритетами. Реализация с помощью бинарной кучи. Алгоритм A*.
  • Лекция 10. Минимальные покрывающие деревья. Алгоритм Прима. Алгоритм Крускала. Система непересекающихся множеств.
  • Лекция 11. Жадные алгоритмы. Задачи о расписании, кэшировании, непересекающихся интервалов. Безпрефиксные коды и алгоритм Хаффмана. Задача о рюкзаке. Задача о покрытии множества.
  • Лекция 12. Динамическое программирование. Задача о максимальном независимом множестве в графе. Задача о наибольшей возрастающей подпоследовательности. Расстояние редактирования и алгоритм Левенштейна. Задача о рюкзаке. Задача коммивояжёра. Оптимальное умножение матриц. Оптимальные бинарные деревья поиска. Динамика по профилю.
  • Лекция 13. Кратчайшие пути. Алгоритм Беллмана-Форда. Алгоритм Флойда. Потоки в сетях. Теорема Форда-Фалкерсона. Алгоритм Эдмондса-Карпа. Максимальное паросочетание.
  • Лекция 14. Линейное программирование. Симплекс метод.
  • Лекция 15. Целочисленное линейное программирование. Метод ветвей и границ. Метод отсечений.
  • Лекция 16. NP-полные задачи.
  • Лекция 17. Методы решения NP-полных задач.
Задачи