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




Алгоритмы и структуры данных
ID 1159441
Статус:
Курс по выбору (Прикладная математика и информатика)
Кто читает:
Базовая кафедра Яндекс
Где читается:
Факультет компьютерных наук
Когда читается:
1-й курс, 2, 4 модуль
Охват аудитории:
для всех кампусов НИУ ВШЭ
Преподаватели:
Богданов Сергей Юрьевич,
Гревцев Александр Владимирович,
Гундарев Пётр Алексеевич,
Густокашин Михаил Сергеевич,
Иванов Максим Юрьевич,
Кондаков Семен Васильевич,
Куренков Владимир Вячеславович,
Лоредо Андрей Александрович,
Лоскутников Станислав Артурович,
Мануйленко Никита Сергеевич,
Нестеренко Алиса Вадимовна,
Никитин Богдан Сергеевич,
Панькова Марина Геннадьевна,
Петров Андрей Иванович,
Петрухин Вячеслав Юрьевич,
Самоненко Илья Юрьевич,
Урьев Максим Дмитриевич,
Фолунин Владимир Александрович,
Шинкарев Елисей Сергеевич,
Шнипов Антон Александрович
Язык:
русский
Кредиты:
10
Контактные часы:
136
Программа дисциплины
Аннотация
"Курс дает базовые знания в области алгоритмов и структур данных. В явном виде они, может быть, не пригодятся, но очень важны для понимания работы библиотек, алгоритмов и языков программирования. Домашние задания по курсу закрепляют полученные знания и воспитывают хороший стиль написания кода, который позволяет избежать стандартных, но от этого ничуть не менее распространенных даже у опытных разработчиков, ошибок."
Цель освоения дисциплины
- Цель курса — обучить основам алгоритмического программирования, привить практические навыки решения задач с помощью базовых алгоритмов и структур данных, сформировать правильное представление о времени работы и эффективности различных алгоритмов и структур данных.
Планируемые результаты обучения
- Иметь представление о быстрых методах поиска k-й порядковой статистики
- Иметь представление о задачах LCA и RMQ и об связи между ними
- Иметь представление о кучах. Уметь использовать кучи для решения практических задач
- Иметь представление о персистентных структурах данных
- Иметь представление об основных алгоритмах сортировки. Понимать их преимущества и недостатки.
- Иметь представление об основных структурах данных
- Иметь представления о хэш-функциях и их свойствах. Уметь выбирать хэш-функцию для работы с заданным типом данных.
- Уметь интерпретировать практические задачи в терминах теории графах, решать эти задачи с использованием графовых алгоритмах
- Уметь находить кратчайшие пути в графах
- Уметь обходить графы в ширину и в глубину
- Уметь строить и эффективно использовать деревья поиска, выбирать правильную стратегию балансировки
- Уметь строить остовные деревья для графов.
- Уметь устранять коллизии при использовании хэш-таблиц
- Уметь эффективно реализовывать структуры данных в виде структур на языке С++
- Понимать устройство массивов переменного размера.
- Уметь оценивать сложность алгоритмов и объём дополнительной памяти.
Содержание учебной дисциплины
- Введение
- Введение в структуры данных
- Сортировки
- Кучи
- Хэширование
- Графы
- Деревья поиска
- Кратчайшие пути в графах
- LCA & RMQ
- Графы: продвинутые темы
- 1. Алгоритмы и их сложность
- 2. Стек. Очередь. Дек
- 3. Сортировки
- 4. Куча. Двоичный поиск
- 5. Быстрая сортировка. Сортировка подсчетом и поразрядная. Хеш-таблицы
- 6. Два указателя. Сортировка событий
- 7. Динамическое программирование. Классические задачи
- 8. Двумерная динамика. Динамика по подстрокам
- 9. Динамическое программирование. Задача о рюкзаке. Жадные алгоритмы
- 10. Хеши для строк
- 11. Обход в глубину: связность, циклы, двудольность, топологическая сортировка, мосты, точки сочленения
- 12. Обход в ширину
- 13. Алгоритм Дейкстры
- 14. Алгоритмы Форда-Беллмана и Флойда
- 15. Система непересекающихся множеств, остовные деревья
- 16. Двоичные деревья поиска, балансировка
- 17. Декартово дерево
- 18. Дерево отрезков
- 19. Префиксные суммы, разреженные таблицы и дерево Фенвика
- 20. LCA
- 21. Арифметика и теория чисел
- 22. Комбинаторные объекты
- 23. Перебор
- 24. Корневая оптимизация
Промежуточная аттестация
- 2026/2027 2nd module0.2 * Контрольная работа + 0.4 * Экзамен + 0.1 * Работа на семинаре + 0.3 * Домашнее задание
- 2026/2027 4th module0.3 * Домашнее задание + 0.1 * Работа на семинаре + 0.2 * Контрольная работа + 0.4 * Экзамен
Список литературы
Рекомендуемая основная литература
- Алгоритмы и структуры данных : учебник для вузов, Белов, В. В., 2022
- Комбинаторика и теория графов : учеб. пособие, Кочетков, Ю. Ю., 2009
Рекомендуемая дополнительная литература
- Теория графов : учеб. пособие для втузов, Белов, В. В., 1976
- Язык С#. Базовый курс : учеб. пособие для вузов, Подбельский, В. В., 2013
- Язык С#. Решение задач : учеб. пособие для вузов, Подбельский, В. В., 2014