Алгоритмы и структуры данных: дополнительные главы
Иванов А.Б.
Когда: суббота, 15:00
Где: 1403 ГЗ МГУ
Канал в Telegram для организационных вопросов: https://t.me/+y2-TkkBjiuE0ZTNi
Спецкурс «Алгоритмы и структуры данных: дополнительные главы» - полугодовой по выбору студента.
Теория алгоритмов и структур данных является необходимой составляющей багажа современного разработчика программного обеспечения. Из практики программирования возникли интересные математические задачи, при решении которых используются методы дискретной математики, алгебры и теории вероятностей. Несмотря на большой интерес к теории алгоритмов, бурное развитие и большое количество публикаций, многие проблемы остаются открытыми до сих пор. В курсе излагаются методы построения алгоритмов: «разделяй и властвуй», жадные алгоритмы, динамическое и линейное программирование. Рассматриваются методы сортировки, хеширования и поиска, методы решения задач на графах, планирования, обработки текста, сжатия данных и 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