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

2025/2026

Учебный год

RUS

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

Кредиты

Кто читает:

Департамент программной инженерии

Статус:

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

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

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

Преподаватели

Игнатов Андрей Дмитриевич

Нестеров Роман Александрович

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

Аннотация

Учебный курс "Алгоритмы и структуры данных" является обязательной дисциплиной для студентов второго курса по направлению "Программная инженерия" факультета компьютерных наук НИУ ВШЭ. Основная цель курса заключается в формировании у студентов навыков анализа производительности алгоритмов, работающих с различными структурами данных, и выбора оптимальных решений для конкретных практических задач. В ходе обучения рассматриваются методы асимптотического анализа сложности как детерминированных, так и стохастических алгоритмов, изучаются алгоритмы сортировки, методы эффективного хранения и поиска данных, включая организацию хеш-таблиц и деревьев, а также графовые и строковые алгоритмы. Особое внимание уделяется различным парадигмам разработки алгоритмов, таким как жадные методы, приближенные алгоритмы и динамическое программирования. Кроме того, рассматриваются фундаментальный вопросы разрешимости и вычислимости. Лекции направлены на систематическое освоение материала, тогда как практические занятия позволяют закрепить полученные знания через решение задач и реализацию изученных алгоритмов и структур данных на языке программирования С++. Тесная взаимосвязь лекционного материала и практической работы обеспечивает глубокое и всестороннее освоение курса.

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

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

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

• овладеть принципами построения и методами анализа временной сложности алгоритмов
• овладеть подходами к проектированию базовых и продвинутых структур данных
• получить практический опыт в реализации алгоритмов и структур данных на языке программирования C++
• овладеть методами точного и асимптотического анализа сложности алгоритмов
• овладеть подходами к анализу, проектированию и реализации базовых (массивы, списки, стеки, очереди) и продвинутых (хеш-таблицы, очереди с приоритетами, сбалансированные деревья поиска, графы) структур данных
• получить практический опыт реализации изученных алгоритмов и структур данных на языке программирования С++
• овладеть специальными подходами к разработке алгоритмов (стохастические и приближенные алгоритмы)
• овладеть основными парадигмами разработки алгоритмов (жадные алгоритмы, динамическое программирование и "разделяй-и-властвуй")
• овладеть подходами точного, асимптотического и амортизированного анализа сложности алгоритмов

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

• Неделя 1. Корректность и сложность алгоритма
• Неделя 2. Линейные контейнеры
• Неделя 3. Асимптотический анализ. Рекуррентное соотношение
• Неделя 4. Асимптотический анализ. Дерево рекурсии
• Неделя 5. Мастер-теорема для решения рекуррентных соотношений
• Неделя 6-7. Стохастические алгоритмы
• Неделя 8. Сортировка, основанная на сравнениях
• Неделя 9. Линейная сортировка
• Неделя 10. Бинарные деревья (поиска). Введение
• Неделя 11. AVL-деревья и красно-черные деревья
• Неделя 12. Случайные и декартовы деревья
• Неделя 13. Splay-деревья
• Неделя 14. Хеширование. Хеш-функции
• Неделя 15. Хеш-таблицы
• Неделя 16. Вероятностные структуры данных
• Неделя 17. Графы. Базовые аспекты
• Неделя 18. Остовное дерево графа
• Неделя 19. Поиск кратчайших путей в графе
• Неделя 20. Сети и потоки
• Неделя 21. Паросочетания в графах
• Неделя 22-23. Раскраска и укладка графа
• Неделя 24. Поиск точного вхождения строки в текст
• Неделя 25. Редакционные расстояния
• Неделя 26. Поиск вхождения набора строк в текст
• Неделя 27. Хранение и сортировка строк
• Неделя 28. Кодирование и сжатие строк
• Неделя 29. Жадный алгоритм и динамическое программирование
• Неделя 30. Приближенные алгоритмы. Метод ветвей и границ
• Неделя 31. Стохастические алгоритмы
• Неделя 32. Разрешимость

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

• НАКОП1
  Формализуемая часть накопленной оценки регулярной работы в течение первого семестра
• НАКОП2
  Формализуемая часть накопленной оценки регулярной работы в течение второго семестра
• ПР1
  Регулярная работа на практических занятиях в течение первого семестра
• ПР2
  Регулярная работа на практических занятиях в течение второго семестра
• ЭКЗАМЕН1
  Устный экзамен по материалам первого семестра курса
• ЭКЗАМЕН2
  Устный экзамен по материалам второго семестра курса

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

• 2025/2026 2nd module
  0.48 * НАКОП1 + 0.17 * ПР1 + 0.35 * ЭКЗАМЕН1
• 2025/2026 4th module
  0.45 * НАКОП2 + 0.2 * ПР2 + 0.35 * ЭКЗАМЕН2

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

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

• Data structures and algorithm analysis in C++, Weiss, M. A., 2006
• Introduction to algorithms, Cormen, T. H., 2009
• Kleinberg, J., & Tardos, E. (2014). Algorithm Design: Pearson New International Edition. Harlow, Essex: Pearson. Retrieved from http://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=edsebk&AN=1418332
• Теория графов, Оре, О., 1980

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

• Грокаем алгоритмы. Иллюстрированное пособие для программистов и любопытствующих. - 978-5-4461-0923-4 - Бхаргава А. - 2022 - Санкт-Петербург: Питер - https://ibooks.ru/bookshelf/376971 - 376971 - iBOOKS
• Седжвик, Р. Алгоритмы на С++ : учебное пособие / Р. Седжвик. — 2-е изд. — Москва : ИНТУИТ, 2016. — 1772 с. — Текст : электронный // Лань : электронно-библиотечная система. — URL: https://e.lanbook.com/book/100565 (дата обращения: 00.00.0000). — Режим доступа: для авториз. пользователей.
• Теория графов, Оре, О., 2009

Авторы

• Нестеров Роман Александрович