Магистратура
2021/2022
Современные методы принятия решений: алгоритмы и структуры данных
Статус:
Курс обязательный
Направление:
01.04.02. Прикладная математика и информатика
Где читается:
Факультет компьютерных наук
Когда читается:
1-й курс, 3 модуль
Формат изучения:
без онлайн-курса
Охват аудитории:
для своего кампуса
Прогр. обучения:
Машинное обучение и высоконагруженные системы
Язык:
русский
Кредиты:
4
Контактные часы:
36
Программа дисциплины
Аннотация
Данный курс покрывает базовые алгоритмы и структуры данных и полезен студентам любого IT-направления. В рамках курса студенты познакомятся с понятиями асимптотической сложности, научатся оценивать сложность алгоритмов, а также изучат базовые алгоритмы, которые зачастую спрашивают при прохождении собеседований на различные IT- позиции.
Цель освоения дисциплины
- Знать основные структуры данных
- Знать способы реализации основных структур данных на языке C++, включая средства стандартной библиотеки (STL)
- Знать основные методы поиска (линейный и бинарный)
- Знать различные методы сортировок (линейные, итерационные, рекурсивные)
- Уметь проводить оценку сложности простых алгоритмов
- Уметь реализовывать различные методы поиска на языке C++
- Уметь реализовывать различные методы сортировок на языке C++
- Уметь решать задачи, связанные с сортировками и методами поиска
Планируемые результаты обучения
- Знать различные методы сортировок
- Уметь решать задачи, связанные с сортировками и методами поиска
- Учение понять рекурсии, знание основных структур данных
Содержание учебной дисциплины
- Простые алгоритмы и асимптотическая оценка их сложности
- Простые структуры данных.
- Методы поиска. Линейный поиск. Бинарный поиск.
- Итерационные сортировки. Сортировка пузырьком. Сортировка выбором. Сортировка простыми вставками. Сортировка бинарными вставками.
- Линейные сортировки. Сортировка подсчетом. Цифровая сортировка (LSD, MSD).
- Рекурсия. Понятие прямой и косвенной рекурсии. Задача о Ханойских башнях.
- Рекурсивные сортировки. Сортировка слиянием. Быстрая сортировка.
- Двоичная куча. Пирамидальная сортировка.
Элементы контроля
- Домашнее заданиеЕсть бонусное задание (Бонус)
- ЭкзаменИтог = Округление(0.7 * Накоп + 0.3 * Э). Округление арифметическое. Если Накоп >=8, то студент может получить Накоп в качестве итоговой оценки, не приходя на экзамен. В рамках курса по каждой теме предусмотрено бонусное задание. Выдается на каждой неделе после проведения лекции и семинара на соответствующую тему. Форма проведения – решение задач в системе Яндекс.Контест. За каждый решенный блок задач можно получить до 2 баллов к оценке за основное домашнее задание по соответствующей теме. Дедлайн по всем задачам – 1 неделя после последнего занятия.
Список литературы
Рекомендуемая основная литература
- Алгоритмы: построение и анализ, Кормен, Т., 2007
- Структуры данных и алгоритмы, Ахо, А. В., 2010
Рекомендуемая дополнительная литература
- Дискретная математика для программистов, Новиков, Ф. А., 2001
- Дискретная математика для программистов, Хаггард, Г., 2010
- Структуры данных и алгоритмы Java, Лафоре, Р., 2014