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