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

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

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

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

- Канал курса: https://t.me/ads_foreings

- Руководитель курса: Александр Смолин

План курса

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

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

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

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

3. Система непересекающихся множеств.

4. Минимальные остовые деревья.

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

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

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

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

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

7. Потоки

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

8. Строки

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

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

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

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

Оценки

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

Сумма — оценка за зачёт.

Оценка за экзамен Оценка за экзамен ставится исходя из непосредственно экзамена.

До 6 баллов за ответ билета, до 1 балла за блиц опрос. Далее, если студент получил менее 5.5, то экзамен заканчивается и студент получает оценку равную наборанному числу баллов округленную по правилам математического округления. Иначе студент получает задачу "на отл(9)". Если решить ее не получается, то студент получает задачу "на отл(8)". Если студент решает задачу "на отл(9)", то получает задачу "на отл(10)".