Бакалавриат
2025/2026
Алгоритмы и структуры данных (углубленный курс)
Статус:
Курс обязательный (Прикладная математика и информатика)
Кто читает:
Базовая кафедра Яндекс
Где читается:
Факультет компьютерных наук
Когда читается:
1-й курс, 2-4 модуль
Охват аудитории:
для своего кампуса
Язык:
русский
Кредиты:
14
Контактные часы:
216
Программа дисциплины
Аннотация
Целями освоения дисциплины «Алгоритмы и структуры данных – 2» являются углубленное ознакомление студентов с основами теории вычислительной сложности, приближенными и вероятностными методами решения труднорешаемых задач, в том числе задач, возникающих в анализе данных. В курсе дается представление о классах сложности P, NP и coNP и NP-полных задачах, изучаются способы доказательства NP-полноты задач и подходы к решению таких задач, в т.ч. экспоненциальные алгоритмы, отличные от полного перебора, приближенные алгоритмы и эффективные алгоритмы для частных случаев. Также рассматриваются потоковые алгоритмы, алгоритмы эффективного перечисления последовательностей и способы оценки их вычислительной сложности (задержка, кумулятивная задержка, сложность относительно размера входа и выхода).
Цель освоения дисциплины
- ознакомление студентов с основами алгоритмической теории сложности, приближенными и вероятностными методами решения труднорешаемых задач, в том числе задач, возникающих в анализе данных
Содержание учебной дисциплины
- Вводная лекция
- Матожидание
- Ram-модель
- Сортировки 1 и 2
- Хеши
- Хеши 2 (фильтр блума)
- Простые структуры данных
- Куча и фибкуча
- Внешняя память
- B-Дерево
- Splay
- Link cut tree
- Персистентность
- Деревья, LCA, LA
- Оптимизации дп
- Матроиды
- Пересечения матроидов
- Ньютон
- FFT Advanced
- Геометрия
- Стереометрия или ray tracing
- Монте Карло
- Эйлер, 2-сат
- СНМ
- Борувка, линейный mst
- ListRanking, Кеш
- Паросочетания, вершинные покрытия
- Потоки
- Венгерский алгоритм
- Переборы с масками
- Линейное программирование, двойственность
- Симплекс
Элементы контроля
- Экзамен
- Листки
- Контесты
- Контрольная работа
- Экзамен
- Контрольная работа
- Контесты
- Листки
- Бонус
