Бакалавриат
2022/2023![Цель освоения дисциплины](/f/src/global/i/edu/objectives.svg)
![Планируемые результаты обучения](/f/src/global/i/edu/results.svg)
![Содержание учебной дисциплины](/f/src/global/i/edu/sections.svg)
![Элементы контроля](/f/src/global/i/edu/controls.svg)
![Промежуточная аттестация](/f/src/global/i/edu/intermediate_certification.svg)
![Список литературы](/f/src/global/i/edu/library.svg)
Алгоритмы и структуры данных
Лучший по критерию «Полезность курса для Вашей будущей карьеры»
Лучший по критерию «Полезность курса для расширения кругозора и разностороннего развития»
Лучший по критерию «Новизна полученных знаний»
Статус:
Курс обязательный (Вычислительные социальные науки)
Направление:
01.03.02. Прикладная математика и информатика
Где читается:
Факультет социальных наук
Когда читается:
1-й курс, 2, 4 модуль
Формат изучения:
без онлайн-курса
Охват аудитории:
для своего кампуса
Язык:
русский
Кредиты:
9
Контактные часы:
144
Программа дисциплины
Аннотация
В курсе рассматриваются теоретические основы комбинаторных алгоритмов решения известных задач сетевой и дискретной оптимизации и изучаются часто используемые структуры данных. Особое внимание уделяется применению современных структур данных для эффективной реализации комбинаторных алгоритмов.
Цель освоения дисциплины
- Изучение базовых алгоритмов и структур данных
- Развитие навыков обоснования корректности алгоритмов, их практической реализации, теоретической и экспериментальной оценки их временной сложности
Планируемые результаты обучения
- Знать о наиболее важных алгоритмах и структурах данных и основных принципах их проектирования и анализа
- Уметь обосновывать корректность алгоритмов, проводить теоретическую и экспериментальную оценки их временной сложности
- Уметь формализовать условие задачи, требующей алгоритмического решения, разбить задачу на подзадачи, сформулировать эффективный алгоритм решения задачи
- Иметь навыки реализации алгоритмов на языках Python
Содержание учебной дисциплины
- Алгоритмы: Классификация, сложность.
- Теория чисел.
- Рекурсивные алгоритмы.
- Поиск и сортировка.
- Структуры данных: стек, очередь, дек.
- Динамическое программирование.
- Куча
- Задача RMQ и RSQ. Запросы на подотрезках массива.
- Обработка событий.
- Дерево поиска
- Задача RMQ / RSQ. Дерево отрезков. Декартово дерево.
- Представление сетей в компьютере.
- Обход в глубину.
- Задача нахождения кратчайших путей в графе.
- Задача union - find.
- Занача нахождения минимального островного дерева.
Элементы контроля
- Работа на семинарах
- Домашние задание
- Контрольная работа
- Контрольная работа
- Работа на семинарах
- Домашнее задание
- Экзамен
- Экзамен
Промежуточная аттестация
- 2022/2023 учебный год 2 модуль0.3 * Домашние задание + 0.3 * Экзамен + 0.1 * Работа на семинарах + 0.3 * Контрольная работа
- 2022/2023 учебный год 4 модуль0.3 * Контрольная работа + 0.3 * Экзамен + 0.1 * Работа на семинарах + 0.3 * Домашнее задание
Список литературы
Рекомендуемая основная литература
- Алгоритмы : построение и анализ, пер. с англ., 3-е изд., 1323 с., Кормен, Т., Лейзерсон, Ч., Ривест, Р., Штайн, К., 2018
Рекомендуемая дополнительная литература
- Arora, S., & Barak, B. (2009). Computational Complexity : A Modern Approach. Cambridge: Cambridge eText. Retrieved from http://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=edsebk&AN=304712
- Искусство программирования. Т. 3: Сортировка и поиск, Кнут, Д., 1978
- Искусство программирования. Т.2: Получисленные алгоритмы, Кнут, Д. Э., 2012