Алгоритмы и структуры данных (углубленный курс)

Бакалавриат 2022/2023

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

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

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

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

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

Охват аудитории: для своего кампуса

Преподаватели: Анопренко Михаил Валентинович, Грибов Филипп Юрьевич, Курилкин Александр Сергеевич, Нечаев Сергей Петрович, Сафонов Иван Андреевич, Смирнов Иван Федорович, Фадеева Екатерина Сергеевна

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

Кредиты: 13

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

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

Аннотация

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

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

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

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

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

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

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

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

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

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

2022/2023 учебный год 2 модуль
0.429 * Контесты + 0 * Бонус + 0.214 * Контрольная работа + 0.357 * Листки
2022/2023 учебный год 3 модуль
0.3 * Контесты + 0.25 * Листки + 0.15 * Контрольная работа + 0.3 * Экзамен + 0 * Бонус
2022/2023 учебный год 4 модуль
0.3 * Контесты + 0.3 * Экзамен + 0.25 * Листки + 0.15 * Контрольная работа + 0 * Бонус

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

Авторы

Алиева Эльмира Махир Кызы

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