Delivered at:: Joint Department with Yandex (Big Data and Information Retrieval School)

Course type:: Compulsory course

When:: 1 year, 2, 4 module

Instructors

Borzunov, Alexander

Гаглоев Александр Владимирович

Gustokashin, Mikhail

Ежкин Вячеслав Сергеевич

Кравчук Никита Валерьевич

Кузнецов Максим Анатольевич

Kucherenko, Demid

Лосев Владимир Александрович

Мельников Сергей Вячеславович

Mineeva, Ekaterina

Михеев Александр Георгиевич

Наймушин Вячеслав Иванович

Нурлыбай Дархан

Погодина Екатерина Валерьевна

Popov, Maksim

Сабянин Максим Анатольевич

Samonenko, Ilya

Tekhazheva, Sofia

Федоров Михаил Антонович

Фолунин Владимир Александрович

Шевченко Дмитрий Васильевич

Яковлев Даниил Дмитриевич

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

Аннотация

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

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

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

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

Знать о наиболее важных алгоритмах и структурах данных и основных принципах их проектирования и анализа
Уметь обосновывать корректность алгоритмов, проводить теоретическую и экспериментальную оценки их временной сложности
Уметь формализовать условие задачи, требующей алгоритмического решения, разбить задачу на подзадачи, сформулировать эффективный алгоритм решения задачи
Иметь навыки реализации алгоритмов на языках 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 * Экзамен

Bachelor’s Programme 'Applied Mathematics and Information Science'

Algorithms and Data Structures

Instructors

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

Аннотация

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

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

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

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

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

Список литературы

Рекомендуемая основная литература

Рекомендуемая дополнительная литература