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

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

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

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

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

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

Преподаватели: Игнатов Андрей Дмитриевич, Нестеров Роман Александрович

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

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

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

Аннотация

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

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

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

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

овладеть принципами построения и методами анализа временной сложности алгоритмов
овладеть подходами к проектированию базовых и продвинутых структур данных
получить практический опыт в реализации алгоритмов и структур данных на языке программирования 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

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

Авторы

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

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