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

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

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

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

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

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

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

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

Кредиты: 14

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

Дополнительные материалы в 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 2nd module
0 * Бонус + 0.357 * Листики + 0.214 * Контрольная работа + 0.429 * Контесты
2026/2027 3rd module
0.3 * Экзамен + 0 * Бонус + 0.15 * Контрольная работа + 0.3 * Контесты + 0.25 * Листики
2026/2027 4th module
0.25 * Листики + 0.3 * Экзамен + 0.3 * Контесты + 0 * Бонус + 0.15 * Контрольная работа

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

Авторы

Фисенко Анна Сергеевна

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