Алгоритмы и структуры данных II. Иностранный поток весна 2025

Общие сведения

Целями освоения дисциплины «Алгоритмы и структуры данных – 2» являются ознакомление с основами теории вычислительной сложности, приближенными и вероятностными методами решения труднорешаемых задач, в том числе задач, возникающих в анализе данных. В курсе дается представление о классах сложности P, NP и coNP и NP-полных задачах, изучаются способы доказательства NP-полноты задач и подходы к решению таких задач, в т.ч. экспоненциальные алгоритмы, отличные от полного перебора, приближенные алгоритмы и эффективные алгоритмы для частных случаев. Также рассматриваются потоковые алгоритмы, алгоритмы эффективного перечисления последовательностей и способы оценки их вычислительной сложности (задержка, кумулятивная задержка, сложность относительно размера входа и выхода).

• Форма контроля: дифф зачет + экзамен.
• Канал курса

Руководитель курса

Александр Смолин

План курса

1. Обходы графов. DFS

- Хранение графа: матрица и список смежности
- Обход в ширину (DFS)
  * Атрибуты вершин: цвета, времена входа и выхода
  * Лемма о белых путях
  * Топологическая сортировка
  * Компоненты сильной связности. Алгоритм Косарайю
  * Реберная двусвязность. Поиск мостов
  * Поиск точек сочленения

2. Кратчайшие пути

- BFS: классический, 0-1, 1-k, 0-k
- Алгоритм Дейкстры
- Эвристический поиск. Алгоритм A-star
- Алгоритм Форда-Беллмана
- Алгоритм Флойда-Уоршелла
- Поиск циклов отрицательного веса

3. Система непересекающихся множеств 4. Минимальные остовые деревья

- Лемма о безопасном ребре
- Алгоритм Прима. Аналогии с алгоритмом Дейкстры
- Алгоритм Крускала.
- Алгоритм Борувки.

5. Наименьший общий предок

- Наивное решение
- Двоичные подъемы
- Сведение LCA <-> RMQ
- Алгоритм Фараха-Колтона-Бендера
- static online RMQ с линейным предподсчетом и константным ответом на запрос

6. Паросочетания

- Двудольные графы
- Теорема Бержа
- Алгоритм Куна

7. Потоки

- Понятие сети, потока, разреза. Модификации сети
- Остаточная сеть
- Соотношение между величинами потоков и разрезов
- Теорема Форда-Фалкерсона
- Схема Форда-Фалкерсона
  * Алгоритм Форда-Фалкерсона
  * Алгоритм Эдмондса-Карпа
- Схема Диница
  * Блокирующий поток
  * Удаляющий обход
- Потенциал сети. Первая теорема Карзанова
- Алгоритм Хопкрофта-Карпа

8. Строки

- Поиск паттерна в тексте
  * Префикс-функция. Алгоритм Кнута-Морриса-Прата
  * Z-функция. Алгоритм Кнута-Морриса-Прата
  * Полиномиальное хеширование. Алгоритм Рабина-Карпа
- Поиск множества паттернов в тексте
  * Бор
  * Автомат Ахо-Корасик
- Алгоритмы на подстроках. Суффиксный автомат
  * Наивное построение
  * Линейный алгоритм

9. Быстрое преобразование Фурье

Домашние задания

• Домашние задания: контесты и теоретические задания. Информация о них будет публиковаться на канале.

Оценки

• Оценивание зачета
• до 7 баллов за контесты,
• до 3 баллов за теор задания,
• 1 бонусный балл от семинариста за активность.
• Сумма — оценка за зачёт.

• Оценка за зачёт ставится исходя из непосредственно экзамена и 2 кр, которые будут проведены течении семестра.
• Формула такая:

Стартовая оценка -2, до 6 баллов за ответ билета, до 1 балла за блиц опрос, до 3 баллов за 2 кр в течении семестра: 1.5 за каждую. Далее, если студент получил 7 и больше, то его текущая оценка 7, если меньше — то что он получил. Для получения отла студенту предлагают 2 задачи, от решения которых зависит итоговая оценка.