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

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

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

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

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

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

Охват аудитории: для всех кампусов НИУ ВШЭ

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

Кредиты: 10

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

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

Аннотация

"Курс дает базовые знания в области алгоритмов и структур данных. В явном виде они, может быть, не пригодятся, но очень важны для понимания работы библиотек, алгоритмов и языков программирования. Домашние задания по курсу закрепляют полученные знания и воспитывают хороший стиль написания кода, который позволяет избежать стандартных, но от этого ничуть не менее распространенных даже у опытных разработчиков, ошибок."

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

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

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

Иметь представление о быстрых методах поиска 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 module
0.2 * Контрольная работа + 0.4 * Экзамен + 0.1 * Работа на семинаре + 0.3 * Домашнее задание
2026/2027 4th module
0.3 * Домашнее задание + 0.1 * Работа на семинаре + 0.2 * Контрольная работа + 0.4 * Экзамен

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

Авторы

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

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