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

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

Статус: Курс по выбору (Науки о данных)

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

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

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

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

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

Преподаватели: Бабенко Максим Александрович

Прогр. обучения: Науки о данных

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

Кредиты: 5

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

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

Аннотация

"Курс дает базовые знания в области алгоритмов и структур данных. В явном виде они, может быть, не пригодятся, но очень важны для понимания работы библиотек, алгоритмов и языков программирования. Домашние задания по курсу закрепляют полученные знания и воспитывают хороший стиль написания кода, который позволяет избежать стандартных, но от этого ничуть не менее распространенных даже у опытных разработчиков, ошибок."

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

Цель курса — обучить основам алгоритмического программирования, привить практические навыки решения задач с помощью базовых алгоритмов и структур данных, сформировать правильное представление о времени работы и эффективности различных алгоритмов и структур данных.

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

Уметь оценивать сложность алгоритмов и объём дополнительной памяти
Понимать устройство массивов переменного размера
Иметь представление об основных структурах данных
Иметь представление о персистентных структурах данных
Уметь эффективно реализовывать структуры данных в виде структур на языке С++
Владеть концепцией динамического программирования
Уметь эффективно решать практические задачи с помощью динамического программирования
Уметь эффективно реализовывать алгоритмы на языке С++
Иметь представление об основных алгоритмах сортировки. Понимать их преимущества и недостатки.
Иметь представление о быстрых методах поиска k-й порядковой статистики
Иметь представление о кучах. Уметь использовать кучи для решения практических задач
Иметь представления о хэш-функциях и их свойствах. Уметь выбирать хэш-функцию для работы с заданным типом данных.
Уметь устранять коллизии при использовании хэш-таблиц
Уметь обходить графы в ширину и в глубину
Уметь интерпретировать практические задачи в терминах теории графах, решать эти задачи с использованием графовых алгоритмах
Уметь строить и эффективно использовать деревья поиска, выбирать правильную стратегию балансировки
Уметь находить кратчайшие пути в графах
Иметь представление о задачах LCA и RMQ и об связи между ними
Уметь строить остовные деревья для графов.

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

Введение
Время и память как основные ресурсы. Модели вычислений: RAM, разрешающие деревья. Сложность на заданном входе, сложность в худшем случае, сложность в среднем случае, рандомизированная сложность. Нижняя оценка на число сравнений при сортировке в модели разрешающих деревьев.Учетная стоимость операций, метод потенциалов, банковский метод анализа сложности. Анализ двоичного счетчика. Массивы переменного размера.
Динамическое программирование
Динамическое программирование. Задача о наибольшей возрастающей подпоследовательности. Задача об оптимальном порядке перемножения матриц.
Введение в структуры данных
Реализация очереди на паре стеков с константной учетной сложностью. Динамические минимумы-максимумы в стеках и очередях. Персистентные структуры данных. Видны персистентности. Модель вычислений Pointer Machine. Персистентные стеки.
Сортировки
"Сортировка слиянием (Merge-Sort). Inplace-разновидность. Galloping в бинарном поиске. Оптимальное по числу сравнений слияние двух упорядоченных последовательностей. Задача о длиннейшей возрастающей подпоследовательности. Быстрая сортировка (Quick-Sort). Способы выбора разделяющего элемента. Элиминация хвостовой рекурсии. Порядковые статистики. Рандомизированный алгоритм Quick-Select. Детермининированный алгоритм поиска (метод ""медианы медиан"")."
Кучи
Кучи: основные определения и свойства. Операции Sift-Down и Sift-Up. Бинарные и k-ичные кучи. Построение кучи за линейное время. Алгоритмы сортировки Heap-Sort и Intro-Sort. Частичная сортировка с помощью кучи и поиска порядковой статистики.
Хэширование
"Хеш-функции. Коллизии. Разрешение коллизий методом цепочек. Гипотеза простого равномерного хеширования, оценка средней длины цепочки. Универсальные семейства хеш-функций, оценка средней длины цепочки. Построение универсального семейства для целочисленных ключей. Совершенные хеш-функции. Построение совершенной хеш-функции методом двухуровненого хеширования. Построение совершенной хеш-функции методом ациклических графов. Фильтр Блюма (Bloom filter). Оценка вероятности ложноположительного срабатывания. Locality-sensitive hashing. Семейства locality-sensitive хеш-функций и общий алгоритм. Семейство для расстояния Хэмминга. Потоковые алгоритмы. Задача подсчета количества вхождений в потоке. Turnstile и cash-register модели. Count-min sketch. Алгоритм Misra-Gries. Locality-sensitive hashing. Семейства для углового расстояния, евклидова расстояния. Asymmetric LSH - приближенный поиск точки в множестве с максимальным скалярным произведением с точкой запроса."
Графы
"Графы: основные определения и способы представления в алгоритмах. Обход в ширину. Обход в глубину. Лемма о белом пути. Проверка на ацикличность и топологическая сортировка. Сильно связные компоненты и топологическая сортировка конденсации. Классификация ребер при обходе в глубину в ориентированном и неориентированном графах. Точки сочленения: определение и нахождение с помощью обхода в глубину. Эйлеров обход: проверка существования и построение с помощью обхода в глубину."
Деревья поиска
"Деревья поиска. Вставка и удаление элементов. Inorder-обход дерева. Обход Морриса для бинарных деревьев. Красно черные деревья: определение и основные свойства. Реализация операций вставки для красно-черного дерева. Splay-деревья. Операция splay: zig, zig-zig и zig-zag шаги. Реализация операций вставки, удаления, слияния и разделения для splay-деревьев. Дучи (treaps). Единственность дучи для заданного набора различных ключей и приоритетов. Логарифмическая оценка матожидания высоты дучи. Операции слияния и разделения для дуч. Операции вставки и удаления элементов для дуч."
Кратчайшие пути в графах
"Кратчайшие пути в графах. Оценки расстояний и их релаксация. Алгоритмы БеллманаФорда, Флойда и Дийкстры. Потенциалы. Критерий консервативности длин. Алгоритм Флойда. Алгоритм Джонсона. Двухсторонний алгоритм Дийкстры. Алгоритм A*."
LCA & RMQ
Задачи LCA и RMQ. Решение RMQ с помощью sparse table. Сведение LCA к RMQ (алгоритм Фарах-Колтона-Бендера). Сведение RMQ к LCA.
Графы: продвинутые темы
"Остовы минимального веса. Лемма о минимальном ребре в разрезе. Алгоритмы Краскала и Прима. Системы непересекающихся множеств. Реализация с использованием леса. Ранги вершин, эвристика ранга. Логарифмическая оценка ранга через количество элементов. Эвристика сжатия путей. Оценка учетной стоимости операций (без доказательства). Алгоритм Борувки. Комбинация алгоритма Борувки и алгоритма Прима. Алгоритм Таржана для задачи offline LCA. Алгоритм hub labels для задачи о кратчайших путях."

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

Домашняя работа 1
Домашняя работа 2
Экзамен

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

Промежуточная аттестация (2 модуль)
0.3 * Домашняя работа 1 + 0.3 * Домашняя работа 2 + 0.4 * Экзамен

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