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

На практике: декартово дерево: построение декартова дерева за линейное время (при предварительно отсортированных ключах), использование неявного ключа, rope.

(11) 19 ноября. Хеширование.
(12) 26 ноября. Строки.
(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