====== Введение в алгоритмы и структуры данных ======
=== Иванов А.Б. ===

**Когда**: суббота, 12:30

**Где**: 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

----

== Материалы лекций 2025/2026 ==