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

Материал из CSC Wiki
Перейти к:навигация, поиск

Содержание

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

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

  1. Экзамен .
  2. Теоретические домашние задания , сдача всех обязательных соответствует значению , значение может быть больше единицы.
  3. Контесты , сдача всех обязательных соответствует значению , значение может быть больше единицы.

Оценка за модуль вычисляется следующим образом: , где — округление к ближайшему целому.

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

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

  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 декабря. Экзамен.

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

---> вы находитесь здесь <---

Литература

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

Практика

Задачи

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

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

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

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

Аудитория 2.3.

Контакты:

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

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

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

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

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

Аудитория 168.

Контакты:

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

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

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

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

Аудитория 170.

Контакты:

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

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

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