====== Алгоритмы и структуры данных ====== === Адрианов Н.М., Иванов А.Б. === **В весеннем семестре 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 == * {{:algo:2023:01_complexity.pdf|Лекция 1}} Сложность алгоритмов, бинарный поиск. * {{:algo:2023:02_sort_1.pdf|Лекция 2}} Алгоритмы сортировки. Оценка снизу сложности сортировки, использующей сравнения. QuickSort. * {{:algo:2023:03_sort_2.pdf|Лекция 3}} QuickSort. QuickSelect. BFPRT. Поразрядная сортировка. * {{:algo:2023:04_divide_and_conquer.pdf|Лекция 4}} Разделяй и властвуй. * {{:algo:2023:05_adt_maps.pdf|Лекция 5}} Абстрактные структуры данных. Ассоциативный массив. Двоичные деревья поиска. * {{:algo:2023:06_red_black_trees.pdf|Лекция 6}} Удаление в двоичных деревьях поиска. 2-3 деревья. Черно-красные деревья. * {{:algo:2023:07_red_black_trees_2.pdf|Лекция 7}} AVL деревья. Порядковые операции в деревьях поиска. Геометрические приложения. * {{:algo:2023:08_hash_tables.pdf|Лекция 8}} B-деревья. Хеш-таблицы. * {{:algo:2023:09_hash_tables_2.pdf|Лекция 9}} Хеш-таблицы. Распределенные хэш-таблицы. Фильтр Блума. HAMT. * {{ :algo:2023:10_graphs.pdf |Лекция 10}} Графы * {{ :algo:2023:11_graphs_dijkstra.pdf |Лекция 11}} Графы. BFS. Алгоритм Дейкстры. Двоичная куча. * {{ :algo:2023:12_graphs_topological.pdf |Лекция 12}} Графы. DFS. Топологическая сортировка. Компоненты сильной связности. * {{ :algo:2023:13_timsort.pdf |Лекция 13}} Timsort. * {{ :algo:2023:14_graphs_mst.pdf | Лекция 14}} Минимальные остовные деревья. Алгоритмы Прима, Крускала. Система непересекающихся множеств. * {{ :algo:2023:15_greedy.pdf | Лекция 15}} Жадные алгоритмы. Алгоритм Хаффмана. * {{ :algo:2023:16_greedy_dynamic.pdf | Лекция 16}} Жадные алгоритмы. Динамическое программирование. * {{ :algo:2023:17_dynamic_2.pdf | Лекция 17}} Динамическое программирование (продолжение). * {{ :algo:2023:18_graphs_extra.pdf | Лекция 18}} Еще раз про кратчайшие пути в графах. * {{ :algo:2023:19_maxflow.pdf | Лекция 19}} Потоки в сетях. * {{ :algo:2023:20_maxflow_2.pdf | Лекция 20}} Потоки в сетях, продолжение. Приложения. * {{ :algo:2023:21_linear_programming.pdf | Лекция 21}} Линейное программирование. * {{ :algo:2023:22_strings.pdf | Лекция 22}} Алгоритмы поиска подстроки. * {{ :algo:2023:23_np_complete.pdf | Лекция 23}} Классы P и NP. NP-полные задачи. ---- == Материалы лекций == * {{:algo:01-complexity.pdf|Лекция 1}}. Сложность алгоритмов, бинарный поиск, сортировка выбором и вставками, сортировка слиянием. * {{:algo:03-sorting.pdf|Лекция 2}}. Сортировки. Оценка снизу сложности сортировки, использующей сравнения. QuickSort. Задача о голландском флаге и 3-частное разбиение. * {{:algo:03b-timsort.pdf|Лекция 2б}}. Timsort. * {{:algo:05-binary-search-trees.pdf|Лекция 3}}. Абстрактные структуры данных. Реализация стека списком и массивом изменяемого размера. Ассоциативные массивы. Бинарные деревья поиска. * {{:algo:06-red-black-trees.pdf|Лекция 4}}. 2-3 деревья. Черно-красные деревья. Геометрические приложения. * {{:algo:hashtables.pdf|Лекция 5}}. Хеш-таблицы. Распределенные хеш-таблицы. * {{:algo:09-graphs.pdf|Лекция 6}}. Графы. Поиск в глубину и поиск в ширину. Топологическая сортировка. Сильносвязанные компоненты в ориентированном графе. Алгоритм Косарайю. * {{:algo:10-graphs-deikstra.pdf|Лекция 9}}. Алгоритм Дейкстры. Очередь с приоритетами. Реализация с помощью бинарной кучи. Алгоритм A*. * {{:algo:11-graphs-mst.pdf|Лекция 10}}. Минимальные покрывающие деревья. Алгоритм Прима. Алгоритм Крускала. Система непересекающихся множеств. * {{:algo:12-greedy.pdf|Лекция 11}}. Жадные алгоритмы. Задачи о расписании, кэшировании, непересекающихся интервалов. Безпрефиксные коды и алгоритм Хаффмана. Задача о рюкзаке. Задача о покрытии множества. * {{:algo:13-dynamic.pdf|Лекция 12}}. Динамическое программирование. Задача о максимальном независимом множестве в графе. Задача о наибольшей возрастающей подпоследовательности. Расстояние редактирования и алгоритм Левенштейна. Задача о рюкзаке. Задача коммивояжёра. Оптимальное умножение матриц. Оптимальные бинарные деревья поиска. Динамика по профилю. * {{:algo:14-graphs-extra.pdf|Лекция 13}}. Кратчайшие пути. Алгоритм Беллмана-Форда. Алгоритм Флойда. Потоки в сетях. Теорема Форда-Фалкерсона. Алгоритм Эдмондса-Карпа. Максимальное паросочетание. * {{:algo:15-linear-programming.pdf|Лекция 14}}. Линейное программирование. Симплекс метод. * {{:algo:16-integer-lp.pdf|Лекция 15}}. Целочисленное линейное программирование. Метод ветвей и границ. Метод отсечений. * {{:algo:17-np-complete.pdf|Лекция 16}}. NP-полные задачи. * {{:algo:18-np-methods.pdf|Лекция 17}}. Методы решения NP-полных задач. == Задачи == * {{:algo:algo-problems-2.pdf|Задачи по теме "Разделяй и властвуй"}} * {{:algo:algo-problems-3.pdf|Задачи по теме "Quicksort"}} * {{:algo:algo-problems-7.pdf|Задачи по теме "Геометрические приложения деревьев поиска"}} * {{:algo:09-graphs-problems.pdf|Задачи по теме "Графы"}}