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

Алгоритмы и структуры данных 2

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

Кто читает: Департамент больших данных и информационного поиска

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

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

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

Преподаватели: Горденко Мария Константиновна, Мануйленко Никита Сергеевич

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

Кредиты: 4

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

Аннотация

Продолжение дисциплины Алгоритмы и структуры данных 1. Понимание материала данного курса необходимо для успешной карьеры в области разработки программного обеспечения.

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

• Освоить принципы построения и анализа сложных структур данных, таких как сбалансированные деревья поиска, хеш-таблицы и графы.
• Сформировать умение применять эффективные алгоритмы для решения задач на графах, жадные алгоритмы и методы динамического программирования.

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

• Знает основые понятия теории алгоритмов и структур данных
• Использует базовые алгоритмы и подходы и модифицирует их, исходя из специфики решаемой задачи.
• Формализует и описывает алгоритм решения поставленных практических задач. Математически корректно и адекватно записывает алгоритмы, наиболее корректно описывающие дискретные объекты прикладной задачи.
• Подбирает оптимальный алгоритм для конкретной практической задачи, анализирует его эффективность.
• Студент знаком с основами алгоритмической теории сложности, приближенными и вероятностными методами решения труднорешаемых задач, в том числе задач, возникающих в анализе данных

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

• Хэш-функция. Полиномиальное хэширование
• Фильтр Блума.
• Z-функция. Префикс функция. Рабина Карпа.
• Бор. Алгоритм Ахо-Карасика
• Суффиксный массив.
• Деревья поиска. АВЛ - дерево.
• Красно-черное дерево.
• B-tree. Splay.
• Дерево отрезков.
• Дерево отрезков. Операции на отрезках.
• Декартово дерево по явному ключу.
• Декартово дерево по не явному ключу.
• LCA. Метод двоичных подъёмов.

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

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

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

• 2025/2026 1st module
  Оценка = 0.25*min(ДЗ; СР) + 0.25*КР + 0.4 * Экзамен + 0.1*активность

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

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

• Алгоритмы : построение и анализ, 2-е изд., 1290 с., Кормен, Т., Лейзерсон, Ч., Ривест, Р., Штайн, К., 2012
• Алгоритмы : построение и анализ, пер. с англ., 3-е изд., 1323 с., Кормен, Т., Лейзерсон, Ч., Ривест, Р., Штайн, К., 2018

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

• Cormen, T. H., Leiserson, C. E., Rivest, R. L., Stein, C. Introduction to Algorithms (3rd edition). – MIT Press, 2009. – 1292 pp.
• Комбинаторная оптимизация. Алгоритмы и сложность, Пападимитриу, Х., 1985

Авторы

• Горденко Мария Константиновна
• Солдатова Татьяна Владимировна