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

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

Содержание

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

Оценка курса выставляется по 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. Потоки в графах.
  • Алгоритм Форда-Беллмана, оптимизация памяти до линейной. Проверка на наличие отрицательного цикла, его нахождение. (Конспект аналогичной лекции: секции 4.1 и 4.2.)
  • Потоки: мотивация, транспортная сеть, поток, остаточная сеть, величина разреза. Теорема и алгоритм Форда — Фалкерсона. (Конспект аналогичной лекции: секция 3.)
(9) 5 ноября. Минимальные остовные деревья.
  • MST: формулировка задачи.
  • Лемма о безопасном ребре (свойство разреза).
  • Алгоритм Прима, реализации за , .
  • Алгоритм Краскала. Система непересекающихся множеств.
  • Реализации СНМ: наивная, "меньшее к большему", лес. Оценки времени работы.
  • Эвристики рангов и сжатия путей.
(10) 12 ноября. Бинарные деревья поиска.
  • СНМ как лес с двумя эвристиками: амортизированная оценка .
  • Деревья поиска. Корневое бинарное дерево. Дерево поиска: поиск, вставка, удаление, поиск следующего и предыдущего элемента за время, пропорциональное высоте.
  • AVL-дерево: верхняя оценка на высоту, сохранение свойства при помощи малых и больших вращений.
(11) 19 ноября. Хеширование.
  • BST как упорядоченное множество. k-я порядковая статистика, lower_bound.
  • BST как словарь (ассоциативный массив).
  • AVL-дерево: реализация Add. Асимптотическая оптимальность среди BST, основанных на сравнениях.
  • Хеширование. Прямая адресация. Коллизии, методы разрешения: метод цепочек, открытая адресация (удаление) — линейный метод, двойное хеширование.
  • Оценка на метод цепочек при выполнении гипотезы простого равномерного хеширования.
  • Оценка на метод цепочек для универсального семейства хеш-функций.
  • Построение универсального семейства хеш-функций.
  • Совершенное (идеальное) хеширование: схема.
(12) 26 ноября. Алгоритмы на строках.
  • Совершенное (идеальное) хеширование: доказательство.
  • Поиск подстроки в строке
    • Наивный алгоритм
    • Z-функция, применение
    • Префикс-функция. Алгоритм Кнута — Морриса — Пратта
(13) 3 декабря. Алгоритм Ахо-Корасик. Числовые алгоритмы.

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

Числовые алгоритмы

  • Модулярная арифметика: отношение сравнимости, свойства, деление и обратный элемент по модулю
  • Обратный элемент по простому модулю: малая теорема Ферма, быстрое возведение в степень
  • Алгоритм Евклида, оценка оценка количества арифметических операций
  • Обратный элемент по произвольному модулю: расширенный алгоритм Евклида
  • Шифрование. Закрытый и открытый ключи. Мотивация использования открытого ключа
  • Теорема Эйлера
  • Алгоритм RSA
(14) 10 декабря. Линейное программирование. NP-трудные задачи.
Линейное программирование
  • Линейная программа. Избавление от =, ⩾, min
  • Симплекс-метод (без строгих доказательств)
    • Максимум достигается в вершине
    • Лемма о локальной максимальности
    • Схема алгоритма, время работы в худшем и в среднем случаях
  • Другие методы решения ЛП: метод эллипсоидов, метод внутренней точки (просто упомянуты)
  • Примеры решения задач с помощью ЛП: максимальный поток, максимальный поток минимальной стоимости, непрерывный рюкзак. Дискретный рюкзак — целочисленное ЛП (ILP)
NP-трудные задачи
  • Задачи поиска
  • Класс NP. Примеры задач: гамильтонов путь, задача о рюкзаке, кратчайший путь
  • Класс P
  • Полиномиальные сведе́ния
    • Свойства: транзитивность,
    • Определение NP-полноты (NPC)
  • Первые NP-полные задачи: Circuit SAT (нестрогое доказательство), 3SAT, SAT (теорема Кука — Левина)
  • Сравнение сложности похожих задач (без доказательств)
    • P: LP, MST, непрерывный рюкзак, эйлеров путь, кратчайший путь, 2SAT/SAT для хорновских формул
    • NPC: ILP, TSP (путь — это дерево с ограничением на степени), дискретный рюкзак, гамильтонов путь, длиннейший путь, 3SAT/SAT
    • Задача проверки на простоту лежит в P, разложение на множители — неизвестно где
  • P ?= NP
  • Решение NP-полных задач
    • Точные алгоритмы, SAT-солверы
    • Параметризованные алгоритмы
    • Приближённые алгоритмы

29 декабря. Экзамен.

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

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

Литература

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

Практика

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