Бакалавриат
2025/2026
Алгоритмы и структуры данных
Статус:
Курс обязательный (Компьютерные науки и анализ данных)
Где читается:
Факультет компьютерных наук
Когда читается:
1-й курс, 2, 4 модуль
Охват аудитории:
для своего кампуса
Преподаватели:
Горденко Мария Константиновна
Язык:
русский
Кредиты:
10
Контактные часы:
144
Программа дисциплины
Аннотация
Курс охватывает фундаментальные алгоритмы и структуры данных, необходимые каждому разработчику. В программу курса входит изучение алгоритмов сортировки, составление рекурсий, динамическое программирование, бинарный поиск, жадные алгоритмы и оценка сложности алгоритмов.
Цель освоения дисциплины
- Целью освоения дисциплины является формирование у студентов теоретических знаний и практических навыков в области теории алгоритмов, современных структур данных и их реализации на языке программирования Python.
Планируемые результаты обучения
- Умеет оценивать сложность алгоритмов по времени и памяти.
- Выбирает и реализует оптимальные структуры данных для решения конкретных задач.
- Применяет эффективные методы поиска и обработки массивов.
- Знает классические алгоритмы теории чисел.
- Реализовывает и сравнивает алгоритмы сортировки разной сложности.
- Использует бинарный поиск для решения задач.
- Строит и обосновывает жадные алгоритмы, понимая границы их применимости.
- Применяет метод сканирующей прямой для решения задач на обработку событий.
- Умеет составлять рекурсивные алгоритмы для перебора и сортировок.
- Решет оптимизационные задачи через динамическое программирование.
Содержание учебной дисциплины
- Алгоритмы: классификация, сложность
- Теория чисел. Алгоритм Евклида. Решето Эратосфена. Факторизация чисел.
- Линейный поиск в массиве данных. Метод двух указателей, метод префиксных сумм.
- Структуры данных: множества, словари, стеки, деки, очереди.
- Жадные алгоритмы
- Обработка событий. Метод сканирующей прямой.
- Бинарный поиск. Бинарный поиск по ответу. Вещественный бинарный поиск.
- Сортировки. Сортировка подсчётом, квадратичные сортировки: вставками, обмена, выбора.
- Структура данных - куча. Пирамидальная сортировка
- Контрольная работа
- Рекурсивные алгоритмы. Комбинаторный перебор и рекурсия.
- Рекурсивные сортировки: сортировка слиянием, быстрая сортировка, k-ая порядковая статистика
- Динамическое программирование: одномерная динамика.
- Динамическое программирование с двумя параметрами. Динамическое программирование на таблицах.
- Динамическое программирование: задачи укладки рюкзака
- Консультационное занятие
Промежуточная аттестация
- 2025/2026 2nd moduleИтог = Округление(0.3* Семинары + 0.3 * ДЗ + 0.1 * КР + 0.3 * Э), Где Семинары – средняя оценка за работу на семинарах, ДЗ — средняя оценка за все домашние задания, КР — оценка за контрольную работу, Э — оценка за экзамен. Автомата за курс нет.
- 2025/2026 4th moduleИтог = Округление(0.3* Семинары + 0.3 * ДЗ + 0.1 * КР + 0.3 * Э), Где Семинары – средняя оценка за работу на семинарах, ДЗ — средняя оценка за все домашние задания, КР — оценка за контрольную работу, Э — оценка за экзамен. Автомата за курс нет.
Список литературы
Рекомендуемая основная литература
- Алгоритмы: построение и анализ : пер.с англ., Кормен, Т., 2013
- Лааксонен, А. Олимпиадное программирование / А. Лааксонен , перевод с английского А. А. Слинкин. — 2-е изд. — Москва : ДМК Пресс, 2020. — 328 с. — ISBN 978-5-97060-878-4. — Текст : электронный // Лань : электронно-библиотечная система. — URL: https://e.lanbook.com/book/190748 (дата обращения: 00.00.0000). — Режим доступа: для авториз. пользователей.
- Программирование: теоремы и задачи, Шень, А., 2007
Рекомендуемая дополнительная литература
- Афанасьев, В. В. Структуры данных и алгоритмы : учебно-методическое пособие / В. В. Афанасьев, Е. И. Новиков, О. В. Тараканов. — Москва : РТУ МИРЭА, 2024. — 163 с. — ISBN 978-5-7339-2380-2. — Текст : электронный // Лань : электронно-библиотечная система. — URL: https://e.lanbook.com/book/464639 (дата обращения: 00.00.0000). — Режим доступа: для авториз. пользователей.