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

Course type:: Compulsory course

When:: 1 year, 2, 4 module

Instructors

Artyukhin, Stanislav G.

Evstropov, Gleb O.

Резников Григорий Михайлович

Smirnov, Ivan

Третьяков Глеб Дмитриевич

Фельдшеров Святослав Викторович

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

Аннотация

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

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

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

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

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

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

Вводная лекция. Структура курса и оргвопросы. Введение в теорию вероятностей (конечные вероятностные пространства).
Введение в теорию вероятностей (математическое ожидание, пример анализа алгоритмов).
Модель вычислений. Методы анализа алгоритмов, примеры доказательства корректности и оценки времени работы.
Эффективные алгоритмы сортировки сравнениями: сортировка слиянием, быстрая сортировка. Оценка снизу на сложность сортировки сравнениями. Поиск порядковой статистики. Метод бинарного поиска. Алгоритмы сортировки, обращающиеся к непосредственным значениям элементов: сортировка подсчётом, цифровая сортировка, корзинная сортировка.
Сортировка случайных данных. Модель вычислений с использованием внешней памяти. Сортировка во внешней памяти.
Простые структуры данных: односвязный и двусвязный списки, стек, очередь, дек. Двоичные и k-ичные кучи. Биномиальные кучи.
Амортизационный анализ. Метод кредитов и метод потенциалов. Динамический массив и сливание двоичных куч
Фибоначчиевы кучи.
Хеширование. Постановка задачи, парадокс дней рождений. Полиномиальный хеш.
Хеш-таблицы с открытой и закрытой адресацией. Стратегии удаления элементов и мас- штабирования таблиц. Фильтр Блума.
Бинарные деревья поиска. Сбалансированные деревья. Декартово дерево.
2-3 деревья и B-деревья.
Частичные суммы, разреженные таблицы, деревья отрезков. Метод сканирующей прямой.
Задачи LCA и LA. Сведение LCA к RMQ и наоборот. Метод четырёх русских
Персистентность и персистентные структуры данных.
Перебор комбинаторных объектов. Динамическое программирование. Генерация комбинаторных объектов.
Динамическое программирование на ацикличных графах, подотрезках, поддеревьях и подмножествах. Метод meet-in-the-middle.
Ускорение вычислений с помощью битовых операций. Эффективное использование памяти в задачах динамического программирования.
Методы асимптотических и эвристических оптимизаций перебора. Эффективный перебор в играх с нулевой суммой.
Теория графов. Обходы в глубину и ширину, топологическая сортировка, компоненты сильной связности.
Мосты и точки сочленения. Компоненты рёберной и вершинной двусвязности.
Кратчайшие пути во взвешенных графах. Алгоритмы Форда-Беллмана, Флойда-Уоршелла и Дейкстры.
Задача о минимальном остове. Лемма о безопасном ребре. Алгоритмы Прима, Борувки и Краскалла
Система непересекающихся множеств. Критерии оптимальности остовного дерева.
Методы работы с графами во внешней памяти.
Задача поиска шаблона в тексте. Префикс-функция и z-функция. Автомат префикс-функции.
Бор-дерево и сжатое бор-дерево. Алгоритм Ахо-Корасик.
Суффиксный массив и lcp.
Алгоритм Укконена.
Паросочетания в двудольном графе. Алгоритм Куна. Теорема Кёнига-Эгервари.
Задача о максимальном потоке. Теорема Форда-Фалкерсона.
Полиномиальные алгоритмы решения задачи о максимальном потоке. Алгоритм Эдмондса- Карпа, техника масштабирования, алгоритм Диница.
Стоимостной поток. Определения и жадный алгоритм. Алгоритм Дейкстры с потенциалами Джонсона.
Вычислительная геометрия. Основные примитивы (точка, прямая, окружность) и базовые операции работы с ними.
Проверка принадлежности точки невыпуклому многоугольнику. Алгоритм Грэхема по-строения выпуклой оболочки. Некоторые алгоритмы быстрой геометрии.
Задача поиска двух ближайших точек. Задача поиска двух наиболее удалённых точек. Пересечение полуплоскостей.
Формальные языки. Иерархия языков. Определения РВ, ДКА, НКА, eps-НКА. Лемма о накачке. Автоматы с магазинной памятью.
Эквивалентность РВ, ДКА, НКА. Алгоритмы минимизации автомата.
Классы задач L, P, NP, co-NP, NPC, co-NPC, PSPACE, EXPTIME, BPP, ZP, RP. Некоторые соотношения данных классов.
Проблема P = NP, теорема Кука-Левина. NP-полнота некоторых задач.
Численные методы интегрирования. Метод Монте-Карло.
Численные методы оптимизации. Троичный поиск, градиентный и покоординатный спуск, метод Ньютона.
Эвристические методы оптимизации: имитация отжига, генетический алгоритм.
Введение в теоретико-числовые алгоритмы. Быстрое возведение в степень, расширенный алгоритм Евклида, решето Эратосфена и линейное решето, факторизация за O(/n). Первообразный корень и дискретное логарифмирование.
Тест на простоту Миллера-Рабина и шифрование RSA.
Алгоритм Карацубы. Быстрое умножение матриц. Метод деревьев рекурсии и основная теорема.
Быстрое преобразование Фурье.
Приближённые алгоритмы. Константные приближения в некоторых задачах. Дерандомизация.
Построение приближённых алгоритмов с помощью задачи линейного программирования.
Задача о покрытии множества. Алгоритм Каргера-Штайна.
Стриминговые алгоритмы. Задача heavy-hitters, приближённое вычисление порядковых статистик и суммы к окне.
Стриминговые алгоритмы. Подсчёт количества различных элементов, count-sketch.

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

Контесты
Листки
Контрольные
Экзамен
Экзамен проходит в письменной форме с синхронным проторингом. Технические требования: web-камера, микрофон, наушники / колонки, Zoom.

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

Промежуточная аттестация (2 модуль)
0.375 * Контесты + 0.325 * Листки + 0.3 * Экзамен
Промежуточная аттестация (4 модуль)
0.3 * Контесты + 0.15 * Контрольные + 0.25 * Листки + 0.3 * Экзамен

Bachelor’s Programme 'Applied Mathematics and Information Science'

Algorithms and Data Structures

Instructors

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

Аннотация

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

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

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

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

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

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

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

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