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

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

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

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

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

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

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

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

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

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

Преподаватели: Ахременко Григорий Андреевич, Бритков Радомир Александрович, Густокашин Михаил Сергеевич, Дерендяев Александр Борисович, Жихарева Александра Руслановна, Кищенко Ярослав Игоревич, Лосев Владимир Александрович, Ляшко Андрей Сергеевич, Минеева Екатерина Андреевна, Наймушин Вячеслав Иванович, Нурлыбай Дархан, Объедков Сергей Александрович, Погудин Глеб Александрович, Попов Максим Павлович, Сабянин Максим Анатольевич, Самоненко Илья Юрьевич, Селищев Артём Алексеевич, Строк Федор Владимирович, Филиппов Антон Сергеевич, Фолунин Владимир Александрович

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

Кредиты: 9

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

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

Аннотация

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

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

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

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

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

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

Рекурсивные алгоритмы и рекуррентные соотношения
Рекурсия и дерево рекурсии. Организация перебора вариантов (выход из лабиринта) с помощью рекурсии. Быстрое возведение в степень, бинарный поиск (с оценкой на число вызовов). Элиминация хвостовой рекурсии.
Асимптотический анализ
$O$-, $o$- и $\Theta$-формализм. Асимптотическая иерархия функций. Анализ конкретных алгоритмов: сложность вложенных циклов, сложность бинарного поиска.
Динамическое программирование
Динамическое программирование как "экономная рекурсия", подходы снизу вверх и сверху вниз. Классические применения: наибольшая возрастающая подпоследовательность, вычисление расстояния Левенштейна, целочисленная задача о рюкзаке.
Сортировки
Сортировка вставкой, сортировка слиянием, быстрая сортировка и др.
Разделяй и властвуй
Решение рекуррентных соотношений через дерево рекурсии. Выбор порядковой статистики за время $O(n)$, поиск ближайшей пары точек за время $O(n \log n)$, алгоритм Карацубы для умножения целых чисел, алгоритм Штрассена для умножения матриц.
Алгоритмы на графах
Способы представления графов: матрица смежности и списки смежности. Обход в глубину и в ширину, поиск компонент связности в неориентированных и ориентированных графах, топологическая сортировка. Алгоритмы Флойда – Уоршелла и Беллмана – Форда.
Структуры данных
Линейные структуры данных. Амортизационный анализ. Хеш-функции и хеш-таблицы. Разрешение коллизий при помощи цепочек. Открытая адресация. Двухуровневое идеальное хеширование. Деревья поиска. Сбалансированные деревья поиска. Красно-черные деревья. Динамические порядковые статистики.
Жадные алгоритмы
Основные принципы, примеры алгоритмов. Поиск кратчайших путей в графе при помощи алгоритма Дейкстры. Приоритетная очередь на основе двоичной кучи. Минимальные остовные деревья: алгоритмы Прима и Крускала. Система непересекающихся множеств.
Потоки в сетях
Задача о максимальном потоке. Максимальный поток и минимальный разрез. Алгоритмы Форда – Фалкерсона и Эдмондса – Карпа. Сведение задачи о максимальном паросочетании в двудольном графе к задаче о максимальном потоке. Устойчивые паросочетания и алгоритм Гейла – Шепли.
Конечные автоматы, регулярные выражения, контекстно-свободные грамматики
Конечные автоматы. Регулярные языки. Минимизация конечного автомата. Недетерминированные конечные автоматы. Замкнутость регулярных языков относительно регулярных операций. Регулярные выражения. Эквивалентность регулярных выражений и конечных автоматов. Три подхода к реализации регулярных выражений: детерминированный автомат, поиск с возвратами в недетерминированном автомате, имитация детерминированного автомата по недетерминированному. Нерегулярные языки. Лемма о накачке. Контекстно-свободные грамматики. Автоматы с магазинной памятью. Эквивалентность контекстно-свободных грамматик и автоматов с магазинной памятью. Построение автомата по грамматике. Лемма о накачке для контекстно-свободных языков. Разбор слов по контекстно-свободной грамматике: алгоритм динамического программирования для грамматики в нормальной форме Хомского.

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

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

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

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

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