2024/2025
Алгоритмы и структуры данных
Статус:
Маго-лего
Когда читается:
4 модуль
Охват аудитории:
для своего кампуса
Преподаватели:
Горденко Мария Константиновна
Язык:
русский
Кредиты:
3
Программа дисциплины
Аннотация
В курсе рассматриваются основы алгоритмов и изучаются часто используемые структуры данных. Особое внимание уделяется применению современных структур данных для эффективной реализации комбинаторных алгоритмов.
Цель освоения дисциплины
- Изучение базовых алгоритмов и структур данных
- Развитие навыков обоснования корректности алгоритмов, их практической реализации, теоретической и экспериментальной оценки их временной сложности
Планируемые результаты обучения
- Студенты понимают основные концепции сложности алгоритмов.
- Студенты умеют выполнять базовые операции над линейными структурами данных.
- Студенты понимают суть рекурсивных функций и принцип их работы.
- Студенты разбирают классические примеры применения рекурсии, включая Ханойские башни.
- Студенты понимают основные термины и определения.
- Студенты умеют представлять графы в памяти компьютера с использованием матриц смежности и списков смежности.
Содержание учебной дисциплины
- Оценка сложности алгоритма
- Линейные структуры данных
- Линейные алгоритмы.
- Понятие рекурсии. Основные задачи рекурсии. Задача о ханойских башнях.
- Задача сортировки и поиска. Виды поиска. Бинарный поиск.
- Итеративные сортировки.
- Двоичная куча. Пирамидальная сортировка.
- Быстрая сортировка. Сортировка слиянием.
- Динамическое программирование. Основные задачи, решаемые с помощью динамического программирования.
- Алгоритмы обработки строк.
- Основные понятия теории графов. Представление графов в памяти компьютера. Алгоритмы обхода графов.
- Связный список
Промежуточная аттестация
- 2024/2025 4th moduleИтог = Округление(0.25 * ДЗ + 0.25 * КР + 0.3 * Э + 0.2 * Проект), где ДЗ — средняя оценка за все домашние задания, КР — оценка за контрольную работу, Э — оценка за экзамен, Проект – сложный набор задач, в т.ч. по непройденным в курсе темам, показывающий блестящее владение материалом.
Список литературы
Рекомендуемая основная литература
- Cormen, T. H. (2009). Introduction to Algorithms (Vol. 3rd ed). Cambridge, Mass: The MIT Press. Retrieved from http://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=edsebk&AN=343613
- Вычислительные машины и труднорешаемые задачи, 416 с., Гэри, М., Джонсон, Д., 2012
Рекомендуемая дополнительная литература
- Computational Complexity, A Modern Approach, 1st published 2009, 4th printing, XXIV, 579 p., Arora, S., Barak, B., 2016
- Алгоритмы : построение и анализ, пер. с англ., 3-е изд., 1323 с., Кормен, Т., Лейзерсон, Ч., Ривест, Р., Штайн, К., 2018