Магистратура
2024/2025
Алгоритмический инструментарий
Статус:
Курс обязательный (Инженерия данных)
Направление:
09.04.04. Программная инженерия
Где читается:
Факультет компьютерных наук
Когда читается:
1-й курс, 3, 4 модуль
Формат изучения:
без онлайн-курса
Охват аудитории:
для своего кампуса
Прогр. обучения:
Инженерия данных
Язык:
русский
Кредиты:
6
Программа дисциплины
Аннотация
В курсе рассматриваются основные подходы к анализу и проектированию алгоритмов и структур данных. Среди тем, изучаемых в курсе, — асимптотическая оценка сложности алгоритма в худшем случае, эффективные алгоритмы сортировки и выбора порядковых статистик, структуры данных (двоичные деревья поиска, хеш-таблицы), способы проектирования алгоритмов (динамическое программирование, жадная стратегия), основные алгоритмы на графах (кратчайшие пути, топологическая сортировка, компоненты связности, минимальные остовные деревья).
Цель освоения дисциплины
- Знать о наиболее важных алгоритмах и структурах данных и основных принципах их проектирования и анализа
- Иметь навыки реализации алгоритмов на языках Python и C++
- Уметь обосновывать корректность алгоритмов, проводить теоретическую и экспериментальную оценки их временной сложности
- Уметь формализовать условие задачи, требующей алгоритмического решения, разбить задачу на подзадачи, сформулировать эффективный алгоритм решения задачи
Планируемые результаты обучения
- Знание наиболее важных алгоритмов и структур данных и основных принципов их проектирования и анализа
- Приобретение навыков реализации алгоритмов на языках Python
- Умение обосновывать корректность алгоритмов, проводить теоретическую и экспериментальную оценки их временной сложности
- Умение оценивать объёмную сложность алгоритмов в дополнение к временной сложности
- -ознакомление студентов с основными принципами проектирования и анализа алгоритмов и структур данных;
- -развитие навыков обоснования корректности алгоритмов, их практической реализации, теоретической и экспериментальной оценки их временной сложности
Содержание учебной дисциплины
- Основы C++
- Настройка среды для разработки и тестирования на C++ и ознакомление с платформой codeforces
- STL в C++26 и основы ООП в C++
- Решение задач для ознакомления с языком
- Рекурсия, перебор, анализ времени работы, O-, o-, Theta-нотации
- Бинарный поиск
- Сортировки
- Метод двух указателей, метод сканирующей прямой
- Стек, очередь, дек
- Хеширование, хеш-таблицы
- Одномерное и многомерное динамическое программирование
- Деревья отрезков
- Дерево отрезков
- Корневая декомпозиция
- Задача о рюкзаке и ее модификации
- Персистетные структуры данных
- B, B+ -деревья, ScapeGoat-tree
- Алгоритмы во внешней памяти
- Map-Reduce
- Потоковые алгоритмы
Элементы контроля
- Домашние заданияВыдается после соответствующей лекции, дедлайн 1-2 недели в зависимости от темы и остальных заданий. Формула оценивания заивист от количества решенных задач, количества задач в контесте и сложности контеста
- Контрольные работы3 штуки: После окончания изучения C++ На последней лекции 3 модуля по пройденным темам 3 модуля На последней лекции 4 моделя по пройденным темам 4 модуля
Промежуточная аттестация
- 2024/2025 4th module0.35 * Домашние задания + 0.35 * Домашние задания + 0.15 * Контрольные работы + 0.15 * Контрольные работы
Список литературы
Рекомендуемая основная литература
- Data structures and algorithm analysis in C++, Weiss, M. A., 2006
- Yang, X.-S. (2019). Introduction to Algorithms for Data Mining and Machine Learning. Academic Press.
Рекомендуемая дополнительная литература
- Павловская, Т. А. Программирование на языке C++ : учебное пособие / Т. А. Павловская. — 2-е изд. — Москва : ИНТУИТ, 2016. — 154 с. — Текст : электронный // Лань : электронно-библиотечная система. — URL: https://e.lanbook.com/book/100409 (дата обращения: 00.00.0000). — Режим доступа: для авториз. пользователей.