Алгоритмы и структуры данных 5SE 2021-2022

Лекции

Лектор: Александр Смаль

Контакты:

• avsmal[at]gmail.com
• Telegram: avsmal

Рабочая программа

Осень

• 9 сентября. Введение. Алгоритм. Модель вычисления RAM-машина. Память и время как ресурсы. Вычисление чисел Фибоначчи: экспоненциальный рекурсивный алгоритм, полиномиальный алгоритм, более детальный анализ. O-символика как инструмент оценки ресурсов, различные асимптотики (логарифм, полином, экспонента). Элементарные структуры данных. Массивы переменного размера: аддитивная и мультипликативная схемы аллокации.

• 16 сентября. Односвязный список, двусвязный список. Абстрактные типы данных, интерфейс и реализация. Стек, очередь, дек; моделирование на основе массива. Моделирование очереди с помощью двух стеков. Анализ учётных стоймостей операций при помощи функция потенциала, истинные и учётные стоимости. Рекуррентные соотношения. Метод ”разделяй и властвуй“. Умножение n-битовых чисел: простой рекурсивный алгоритм, улучшенный рекурсивный алгоритм. Рекуррентные соотношения: основная теорема. Двоичный поиск. Сортировка слиянием: с рекурсией и без.

• 23 сентября. Алгоритмы сортировки. Нижняя оценка $\Omega(n\log n)$ для сортировки сравнениями. Квадратичные сортировки. Сортировка с помощью кучи: очередь с приоритетами, построение кучи за линейное время, частичная сортировка.

• 30 сентября. Частичная сортировка. Сортировка подсчётом, стабильность. Цифровая сортировка. Bucket sort для равномерно распределённых вещественных чисел. Быстрая сортировка: понятие вероятностного алгоритма, время работы в среднем, анализ времени работы.

• 7 октября Быстрая сортировка: элиминация хвостовой рекурсии, IntroSort, массивы с малым количеством различных элементов, QuickSort3. Порядковые статистики, нахождение за линейное в среднем время. Медиана медиан.

• 14 октября. Динамическое программирование. Общие принципы динамического программирования. Наибольшая возрастающая подпоследовательность: подзадачи, порядок на подзадачах, граф подзадач, сравнение с рекурсивным алгоритмом; нахождение не только длины, но и самой подпоследовательности. Кратчайшие пути в ациклических ориентированных графах. Дискретная задача о рюкзаке.

• 21 октября. Динамическое программирование (продолжение). Дискретная задача о рюкзаке. Умножение матриц. Независимые множества максимального веса в деревьях. Редакционное расстояние: граф на подзадачах, нахождение кратчайшего пути в данном графе; нахождение оптимального выравнивания с использованием линейной памяти.

• 28 октября. Жадные алгоритмы. Покрытие точек единичными отрезками. Непрерывный рюкзак. Задача о выборе заявок. Максимальные независимые множества в деревьях. Код Хаффмена.

• 4 ноября. Минимальное покрывающее дерево: свойство разреза, жадная стратегия, алгоритм Прима.

• 11 ноября. Алгоритм Краскала. Система непересекающихся множеств. Представление множеств с помощью деревьев, эвристика сжатия путей, верхняя оценка $O(m \log^* n)$ на время работы m операций. Анализ учётных стоймостей операций: метод ростовщика.

• 18 ноября Альтернативные модели вычисления. Модель внешней памяти. Сортировка слиянием в модели внешней памяти. Модель cache-oblivios. Модель PRAM, вычисление максимума за константу. Модель BSP. Сортировка методом регулярного сэмплирования.

• 25 ноября. Способы хранения графов: матрица смежности, списки смежности, матрица инцидентности. Поиск в глубину. Графы и способы их представления, способы использования графов. Поиск в глубину в неориентированных графах, выделение компонент связности. Поиск в глубину в ориентированных графах: ориентированные ациклические графы, топологическая сортировка вершин. Выделение компонент сильной связности в орграфах.

• 2 декабря. Кратчайшие пути в графах. Нахождение кратчайших путей из одной вершины в невзвешенных графах, поиск в ширину. Нахождение кратчайших путей из одной вершины в графах с положительными весами, алгоритм Дейкстры, оценка времени работы при различных реализациях очереди с приоритетами (массивом, двоичной кучей, d-ичной кучей).

• 9 декабря. Нахождение кратчайших путей из одной вершины в графах, в которых есть рёбра отрицательного веса, алгоритм Беллмана-Форда, проверка наличия цикла отрицательного веса. Кратчайшие пути в ациклических ориентированных графах. Кратчайшие пути между всеми парами вершин: алгоритм Флойда-Уоршолла.

• 16 декабря. ЗАПАСНАЯ ЛЕКЦИЯ

Весна

• 15 февраля. Задачи RMQ и LCA. Динамическая задача RMQ/RSQ: оценка $O(\log n)$ для запросов суммы/минимума и изменения элемента. Дерево отрезков. Статический вариант задачи RMQ: полное предвычисление ($O(n^2)$ на предобработку, $O(1)$ на запрос), метод разреженной таблицы ($O(n \log n)$ на предобработку, $O(1)$ на запрос). Задача LCA: эйлеров обход дерева, сведение к задаче RMQ.

• 22 февраля. Деревья поиска. Корневое дерево: бинарное дерево, дерево с произвольным ветвлением, представление "левый ребёнок — правый сосед". Дерево поиска: поиск, вставка, удаление, поиск следующего и предыдущего элемента за время, пропорциональное высоте. АВЛ-дерево: верхняя оценка $O(\log n)$ на высоту, сохранение свойства при помощи малых и больших вращений.

• 1 марта. Splay-дерево. Splay-дерево: дерево, которое остаётся сбалансированным в среднем и при этом не хранит никакой дополнительной информации в вершинах; реализация основных операций через операцию splay. Верхняя оценка $O(\log n)$ на учётную стоимлость операции splay.

• 15 марта. Декартово дерево. Декартово дерево: построение декартова дерева за линейное время (при предварительно отсортированных ключах), реализация операций вставки и удаления через split и merge. Дуча: верхняя оценка $O(\log n)$ на мат. ожидание глубины. Использование неявного ключа, rope.

• 22 марта. Хеширование. Прямая адресация. Коллизии. Разрешение коллизий методом цепочек, методом последовательных проб и методом двойного хеширования. Гипотеза равномерного хеширования. Оценка времени поиска в хеш-таблице при использовании метода цепочек для гипотезы равномерного хеширования.

• 29 марта. Универсальные семейства хеш-функций. Построение универсального семейства для целочисленных ключей. Оценка времени поиска в хеш-таблице при использовании метода цепочек для универсального семейства. Совершенное хеширование с помощью универсального семейства хеш-функций.

• 5 апреля. Числовые алгоритмы. Cложение, умножение, деление длинных чисел. Арифметика по модулю: сложение, умножение, возведение в степень, алгоритм Евклида, расширенный алгоритм Евклида, деление. Проверка чисел на простоту. Генерация случайных простых чисел. Криптография: схемы с закрытым ключом, RSA.

• 12 апреля. Быстрое преобразование Фурье. Быстрое вычисление значений многочлена в точках: два способа задания многочленов — коэффициентами и значениями в точках; вычисление значений многочлена в точках методом "разделяй и властвуй"; дискретное преобразование Фурье; быстрое преобразование Фурье. Интерполяция: интерполяция в терминах матриц; матрица Вандермонда; интерполяция как домножение на обратную матрицу.

• 19 апреля. Задача линейного программирования и симплекс-метод. Линейное программирование: общий вид задачи, матричная форма и сведение между различными представлениями.

Линейное программирование: двойственность. Нахождение начальной точки. Задача о максимальном потоке. Теорема о минимальном разрезе и максимальном потоке. Алгоритм Форда-Фалкерсона.

• 26 апреля. Поиск подстроки в строке. Наивный алгоритм. Алгоритм Рабина-Капра. z-функция, префикс функция, алгоритм Кнута-Морриса-Пратта.

• 17 мая. Суффиксное дерево и суффиксный массив: идеи, определение. NP-полные задачи. Определение классов P и NP.

• 24 мая. Полиномиальные сведения. Примеры NP-полных задач. NP-полнота задачи BoundedHalting.

Литература

• Дасгупта С., Пападимитриу Х., Вазирани У. Алгоритмы.
• Т.Кормен, Ч.Лейзерсон, Р.Ривест, К.Штайн - Алгоритмы. Построение и анализ.
• А. Шень. Программирование: теоремы и задачи.
• М. А. Бабенко, М. В. Левин. Введение в теорию алгоритмов и структур данных.

Онлайн-курсы

• Алгоритмы: теория и практика. Методы
• Алгоритмы: теория и практика. Структуры данных
• Data Structures and Algorithms Specialization on Coursera
• Algorithmic Toolbox — часть специализации из предыдущего пункта

Практика

Таблица с результатами, осень.

Таблица с результатами, весна.

ПРАВИЛО

Если вы используете какие-то внешние источники, то вы должны явно сообщить об этом.

Задачи

TeX-шаблон для домашек

Условия задач, осень

Условия задач, весна

Александр Мишунин

Контакты: alexander.mishunin[at]gmail.com

Дедлайны по теоретическому ДЗ: до начала занятия для правок уже присланных ранее задач, и до начала суток, в которые будет занятие, для новых задач.

Татьяна Белова

Контакты:

• yukikomodo@gmail.com
• Telegram: @tbelova

Правила сдачи:

• Работы присылайте, пожалуйста, на почту в виде pdf-файла.

Дедлайны по теоретическому ДЗ:

• Мягкий дедлайн: пятница, 20:00.
• Жесткий дедлайн: воскресенье, 23:59.

Задачи, присланные до мягкого дедлайна, будут проверены к воскресенью. Исправления, а также новые задачи можно присылать до жесткого дедлайна.

Евгений Кравченко и Виктор Крыштапович

Контакты:

• Виктор: kry127+itmo-se-5-algo-2021@yandex.ru. Тема письма: HW <номер домашки>, <Фамилия>. В случае отправки по правильному почтовому адресу вернётся автоматический ответ вида "Спасибо! Домашняя работа принята в пул работ."

• Евгений: zzzheka97+itmo-se-5-algo-2021@gmail.com. Тема письма: HW <номер домашки>, <Фамилия>.

Правила сдачи:

• Мягкий дедлайн: пятница, 20:00. Гарантии на работы, присланные до мягкого дедлайна: будут обязательно проверены и получен фидбек до жёсткого дедлайна, исправления можно прислать к жёсткому дедлайну
• Жёсткий дедлайн: воскресенье, 23:59. Гарантия: будут обязательно проверены
• После жёсткого дедлайна: работы не проверяются с вероятностью почти наверное

Правила зачета: TBD