Алгоритмы 5ML осень 2019 — различия между версиями

Материал из CSC Wiki
Перейти к:навигация, поиск
((11) 19 ноября. Хеширование.)
((13) 3 декабря. Числовые алгоритмы.)
 
Строка 147: Строка 147:
  
 
=====(13) 3 декабря. Числовые алгоритмы. =====
 
=====(13) 3 декабря. Числовые алгоритмы. =====
 +
[[Медиа:2019-12-03_Aho-Corasick.pdf| Презентация про алгоритм Ахо-Корасик]]
 +
 
=====(14) 10 декабря. NP-трудные задачи. =====
 
=====(14) 10 декабря. NP-трудные задачи. =====
 
* Алгоритм A*.
 
* Алгоритм A*.

Текущая версия на 07:31, 3 декабря 2019

Содержание

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

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

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

Каждый компонент также оценивается по 10-балльной шкале. Оценки в модулях независимы между собой и являются взвешенной суммой:

  • 1 модуль: 0.4 экзамен + 0.35 дз + 0.25 контесты
  • 2 модуль: 0.4 экзамен + 0.35 дз + 0.25 контесты

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

  1. Их не разбирают, поэтому их можно решать долго (месяц с момента выдачи, чтобы все не занялись ими 30 декабря)
  2. Они не учитываются в теоретическом максимуме при расчёте итогового балла

Балл за контест является блокирующим по оценке 4/10, то есть набрав меньше, вы не получите зачёт за курс. Домашние задания и экзамен таких ограничений не имеют.

Лекции

Лекторы:

  1. Данил Сагунов (лекции 1 – 4)
    • danilka.pro[at]gmail.com
    • Telegram: dsagunov
  2. Пётр Смирнов
    • comradepetr+hse_19fall_algo@gmail.com

Программа

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

(1) 3 сентября. Асимптотика, рекуррентные соотношения.
  • Введение. Алгоритм. Память и время как ресурсы.
  • Вычисление чисел Фибоначчи: экспоненциальный рекурсивный алгоритм, полиномиальный алгоритм, более детальный анализ.
  • O-символика как инструмент оценки ресурсов, различные асимптотики (логарифм, полином, экспонента). Примеры: простые сортировки, бинарный поиск.
  • Метод разделяй и властвуй. Сортировка слиянием.
  • Рекуррентные соотношения: основная теорема.
(2) 10 сентября. Сортировки.
  • Алгоритмы сортировки. Квадратичные сортировки.
  • Нижняя оценка Ω(n log n) для сортировки сравнениями.
  • Сортировка подсчётом, стабильность. Цифровая сортировка.
  • Интерфейс «очередь с приоритетами». Куча: определение, просеивание вниз, извлечение максимального элемента.
(3) 17 сентября. Анализ быстрой сортировки, порядковые статистики.
  • Куча: просеивание вверх, добавление нового элемента. Построение кучи за линейное время.
  • Сортировка кучей. Частичная сортировка кучей.
  • Быстрая сортировка: понятие вероятностного алгоритма, время работы в среднем.
  • Быстрая сортировка: элиминация хвостовой рекурсии, IntroSort.
  • Анализ среднего времени работы.
  • Массивы с малым количеством различных элементов, QuickSort3.
  • [На практике] Порядковые статистики. Порядковые статистики, нахождение за линейное в среднем время. Частичная сортировка.
(4) 24 сентября. Динамическое программирование — 1.
  • Анализ средней глубины рекурсии быстрой сортировки.
  • Динамическое программирование. Общие принципы динамического программирования. Кратчайшие пути в ациклических ориентированных графах.
  • Наибольшая возрастающая подпоследовательность: подзадачи, порядок на подзадачах, граф подзадач; нахождение не только длины, но и самой подпоследовательности.
  • Дискретная задача о рюкзаке с повторениями.
(5) 1 октября. Динамическое программирование — 2. Жадные алгоритмы — 1.
  • Дискретная задача о рюкзаке без повторений.
  • Редакционное расстояние.
  • Задача коммивояжёра.

Жадные алгоритмы:

  • Покрытие точек единичными отрезками.
  • Задача о выборе заявок.
  • Непрерывная задаче о рюкзаке.
  • Код Хаффмана.

На практике, динамическое программирование:

  • Быстрое возведение матрицы в степень для динамического программирования. (4.1.1 и 4.2.5)
  • Паросочетание максимального веса в деревьях. (4.1.3a)
(6) 8 октября. Жадные алгоритмы — 2. Алгоритмы на графах — 1.
  • Доказательство алгоритма Хаффмана.
  • Задача выполнимости для хорновских формул.

Графы:

  • Определения, способы хранения (матрица смежности и списки смежности).
  • Поиск в глубину (DFS), доказательство корректности. Компоненты связности.
(7) 15 октября. Алгоритмы на графах — 2. Кратчайшие пути.
  • DFS: поиск цикла, три цвета вершин, классификация рёбер.
  • Топологическая сортировка: два подхода.
  • Поиск в ширину (BFS), доказательство корректности. Лучевой поиск (beam search) (только идея).
  • Алгоритм Дейкстры, доказательство корректности. Реализации для плотных и разреженных графов.
  • Алгоритм Флойда. Оптимизация памяти до квадратичной, доказательство корректности. Проверка на наличие отрицательного цикла (доказательство оставлено как упражнение).


27 октября. Экзамен.

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

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

(8) 29 октября. Кратчайшие пути — 2. Потоки в графах.
  • Алгоритм Форда-Беллмана, оптимизация памяти до линейной. Проверка на наличие отрицательного цикла, его нахождение.
  • Потоки: мотивация, транспортная сеть, поток, остаточная сеть, величина разреза. Теорема и алгоритм Форда — Фалкерсона.
(9) 5 ноября. Минимальные остовные деревья.
  • MST: формулировка задачи.
  • Лемма о безопасном ребре (свойство разреза).
  • Алгоритм Прима, реализации за , .
  • Алгоритм Краскала. Система непересекающихся множеств.
  • Реализации СНМ: наивная, "меньшее к большему", лес. Оценки времени работы.
  • Эвристики рангов и сжатия путей.
(10) 12 ноября. Бинарные деревья поиска.
  • СНМ как лес с двумя эвристиками: амортизированная оценка .
  • Деревья поиска. Корневое дерево: бинарное дерево. Дерево поиска: поиск, вставка, удаление, поиск следующего и предыдущего элемента за время, пропорциональное высоте.
  • АВЛ-дерево: верхняя оценка на высоту, сохранение свойства при помощи малых и больших вращений.


(11) 19 ноября. Хеширование.
  • BST как упорядоченное множество. k-я порядковая статистика, lower_bound.
  • BST как словарь (ассоциативный массив).
  • AVL-дерево: реализация Add. Асимптотическая оптимальность среди BST, основанных на сравнениях.
  • Хеширование. Прямая адресация. Коллизии, методы разрешения: метод цепочек, открытая адресация (удаление) — линейный метод, двойное хеширование.
  • Оценка на метод цепочек при выполнении гипотезы простого равномерного хеширования.
  • Оценка на метод цепочек для универсального семейства хеш-функций.
  • Построение универсального семейства хеш-функций.
  • Совершенное (идеальное) хеширование: схема.
---> вы находитесь здесь <---
(12) 26 ноября. Строки.
  • Совершенное (идеальное) хеширование: доказательство.
  • Поиск подстроки в строке:
    • Наивный алгоритм.
    • Алгоритм Рабина-Карпа.
    • Z-функция, применения.
    • Префикс-функция. Алгоритм Кнута — Морриса — Пратта.
  • Алгоритм Ахо-Корасик.
  • Шинглы.
(13) 3 декабря. Числовые алгоритмы.

Презентация про алгоритм Ахо-Корасик

(14) 10 декабря. NP-трудные задачи.
  • Алгоритм A*.

Литература

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

Практика

Telegram-чат для обсуждений лекций и практик: https://t.me/joinchat/AA2G2xTf_DQL1lfqOqS_hA

Задачи

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

Артур Рязанов

Контакты:

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

Дедлайны по теоретическому ДЗ в 23:59 в день до занятия, после него работы не принимаются

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

Михаил Слабодкин

Контакты:

  • slabodkin.m[at]gmail.com
  • Telegram: slabod

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

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

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

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