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

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

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

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

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

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

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

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

Лекции

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

Программа

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

(1) 7 сентября. Асимптотика, рекуррентные соотношения.

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

(2) 14 сентября. Сортировки.

• Нижняя оценка Ω(n log n) для сортировки сравнениями.
• Сортировка подсчётом, стабильность. Цифровая сортировка.
• Интерфейс «очередь с приоритетами». Куча: определение, просеивание вниз, извлечение максимального элемента.
• Куча: просеивание вверх, добавление нового элемента. Сортировка кучей.

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

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

(4) 28 сентября. Быстрая сортировка — 2. Динамическое программирование — 1.

• Быстрая сортировка. Корректность inplace-версии. Частичная сортировка.
• Средняя глубины рекурсии (без доказательства).
• Элиминация хвостовой рекурсии. IntroSort.

Динамическое программирование:

• Общие принципы динамического программирования. Кратчайшие пути в ациклических ориентированных графах.
• Наибольшая возрастающая подпоследовательность: подзадачи, порядок на подзадачах, граф подзадач; нахождение не только длины, но и самой подпоследовательности.

На практике:

• Быстрое возведение матрицы в степень для динамического программирования.
• Паросочетание максимального веса на деревьях.

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

Динамическое-программирование — 2:

• Дискретная задача о рюкзаке с повторениями.
• Дискретная задача о рюкзаке без повторений.
• Редакционное расстояние.
• Задача коммивояжёра.

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

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

(6) 12 октября. Код Хаффмана. Алгоритмы на графах — 1.

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

• Непрерывная задаче о рюкзаке — доказательство
• Код Хаффмана.

Графы:

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

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

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

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

(7) 30 октября. Кратчайшие пути в графах.

Невзвешенные графы:

• Поиск в ширину (BFS), доказательство корректности.

Взвешенные графы:

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

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

• Доказательство корректности алгоритмов ФБ, Флойда.
• MST.

(9) 9 ноября. СНМ с двумя эвристиками. Потоки в графах.

• Оценка времени работы СНМ с двумя эвристиками.
• Потоки в графах. Конспект аналогичной лекции.

(10) 16 ноября. Потоки-2. Бинарные деревья поиска.

• Потоки: алгоритм Эдмондса-Карпа и масштабирования.
• Бинарные деревья поиска.

(11) 23 ноября. Алгоритмы на строках, хеширование.

Строки:

• Z-функция
• Префикс-функция и алгоритм Кнута-Морриса-Пратта
• Полиномиальное хеширование
• Хеш-таблица

(12) 30 ноября. Хеширование-2. Алгоритм Ахо-Корасик.

• Хеширование
• Бор и алгоритм Ахо-Корасик Презентация

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

• Теория чисел: 1, 2

(14) 14 декабря.

• Теория сложности: 1, 2

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

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

Литература

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

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

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

Практика

Задачи

Условия задач | Разборы | Разборы контестов

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

TeX-шаблон для домашек

Сергей Копелиович

Контакты:

• Почта для домашек: burunduk30@gmail.com, в теме письма должна быть подстрока SPb HSE HW

Правила сдачи:

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

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

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

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

Владислав Кораблинов

Контакты:

• vladislav.korablinov+hse_20_algo@gmail.com
• Telegram: ladine0n

Правила сдачи:

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

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

• мягкий дедлайн в пятницу в 22:00, задачи, присланные до него, гарантированно проверяются как минимум 1 раз до жесткого дедлайна
• жёсткий дедлайн в воскресенье в 23:59, после него до начала занятия можно присылать только исправления по задачам, по которым было написано что-то разумное (в ваших интересах прислать пораньше, чтобы я успел посмотреть и было понятно, что исправлять)

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