Бакалавриат
2021/2022
Алгоритмы и структуры данных (углубленный курс)
Статус:
Курс обязательный (Прикладная математика и информатика)
Направление:
01.03.02. Прикладная математика и информатика
Кто читает:
Базовая кафедра Яндекс
Где читается:
Факультет компьютерных наук
Когда читается:
1-й курс, 2-4 модуль
Формат изучения:
без онлайн-курса
Охват аудитории:
для своего кампуса
Преподаватели:
Артюхин Станислав Геннадьевич,
Гайдук Максим Игоревич,
Евстропов Глеб Олегович,
Ковальков Дмитрий Андреевич,
Смирнов Иван Федорович,
Третьяков Глеб Дмитриевич
Язык:
русский
Кредиты:
14
Контактные часы:
230
Программа дисциплины
Аннотация
В курсе рассматриваются основные подходы к анализу и проектированию алгоритмов и структур данных. Среди тем, изучаемых в курсе, — асимптотическая оценка сложности алгоритма в худшем случае, эффективные алгоритмы сортировки и выбора порядковых статистик, структуры данных (двоичные деревья поиска, кучи, хеш-таблицы), способы проектирования алгоритмов (разделяй и властвуй, динамическое программирование, жадная стратегия), основные алгоритмы на графах (кратчайшие пути, топологическая сортировка, компоненты связности, минимальные остовные деревья).
Цель освоения дисциплины
- Углубленное изучение принципов проектирования и анализа алгоритмов и структур данных
- Развитие навыков обоснования корректности алгоритмов, их практической реализации, теоретической и экспериментальной оценки их временной сложности
Планируемые результаты обучения
- Иметь навыки реализации алгоритмов на языках 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.
Промежуточная аттестация
- 2021/2022 учебный год 2 модульО(итог) = 0.375 · О(контесты) + 0.325 · O(листки) + 0.3 · O(экз) + O(бонус)
- 2021/2022 учебный год 3 модульО(итог) = 0.375 · О(контесты) + 0.325 · O(листки) + 0.3 · O(экз) + O(бонус)
- 2021/2022 учебный год 4 модульО(итог) = 0.375 · О(контесты) + 0.325 · O(листки) + 0.3 · O(экз) + O(бонус)
Список литературы
Рекомендуемая основная литература
- Седжвик, Р. Алгоритмы на С++ : учебное пособие / Р. Седжвик. — 2-е изд. — Москва : ИНТУИТ, 2016. — 1772 с. — Текст : электронный // Лань : электронно-библиотечная система. — URL: https://e.lanbook.com/book/100565 (дата обращения: 00.00.0000). — Режим доступа: для авториз. пользователей.
Рекомендуемая дополнительная литература
- Вирт, Н. Алгоритмы и структуры данных. Новая версия для Оберона : учебное пособие / Н. Вирт. — Москва : ДМК Пресс, 2010. — 272 с. — ISBN 978-5-94074-584-6. — Текст : электронный // Лань : электронно-библиотечная система. — URL: https://e.lanbook.com/book/1261 (дата обращения: 00.00.0000). — Режим доступа: для авториз. пользователей.