Просмотр исходного текста страницы Алгоритмы 5ML осень 2020

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

Оценка курса выставляется по 10-балльной шкале и состоит из 3 компонентов:
# Экзамен
# Теоретические домашние задания. Балл — доля всех сданных обязательных задач.
# Контесты. Балл за контесты — доля всех сданных обязательных задач.

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

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

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

== Лекции ==

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

=== Программа ===

<!--
Список вопросов к экзаменам аналогичного курса в прошлом году:
* [[Медиа:Algo_exam_HSE_masters_2019_Fall_part1.pdf| 1 модуль]]
* [[Медиа:Algo_exam_HSE_masters_2019_Fall_part2.pdf| 2 модуль]]
-->

<div class="mw-collapsible mw-collapsed" data-expandtext="{{int:show}}" data-collapsetext="{{int:hide}}" style="width:45em;">
====Первый модуль====
<div class="mw-collapsible-content">

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

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

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

=====(4) 28 сентября. Быстрая сортировка — 2. Динамическое программирование — 1.=====
* Быстрая сортировка. Корректность inplace-версии. Частичная сортировка.
* Средняя глубины рекурсии (без доказательства).
* Элиминация хвостовой рекурсии. IntroSort.

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

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

=====(5) 5 октября. Динамическое программирование — 2. Жадные алгоритмы.=====
[https://cdkrot.me/teaching/2020f-algo-masters/notes/2020-10-05_DP2.pdf Динамическое-программирование — 2]:
* Дискретная задача о рюкзаке с повторениями.
* Дискретная задача о рюкзаке без повторений.
* Редакционное расстояние.
* Задача коммивояжёра.

[https://cdkrot.me/teaching/2020f-algo-masters/notes/2020-10-05_Greedy.pdf Жадные алгоритмы]:
* Покрытие точек единичными отрезками.
* Задача о выборе заявок.
* Непрерывная задаче о рюкзаке.

=====(6) 12 октября. Код Хаффмана. Алгоритмы на графах — 1.=====
[https://cdkrot.me/teaching/2020f-algo-masters/notes/2020-10-12_Huffman.pdf Жадные алгоритмы]:
* Непрерывная задаче о рюкзаке — доказательство
<!-- * Задача выполнимости для хорновских формул. -->
* Код Хаффмана.

[https://cdkrot.me/teaching/2020f-algo-masters/notes/2020-10-12_Graphs_DFS.pdf Графы]:
* Определения, способы хранения (матрица смежности и списки смежности).
* Поиск в глубину (DFS), доказательство корректности. Компоненты связности.
* DFS: поиск цикла, три цвета вершин<!--, классификация рёбер-->.
* Топологическая сортировка, два подхода: с очередью, с помощью DFS (на практике).

</div>
</div>

====25 октября. Экзамен.====
[[Медиа:Algo_exam_HSE_masters_2020_Fall_part1.pdf| Список вопросов]]

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

=====(7) 30 октября. Кратчайшие пути в графах.=====
[https://cdkrot.me/teaching/2020f-algo-masters/notes/2020-10-30_BFS.pdf Невзвешенные графы]:
* Поиск в ширину (BFS), доказательство корректности. <!--Лучевой поиск (beam search).-->
[https://cdkrot.me/teaching/2020f-algo-masters/notes/2020-10-30_ShortestPaths.pdf Взвешенные графы]:
* Алгоритм Дейкстры, доказательство корректности. Реализации для плотных и разреженных графов.
* Алгоритм Форда — Беллмана. Оптимизация памяти до линейной. <!-- Доказательство корректности. Проверка на наличие отрицательного цикла, его нахождение.-->
* Алгоритм Флойда — Уоршелла. Оптимизация памяти до квадратичной. <!--, доказательство корректности. Проверка на наличие отрицательного цикла.-->

=====(8) 2 ноября. Минимальные остовные деревья.=====
* [https://cdkrot.me/teaching/2020f-algo-masters/notes/2020-11-02_ShortestPathsProofs.pdf Доказательство корректности алгоритмов ФБ, Флойда.]
* [https://cdkrot.me/teaching/2020f-algo-masters/notes/2020-11-02_MST.pdf MST.]

=====(9) 9 ноября. СНМ с двумя эвристиками. Потоки в графах.=====
* [https://cdkrot.me/teaching/2020f-algo-masters/notes/2020-11-09_DSUProof.pdf Оценка времени работы СНМ с двумя эвристиками.]
* [https://cdkrot.me/teaching/2020f-algo-masters/notes/2020-11-09_Flows.pdf Потоки в графах.] [https://cdkrot.me/teaching/2020f-algo-masters/conspect.pdf Конспект аналогичной лекции.]

=====(10) 16 ноября. Потоки-2. Бинарные деревья поиска.=====
* [https://cdkrot.me/teaching/2020f-algo-masters/notes/2020-11-16_EK_Scaling.pdf Потоки: алгоритм Эдмондса-Карпа и масштабирования.]
* [https://cdkrot.me/teaching/2020f-algo-masters/notes/2020-11-16_BST.pdf Бинарные деревья поиска.]

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

=====(11) 23 ноября. Алгоритмы на строках, хеширование.=====
[https://cdkrot.me/teaching/2020f-algo-masters/notes/2020-11-23_Strings.pdf Строки:]
* Z-функция
* Префикс-функция и алгоритм Кнута-Морриса-Пратта
* Полиномиальное хеширование
* Хеш-таблица

=====(12) 30 ноября.=====

=====(13) 7 декабря.=====

=== Литература ===
* [https://logic.pdmi.ras.ru/~kulikov/en/algorithms Дасгупта С., Пападимитриу Х., Вазирани У. Алгоритмы.]
* М. А. Бабенко, М. В. Левин. Введение в теорию алгоритмов и структур данных.
* Т.Кормен, Ч.Лейзерсон, Р.Ривест, К.Штайн - Алгоритмы. Построение и анализ.
* [https://www.mccme.ru/free-books/shen/shen-progbook.pdf А. Шень. Программирование: теоремы и задачи.]

=== Онлайн-курсы ===
* [https://stepik.org/course/217/syllabus Алгоритмы: теория и практика. Методы]
* [https://stepik.org/course/1547/syllabus Алгоритмы: теория и практика. Структуры данных]
* [https://www.coursera.org/specializations/data-structures-algorithms Data Structures and Algorithms Specialization on Coursera]
* [https://www.coursera.org/learn/algorithmic-toolbox Algorithmic Toolbox — часть специализации из предыдущего пункта]

== Практика ==
<h3>Задачи</h3>

[[Медиа:Hse.master.2020.fall.pdf|Условия задач]] | [https://cdkrot.me/teaching/2020f-algo-masters/practice/tutorial.pdf Разборы] | [https://cdkrot.me/teaching/2020f-algo-masters/practice/tutorial_contest.pdf Разборы контестов]

[[Медиа:Hse.master.2020.fall.hints.pdf|Технические советы для написании кода]]

[[Медиа:Algo_hw_tex_template.zip| TeX-шаблон для домашек]]

<!--<h3>Антон Гардер</h3>-->
<h3>Сергей Копелиович</h3>

Контакты: 
* Почта для домашек: <code>burunduk30@gmail.com</code>, в теме письма должна быть подстрока <code>SPb HSE HW</code>
<!--
* Почта для домашек: <code>AntonProverDZ@yahoo.com</code>
* Почта для общения: <code>anton.garder@yahoo.com</code>
* Telegram: <code>avgarder</code>-->

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

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

[https://docs.google.com/spreadsheets/d/1Gk-7b6NkWUu7KswpuXs7yQ8uqcBNQ10T6hffXBX8YnY/edit?usp=sharing Таблица с результатами]

<h3>Владислав Кораблинов</h3>
Контакты:

* <code>vladislav.korablinov+hse_20_algo@gmail.com</code>
* Telegram: <code>ladine0n</code>

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

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

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

[https://docs.google.com/spreadsheets/d/1O0tM5UvtzvnmdmolHHwma5r2XqsQU-NB99aZu7iE8RY/edit#gid=1211943617 Табличка с результатами]