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

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

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

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

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

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

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

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

Программа

Сложность алгоритмов, бинарный поиск, сортировка выбором и вставками
Сортировка слиянием. Основная теорема для метода «разделяй и властвуй».
Алгоритм Карацубы умножения чисел, алгоритм Штрассена умножения матриц. Быстрое преобразование Фурье.
Оценка снизу количества сравнений при сортировке, быстрая сортировка Хоара, сложность в среднем и в худшем. Задача Дейкстры о голландском флаге, 3х-частное разбиение, эвристики выбора опорного элемента.
Алгоритмы нахождения k-й порядковой статистики - вероятностный и детерминированный. Метод сортировки TimSort.
Абстрактные типы данных, интерфейс и реализация, стек и очередь - реализация связанным списком и массивом.
Ассоциативные массивы, бинарные деревья поиска.
Сбалансированные деревья, 2-3 и красно-черные деревья.
B-деревья, геометрические приложения бинарных деревьев поиска.
Хеш-таблицы, реализация методом цепочек и открытой адресацией.
Распределенные хеш-таблицы. Фильтр Блума.
Графы, способы представления в программе. Поиск в глубину и поиск в ширину.
Топологическая сортировка. Алгоритм Косарайю поиска сильносвязанных компонент.
Очередь с приоритетами, реализация с помощью бинарной кучи. Пирамидальная сортировка. Алгоритм Дейкстры.
Минимальные остовные деревья. Алгоритмы Прима и Крускала.
Система непересекающихся множеств, (union-find), примитивная реализация, версия со взвешиванием и сокращением путей.
Жадные алгоритмы. Задача о расписании, задача о кэшировании, выбор непересекающихся интервалов. Оптимальные беспрефиксные коды, алгоритм Хаффмана.
Задача о рюкзаке. Задача о покрытии множествами. Оценка точности решения, получаемого с помощью жадного алгоритма.
Поиск кратчайших путей в графе из одной вершины. Алгоритм Дейкстры. Алгоритм Беллмана-Форда.
Поиск кратчайших путей в графе из всех вершин. Алгоритм Флойда. Алгоритм избавления от ребер отрицательной длины.
Динамическое программирование. Задача о максимальном независимом множестве в деревьях. Задача о наибольшей возрастающей последовательности. Расстояние редактирования и алгоритм Левенштейна.
Алгоритм динамического программирования в задаче о рюкзаке и задаче коммивояжёра. Задача о произведении матриц. Оптимальные бинарные деревья поиска. Динамика по профилю.
Максимальное паросочетание. Алгоритм Форда-Фалкерсона. Алгоритм Куна.
Потоки в сетях. Теорема Форда-Фалкерсона. Алгоритм Эдмондса-Карпа.
Поразрядная сортировка. Сортировка строк. Tries.
Конечные автоматы. Регулярные выражения.
Поиск подстроки. Алгоритм Кнута-Морриса-Пратта. Алгоритм Ахо-Корасика. Алгоритм Бойера-Мура.
Суффиксные массивы и суффиксные деревья.
Линейное программирование. Стандартная форма. Двойственность. Симплекс-метод. Эвристики выбора входящей переменной.
Приложения линейного программирования. Траспортная задача, задача о паросочетании.
Целочисленное линейное программирование. Метод ветвей и границ. Метод отсечений. Сведение комбинаторных задач к задачам целочисленного линейного программирования.
Классы P и NP. Сведение задач. NP-полнота. 3-SAT, поиск гамильтонова пути, задача коммивояжёра, задача о рюкзаке, минимальное вершинное покрытие, уравнения в нулях и единицах.
Доказательство NP-полноты задач SAT, 3-SAT, о трехдольном сочетании, уравнений в нулях и единицах, о рюкзаке, целочисленного линейного программирования, о гамильтоновом цикле, коммивояжёра.
Приближенные методы решения NP-полных задач. Полиномиальный алгоритм решения задачи о рюкзаке с точностью (1-ε). Метод локального поиска при решении NP-задач.

Литература

Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн «Алгоритмы. Построение и анализ», Вильямс, 2013
Р. Седжвик, К. Уэйн «Алгоритмы на Java», Вильямс, 2012
С. Дасгупта, Х. Пападимитриу, У. Вазирани «Алгоритмы», МЦНМО, 2014

Веб-ресурсы

http://neerc.ifmo.ru/wiki
http://e-maxx.ru/
http://algolist.manual.ru/
https://algs4.cs.princeton.edu/ - сайт с дополнительными материалами к книге Седжвика-Уэйна
https://alexanderskulikov.github.io/files/algorithms_href.pdf - черновой вариант русского перевода книги Дасгупта-Пападимитриу-Вазирани (свободно распространяется).
https://alexanderskulikov.github.io/ - страница Александра Куликова (кроме перевода предыдущей книги на ней ссылки на другие книги и курсы на coursera/edX/Stepic).

Материалы лекций 2023/2024

Лекция 1 Сложность алгоритмов, бинарный поиск.
Лекция 2 Алгоритмы сортировки. Оценка снизу сложности сортировки, использующей сравнения. QuickSort.
Лекция 3 QuickSort. QuickSelect. BFPRT. Поразрядная сортировка.
Лекция 4 Разделяй и властвуй.
Лекция 5 Абстрактные структуры данных. Ассоциативный массив. Двоичные деревья поиска.
Лекция 6 Удаление в двоичных деревьях поиска. 2-3 деревья. Черно-красные деревья.
Лекция 7 AVL деревья. Порядковые операции в деревьях поиска. Геометрические приложения.
Лекция 8 B-деревья. Хеш-таблицы.
Лекция 9 Хеш-таблицы. Распределенные хэш-таблицы. Фильтр Блума. HAMT.
Лекция 10 Графы
Лекция 11 Графы. BFS. Алгоритм Дейкстры. Двоичная куча.
Лекция 12 Графы. DFS. Топологическая сортировка. Компоненты сильной связности.
Лекция 13 Timsort.
Лекция 14 Минимальные остовные деревья. Алгоритмы Прима, Крускала. Система непересекающихся множеств.
Лекция 15 Жадные алгоритмы. Алгоритм Хаффмана.
Лекция 16 Жадные алгоритмы. Динамическое программирование.
Лекция 17 Динамическое программирование (продолжение).
Лекция 18 Еще раз про кратчайшие пути в графах.
Лекция 19 Потоки в сетях.
Лекция 20 Потоки в сетях, продолжение. Приложения.
Лекция 21 Линейное программирование.
Лекция 22 Алгоритмы поиска подстроки.

Материалы лекций

Лекция 1. Сложность алгоритмов, бинарный поиск, сортировка выбором и вставками, сортировка слиянием.
Лекция 2. Сортировки. Оценка снизу сложности сортировки, использующей сравнения. QuickSort. Задача о голландском флаге и 3-частное разбиение.
Лекция 2б. Timsort.
Лекция 3. Абстрактные структуры данных. Реализация стека списком и массивом изменяемого размера. Ассоциативные массивы. Бинарные деревья поиска.
Лекция 4. 2-3 деревья. Черно-красные деревья. Геометрические приложения.
Лекция 5. Хеш-таблицы. Распределенные хеш-таблицы.
Лекция 6. Графы. Поиск в глубину и поиск в ширину. Топологическая сортировка. Сильносвязанные компоненты в ориентированном графе. Алгоритм Косарайю.
Лекция 9. Алгоритм Дейкстры. Очередь с приоритетами. Реализация с помощью бинарной кучи. Алгоритм A*.
Лекция 10. Минимальные покрывающие деревья. Алгоритм Прима. Алгоритм Крускала. Система непересекающихся множеств.
Лекция 11. Жадные алгоритмы. Задачи о расписании, кэшировании, непересекающихся интервалов. Безпрефиксные коды и алгоритм Хаффмана. Задача о рюкзаке. Задача о покрытии множества.
Лекция 12. Динамическое программирование. Задача о максимальном независимом множестве в графе. Задача о наибольшей возрастающей подпоследовательности. Расстояние редактирования и алгоритм Левенштейна. Задача о рюкзаке. Задача коммивояжёра. Оптимальное умножение матриц. Оптимальные бинарные деревья поиска. Динамика по профилю.
Лекция 13. Кратчайшие пути. Алгоритм Беллмана-Форда. Алгоритм Флойда. Потоки в сетях. Теорема Форда-Фалкерсона. Алгоритм Эдмондса-Карпа. Максимальное паросочетание.
Лекция 14. Линейное программирование. Симплекс метод.
Лекция 15. Целочисленное линейное программирование. Метод ветвей и границ. Метод отсечений.
Лекция 16. NP-полные задачи.
Лекция 17. Методы решения NP-полных задач.