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

Бакалавриат 2026/2027

Статус: Курс обязательный (Прикладная математика и информатика)

Кто читает: Базовая кафедра Яндекс

Где читается: Факультет компьютерных наук

Когда читается: 2-й курс, 1 модуль

Охват аудитории: для своего кампуса

Преподаватели: Волков Иван Андреевич, Шайдурова Полина Сергеевна, Шулятьев Артём Евгеньевич

Язык: русский

Кредиты: 3

Контактные часы: 56

Дополнительные материалы в LMS Задать вопрос

Аннотация

Целями освоения дисциплины «Алгоритмы и структуры данных – 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.05 * Внешний экзамен компетенций образовательной программы топ-уровня + 0.25 * Экзамен + 0.25 * Домашнее задание + 0.16 * Контесты + 0.29 * Контрольная работа

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

Авторы

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

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