Алгоритмы 5ML осень 2021

Правила сдачи курса

Оценка курса выставляется по 10-балльной шкале и состоит из 3 компонентов:

1. Экзамен $0\leqslant e\leqslant 1$.
2. Теоретические домашние задания $h_{t}$, сдача всех обязательных соответствует значению $h_{t}=1$, значение может быть больше единицы.
3. Контесты $h_{c}$, сдача всех обязательных соответствует значению $h_{c}=1$, значение может быть больше единицы.

Оценка за модуль вычисляется следующим образом: $\min(\lfloor (h_{t}+h_{c}+e)\cdot 10/3\rceil ,10)$, где $\lfloor \cdot \rceil$ — округление к ближайшему целому.

Оценки в модулях независимы между собой, каждая является взвешенной суммой компонентов.

Кроме обязательных задач бывают и дополнительные. Отличия:

1. Они не учитываются в теоретическом максимуме при расчёте итогового балла

Лекции

Лектор: Пётр Смирнов

Программа

Конспект (не в точности соответствует лекциям)

Первый модуль

(1) 6 сентября. Асимптотика. Сортировка слиянием.

• Введение. Алгоритм. Память и время как ресурсы.
• O-символика как инструмент оценки ресурсов, различные асимптотики (логарифм, полином, экспонента).
• Задача поиска в множестве: наивное решение, решение сортировкой выбором и бинарным поиском.
• Метод «разделяй и властвуй». Сортировка слиянием.

(2) 13 сентября. Куча.

• MergeSort без перевыделений памяти, MergeSort без рекурсии
• Мастер-теорема — основная теорема о рекуррентных соотношениях.
• Интерфейс «очередь с приоритетами». Наивные реализации
• Куча. Определение, операции, сортировка кучей.
• [На практике] Inplace Build. Build за O(n). Частичная сортировка кучей.

(3) 20 сентября. Быстрая сортировка, порядковые статистики.

• Доказательство корректности операций в куче.
• Изменение элемента в куче, удаление произвольного элемента. Ленивое удаление.

• Быстрая сортировка: понятие вероятностного алгоритма, время работы в среднем.
• Анализ среднего времени работы.
• [На практике] Порядковые статистики. Нахождение за линейное в среднем время. Частичная сортировка.
• [На практике] QuickSort3.

(4) 27 сентября. Сортировки: финал.

• Inplace QuickSort. Корректность.
• Элиминация хвостовой рекурсии.
• IntroSort.
• Сравнение сортировок. Стабильность. Кеш.
• Нижняя оценка Ω(n log n) для сортировки сравнениями.
• Сортировка подсчётом, стабильность. Цифровая сортировка.

(5) 4 октября. Динамическое программирование.

• Рекурсия, мемоизация, ленивое ДП. ДП назад.
• Составные части решения с помощью ДП.

Задачи:

• Задача «Калькулятор»/«Кузнечик».
• Наибольшая возрастающая подпоследовательность за O(n^2).
• Редакционное расстояние.
• Дискретная задача о рюкзаке с повторениями.

(6) 11 октября. Динамическое программирование по подмножествам. Жадные алгоритмы.

• Динамическое программирование по подмножествам. Задача коммивояжёра.
• Непрерывная задача о рюкзаке.
• Код Хаффмана. (Без доказательства оптимальности.)

(Э) 24 октября. Экзамен.

Список вопросов

Второй модуль

(7) 25 октября. Алгоритмы на графах.

• Определения, способы хранения графов (матрица смежности и списки смежности).
• Поиск в глубину (DFS), доказательство корректности. Компоненты связности.
• DFS: поиск цикла, три цвета вершин, классификация рёбер.
• Топологическая сортировка, два подхода: с очередью, с помощью DFS.
• Поиск в ширину (BFS).

Доски с лекции: DFS1, DFS2, BFS.

(8) 1 ноября. Кратчайшие пути во взвешенных графах.

• Алгоритм Дейкстры, доказательство корректности. Реализации для плотных и разреженных графов.
• Алгоритм Форда — Беллмана. Оптимизация памяти до линейной. На практике: поиск отрицательного цикла.
• Алгоритм Флойда — Уоршелла. Оптимизация памяти до квадратичной. На практике: поиск отрицательного цикла.

Доски с лекции: алгоритм Дейкстры, алгоритмы Форда-Беллмана и Флойда-Уоршелла.

(9) 8 ноября. Минимальное остовное дерево.

• Минимальное остовное дерево (MST). Лемма о безопасном ребре (лемма о разрезе).
• Алгоритм Прима и алгоритм Краскала.
• Система непересекающихся множеств (СНМ, DSU):
  • на векторах, оптимизация «меньшее к большему»;
  • с помощью леса, ранговая эвристика и эвристика сжатия путей.

Доски с лекции: минимальное остовное дерево, система непересекающихся множеств.

(10) 15 ноября. Строки. Z-функция. Префикс-функция и КМП.

• Поиск подстроки в строке. Наивное решение.
• Z-функция. Поиск подстроки в строке.
• Префикс-функция. Алгоритм Кнута — Морриса — Пратта. Оптимизация памяти.

Доски с лекции: наивный поиск и Z-функция, префикс-функция и КМП.

(11) 22 ноября. Хеширование строк. Хеш-таблица. Бор.

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

Доски с лекции: хеширование, хеш-таблицы, бор.

(12) 29 ноября. Алгоритм Ахо — Корасик. Теория чисел.

• Алгоритм Ахо — Корасик. Слайды, доска.
• Теория чисел: проверка на простоту, разложение на простые множители, решето Эратосфена, алгоритм Евклида. Доска.

(13) 6 декабря. Теория чисел — 2.

• Теория чисел: расширенный алгоритм Евклида, быстрое возведение в степень, модульная арифметика, деление по простому и произвольному модулю.
• Шифрование, RSA.

Доска.

(14) 13 декабря. Оценки для хеширования. Бинарные деревья поиска.

• Универсальное семейство хеш-функций. Время работы хеш-таблицы с закрытой адресацией.
• Вероятности коллизий полиномиального хеширования строк в двух сеттингах: строки случайные, строки произвольные.
• Бинарные деревья поиска. Основные операции.
• AVL-дерево. Добавление с сохранением AVL-свойства.

Доски с лекции: оценки для хеширования, бинарные деревья поиска.

(Э) 27 декабря. Экзамен.

Список вопросов

Литература

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

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

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

Практика

Задачи

Условия задач

Технические советы для написания кода в контестах

Решения теордз нужно присылать в виде pdf-файла на почту для домашек, указанную ниже. Можно использовать TeX-шаблон для домашек.

[1] Никита Гаевой

Аудитория 2.3.

Контакты:

• Telegram/VK для вопросов (если не хочется писать на почту): @nikgaevoy
• Тема для писем с домашками: SPb HSE HW Masters Algorithms
• Почта для домашек: nikgaevoy@gmail.com

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

• мягкий дедлайн в субботу в 12:00
• жёсткий дедлайн в понедельник в 23:59, исправления можно присылать до начала пары

Таблица с результатами

[2] Даниил Орешников

Аудитория 168.

Контакты:

• Telegram: @doreshnikov
• Почта для домашек: hsem.algo.2021.group2+hwXX@gmail.com

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

• мягкий дедлайн в воскресенье в 23:59
• жёсткий дедлайн в понедельник в 23:59

Таблица с результатами

[3] Данил Сагунов

Аудитория 170.

Контакты:

• Почта для домашек: danilka.pro@gmail.com
• Telegram: @dsagunov
• Тема для писем с домашками: [Algorithms HSE HW]

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

• мягкий дедлайн в воскресенье в 23:59
• жёсткий дедлайн в понедельник в 23:59

Таблица с результатами