Алгоритмы и структуры данных

Бакалавриат 2020/2021

Лучший по критерию «Полезность курса для Вашей будущей карьеры»

Лучший по критерию «Полезность курса для расширения кругозора и разностороннего развития»

Статус: Курс обязательный (Прикладная математика и информатика)

Направление: 01.03.02. Прикладная математика и информатика

Кто читает: Базовая кафедра Яндекс

Где читается: Факультет компьютерных наук

Когда читается: 1-й курс, 2, 4 модуль

Формат изучения: без онлайн-курса

Преподаватели: Борзунов Александр Александрович, Гаглоев Александр Владимирович, Густокашин Михаил Сергеевич, Ежкин Вячеслав Сергеевич, Кравчук Никита Валерьевич, Кузнецов Максим Анатольевич, Кучеренко Демид Сергеевич, Лосев Владимир Александрович, Мельников Сергей Вячеславович, Минеева Екатерина Андреевна, Михеев Александр Георгиевич, Наймушин Вячеслав Иванович, Нурлыбай Дархан, Погодина Екатерина Валерьевна, Попов Максим Павлович, Сабянин Максим Анатольевич, Самоненко Илья Юрьевич, Техажева София Андреевна, Федоров Михаил Антонович, Фолунин Владимир Александрович, Шевченко Дмитрий Васильевич, Яковлев Даниил Дмитриевич

Язык: русский

Кредиты: 9

Контактные часы: 144

Полная версия программы учебной дисциплины

Аннотация

В курсе рассматриваются основные подходы к анализу и проектированию алгоритмов и структур данных. Среди тем, изучаемых в курсе, — асимптотическая оценка сложности алгоритма в худшем случае, эффективные алгоритмы сортировки и выбора порядковых статистик, структуры данных (двоичные деревья поиска, кучи, хеш-таблицы), способы проектирования алгоритмов (разделяй и властвуй, динамическое программирование, жадная стратегия), основные алгоритмы на графах (кратчайшие пути, топологическая сортировка, компоненты связности, минимальные остовные деревья).

Цель освоения дисциплины

ознакомление студентов с основными принципами проектирования и анализа алгоритмов и структур данных
развитие навыков обоснования корректности алгоритмов, их практической реализации, теоретической и экспериментальной оценки их временной сложности

Планируемые результаты обучения

Знать о наиболее важных алгоритмах и структурах данных и основных принципах их проектирования и анализа
Уметь обосновывать корректность алгоритмов, проводить теоретическую и экспериментальную оценки их временной сложности
Уметь формализовать условие задачи, требующей алгоритмического решения, разбить задачу на подзадачи, сформулировать эффективный алгоритм решения задачи
Иметь навыки реализации алгоритмов на языках Python и C++

Содержание учебной дисциплины

Рекурсивные алгоритмы и рекуррентные соотношения
Рекурсия и дерево рекурсии. Организация перебора вариантов (выход из лабиринта) с помощью рекурсии. Быстрое возведение в степень, бинарный поиск (с оценкой на число вызовов). Элиминация хвостовой рекурсии.
Асимптотический анализ
$O$-, $o$- и $\Theta$-формализм. Асимптотическая иерархия функций. Анализ конкретных алгоритмов: сложность вложенных циклов, сложность бинарного поиска.
Динамическое программирование
Динамическое программирование как "экономная рекурсия", подходы снизу вверх и сверху вниз. Классические применения: наибольшая возрастающая подпоследовательность, вычисление расстояния Левенштейна, целочисленная задача о рюкзаке.
Сортировки
Сортировка вставкой, сортировка слиянием, быстрая сортировка и др.
Разделяй и властвуй
Решение рекуррентных соотношений через дерево рекурсии. Выбор порядковой статистики за время $O(n)$, поиск ближайшей пары точек за время $O(n \log n)$, алгоритм Карацубы для умножения целых чисел, алгоритм Штрассена для умножения матриц.
Алгоритмы на графах
Способы представления графов: матрица смежности и списки смежности. Обход в глубину и в ширину, поиск компонент связности в неориентированных и ориентированных графах, топологическая сортировка. Алгоритмы Флойда – Уоршелла и Беллмана – Форда.
Структуры данных
Линейные структуры данных. Амортизационный анализ. Хеш-функции и хеш-таблицы. Разрешение коллизий при помощи цепочек. Открытая адресация. Двухуровневое идеальное хеширование. Деревья поиска. Сбалансированные деревья поиска. Красно-черные деревья. Динамические порядковые статистики.
Жадные алгоритмы
Основные принципы, примеры алгоритмов. Поиск кратчайших путей в графе при помощи алгоритма Дейкстры. Приоритетная очередь на основе двоичной кучи. Минимальные остовные деревья: алгоритмы Прима и Крускала. Система непересекающихся множеств.
Хэш таблицы
Хэш функции, хэш значения, коллизии, прямая адресация (open hashing), сцепление элементов (chaining). Коэффициент заполнения (load coefficient), равномерное хеширование (simple uniform hashing). Свойства хорошей хэш функции, способы построения хеш функций, двойное хэширование, примеры хэш функций. Фильтр Блума (Bloom Filter), Cuckoo filter и их разновидности. Хэш таблицы в стандартной библиотеке C++. Шаблонный класс std::unordered_map.
Деревья
Формальное определение множества, пары и дерева (краткая математическая справка). Деревья и их представление. Двоичные деревья, деревья с произвольным ветвлением. Преобразование дерева в двоичное дерево. Двоичное дерево поиска. Свойство упорядоченности. Способы обхода двоичного дерева поиска. Поиск заданного элемента в двоичном дереве поиска, поиск минимума и максимума, поиск следующего и предыдущего элемента. Добавление и удаление элементов в двоичном дереве поиска. Динамические множества с сохранением предыдущих версий. Устройство жесткого диска. B-деревья, R-деревья, деревья отрезков (промежутков): определение, предназначение, основные операции, разновидности этих деревьев.

Элементы контроля

Домашнее задание (2 модуль)
Контрольная работа 1
Работа на семинаре 1
Экзамен (письменный) 1
Домашнее задание (4 модуль)
Контрольная работа 2
Работа на семинаре 2
Экзамен
Экзамен проводится дистанционно через Zoom. Технические требования: web-камера, микрофон, наушники / колонки, Zoom.

Промежуточная аттестация

Промежуточная аттестация (2 модуль)
0.3 * Домашнее задание (2 модуль) + 0.2 * Контрольная работа 1 + 0.1 * Работа на семинаре 1 + 0.4 * Экзамен (письменный) 1
Промежуточная аттестация (4 модуль)
0.4 * Домашнее задание (4 модуль) + 0.33 * Промежуточная аттестация (2 модуль) + 0.07 * Работа на семинаре 2 + 0.2 * Экзамен

Программа дисциплины