Алгоритмы и структуры данных 2 (углубленный курс)

2026/2027

Учебный год

RUS

Обучение ведется на русском языке

3

Кредиты

Кто читает:

Базовая кафедра Яндекс (Департамент больших данных и информационного поиска)

Статус:

Курс обязательный

Когда читается:

2-й курс, 1 модуль

Программа дисциплины

Аннотация

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

Цель освоения дисциплины

• ознакомление студентов с основами алгоритмической теории сложности, приближенными и вероятностными методами решения труднорешаемых задач, в том числе задач, возникающих в анализе данных

Планируемые результаты обучения

• Уметь адаптировать известные и проектировать новые алгоритмы для решения вычислительно сложных задач на практике
• Уметь разбить задачу на подзадачи, эффективно реализовать программные компоненты для отдельных подзадач и связать их воедино
• Уметь проводить анализ корректности и временной сложности алгоритмов; распознавать класс сложности задач

Содержание учебной дисциплины

• Основы теории вычислительной сложности
• Методы решения труднорешаемых задач
• Задачи и алгоритмы анализа данных
• Вводная лекция
• Матожидание
• Ram-модель
• Сортировки 1 и 2
• Хеши
• Хеши 2 (фильтр блума)
• Простые структуры данных
• Куча и фибкуча
• Внешняя память
• B-Дерево
• Splay
• Link cut tree
• Персистентность
• Деревья, LCA, LA
• Оптимизации дп
• Матроиды
• Пересечения матроидов
• Ньютон
• FFT Advanced
• Геометрия
• Стереометрия или ray tracing
• Монте Карло
• Эйлер, 2-сат
• СНМ
• Борувка, линейный mst
• ListRanking, Кеш
• Паросочетания, вершинные покрытия
• Потоки
• Венгерский алгоритм
• Переборы с масками
• Линейное программирование, двойственность
• Симплекс

Элементы контроля

• Контрольная работа
• Экзамен
• Домашнее задание
• Контесты

Промежуточная аттестация

• 2026/2027 1st module
  0.25 * Домашнее задание + 0.3 * Экзамен + 0.16 * Контесты + 0.29 * Контрольная работа

Список литературы

Рекомендуемая основная литература

• Седжвик, Р. Алгоритмы на С++ : учебное пособие / Р. Седжвик. — 2-е изд. — Москва : ИНТУИТ, 2016. — 1772 с. — Текст : электронный // Лань : электронно-библиотечная система. — URL: https://e.lanbook.com/book/100565 (дата обращения: 00.00.0000). — Режим доступа: для авториз. пользователей.

Рекомендуемая дополнительная литература

• Вирт, Н. Алгоритмы и структуры данных. Новая версия для Оберона : учебное пособие / Н. Вирт. — Москва : ДМК Пресс, 2010. — 272 с. — ISBN 978-5-94074-584-6. — Текст : электронный // Лань : электронно-библиотечная система. — URL: https://e.lanbook.com/book/1261 (дата обращения: 00.00.0000). — Режим доступа: для авториз. пользователей.

Авторы

• Фисенко Анна Сергеевна
• Евстропов Глеб Олегович
• Алиева Эльмира Махир Кызы
• Смирнов Иван Федорович