Магистратура
2021/2022




Алгоритмы и структуры данных
Лучший по критерию «Полезность курса для Вашей будущей карьеры»
Лучший по критерию «Полезность курса для расширения кругозора и разностороннего развития»
Лучший по критерию «Новизна полученных знаний»
Статус:
Курс по выбору (Науки о данных (Data Science))
Направление:
01.04.02. Прикладная математика и информатика
Кто читает:
Базовая кафедра Яндекс
Где читается:
Факультет компьютерных наук
Когда читается:
1-й курс, 1, 2 модуль
Формат изучения:
без онлайн-курса
Охват аудитории:
для своего кампуса
Преподаватели:
Бабенко Максим Александрович
Прогр. обучения:
Науки о данных
Язык:
русский
Кредиты:
5
Контактные часы:
56
Программа дисциплины
Аннотация
"Курс дает базовые знания в области алгоритмов и структур данных. В явном виде они, может быть, не пригодятся, но очень важны для понимания работы библиотек, алгоритмов и языков программирования. Домашние задания по курсу закрепляют полученные знания и воспитывают хороший стиль написания кода, который позволяет избежать стандартных, но от этого ничуть не менее распространенных даже у опытных разработчиков, ошибок."
Цель освоения дисциплины
- Цель курса — обучить основам алгоритмического программирования, привить практические навыки решения задач с помощью базовых алгоритмов и структур данных, сформировать правильное представление о времени работы и эффективности различных алгоритмов и структур данных.
Планируемые результаты обучения
- Владеть концепцией динамического программирования
- Иметь представление о быстрых методах поиска k-й порядковой статистики
- Иметь представление о задачах LCA и RMQ и об связи между ними
- Иметь представление о кучах. Уметь использовать кучи для решения практических задач
- Иметь представление о персистентных структурах данных
- Иметь представление об основных алгоритмах сортировки. Понимать их преимущества и недостатки.
- Иметь представление об основных структурах данных
- Иметь представления о хэш-функциях и их свойствах. Уметь выбирать хэш-функцию для работы с заданным типом данных.
- Понимать устройство массивов переменного размера
- Уметь интерпретировать практические задачи в терминах теории графах, решать эти задачи с использованием графовых алгоритмах
- Уметь находить кратчайшие пути в графах
- Уметь обходить графы в ширину и в глубину
- Уметь оценивать сложность алгоритмов и объём дополнительной памяти
- Уметь строить и эффективно использовать деревья поиска, выбирать правильную стратегию балансировки
- Уметь строить остовные деревья для графов.
- Уметь устранять коллизии при использовании хэш-таблиц
- Уметь эффективно реализовывать алгоритмы на языке С++
- Уметь эффективно реализовывать структуры данных в виде структур на языке С++
- Уметь эффективно решать практические задачи с помощью динамического программирования
Содержание учебной дисциплины
- Введение
- Динамическое программирование
- Введение в структуры данных
- Сортировки
- Кучи
- Хэширование
- Графы
- Деревья поиска
- Кратчайшие пути в графах
- LCA & RMQ
- Графы: продвинутые темы
Промежуточная аттестация
- 2021/2022 учебный год 2 модуль0.4 * Экзамен + 0.3 * Домашняя работа 1 + 0.3 * Домашняя работа 2
Список литературы
Рекомендуемая основная литература
- Комбинаторика и теория графов. Ч.1: ., Григорьев, Б. В., 2005
- Сахибназарова Виктория Бахтиёровна, Сайгак Кристина Олеговна, & Saygak Kristina Olegovna. (2016). Разработка и анализ алгоритма сортировки на основе использования бинарных деревьев. Retrieved from http://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=edsbas&AN=edsbas.8368E341
- Суркова, А., & Буденков, С. (2012). Построение Модели И Алгоритма Кластеризации В Интеллектуальном Анализе Данных. Retrieved from http://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=edsbas&AN=edsbas.E4300A4
Рекомендуемая дополнительная литература
- ВИТИСКА НИКОЛАЙ ИВАНОВИЧ, & ПОПОВ РОМАН АНАТОЛЬЕВИЧ. (2014). Разработка Учебной Программы На Ассемблере Для Демонстрации Скорости Реализации Программных И Быстрых Сортировок Массивов. Retrieved from http://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=edsbas&AN=edsbas.36D9DE1C
- Комбинаторика и теория графов : учеб. пособие, Кочетков, Ю. Ю., 2009