Просмотр исходного текста страницы Алгоритмы и структуры данных 2 КНАД 24/25

[https://t.me/+wNPuVnDwe5U3NmEy Ссылка на чат курса]

== Лекции и ДЗ ==

Лектор: [https://www.hse.ru/org/persons/191485259 Куренков Владимир Вячеславович]

Запись лекций:
https://disk.yandex.ru/d/SYzrnC3HeOJIDA

{| class="wikitable"
|-
! № !! Дата !! Тема !! ДЗ
|-
| 1 || 07.09 || Хэш-функция. || [https://official.contest.yandex.ru/contest/67753 ДЗ 1]
|-
| 2 || 10.09 || Z-функция. Префикс функция. || [https://official.contest.yandex.ru/contest/67809 ДЗ 2]
|-
| 3 || 14.09 || Суффиксный массив. || [https://official.contest.yandex.ru/contest/68181 ДЗ 3]
|-
| 4 || 17.09 || Бор. Алгоритм Ахо-Карасика || [https://official.contest.yandex.ru/contest/68182 ДЗ 4]
|-
| 5 || 21.09 || Метод имитации отжига. Перебор. || [https://official.contest.yandex.ru/contest/68699 ДЗ 5]
|-
| 6 || 24.09 || Задача нахождения максимального потока в транспортной сети. Алгоритмы: Форда-Фалкерсона, Эдмондса — Карпа. || -
|-
| 7 || 28.09 || Нахождение максимального паросочетания в двудольном графе: алгоритм Куна. || -
|- 
| 8 || 01.10 || Алгоритм Диницы. || [https://official.contest.yandex.ru/contest/69235/standings ДЗ 6]
|- 
| 9 || 05.10 || Сбалансированные деревья поиска. АВЛ - дерево. Splay - дерево. || -
|- 
| 10 || 08.10 || Длинная арифметика. || [https://official.contest.yandex.ru/contest/69532/standings/ ДЗ 7]
|- 
| 11 || 12.10 || Быстрое преобразование Фурье. || -
|- 
| 12 || 15.10 || - || -
|- 
| 13 || 19.10 || Контрольная работа в формате теста. || [https://official.contest.yandex.ru/contest/69741/ К.Р.]
|- 
| 14 || 22.10 || Запасная лекция. || -
|}

== Система оценки ==

Итоговая оценка, для ЭАД:
0.4 * ДЗ + 0.15 Коллоквиум + 0.15 * К.Р. + 0.1 * max(Семинары, Бонусное д.з.) + 0.2 * Экзамен

Количество домашних контестов может измениться. Гарантируется, что общий вклад дз в итоговую оценку 0,4 и что у всех блоков дз будет одинаковый вес.


Таблица с промежуточными результатами:

== Бонусные баллы ==

Бонусные баллы можно получить следующим образом:

* Бонусные баллы за 1/8 финала ICPC


== Выполнение ДЗ. Правила оценивания ==

После каждой лекции выдается контест, как правило, состоящий из 10 задач. Дедлайн - в 23:59, дня, указанного в таблице. В течение недели после дедлайна разрешается дорешивать задачи домашнего контеста за половину стоимости.

== К.Р. Общие положения ==

https://official.contest.yandex.ru/contest/69741

== Темы для коллоквиума ==

Хэш-функция. Полиномиальное хеширование.
Применение: Количество разных подстрок.
Поиск подстроки в строке. Сравнение подстрок.
Палиндромность подстроки. Количество палиндромов.
    
Z-функция. Префикс функция. Построение за линейное время.
Применение: Поиск подстроки в строке.
Количество различных подстрок в строке.
Сжатие строки(Период строки). 

Алгоритм Ахо-Карасик. Построение дерева. Оценка трудоёмкости алгоритма. Применение.

Суффиксный массив. Сортировка суффиксов. Оценка трудоёмкости алгоритма. Применение в задачах на строки. Поиск lcp.

Задача построения максимального потока в сети.
Алгоритм Форда-Фалкерсона построения максимального потока  в сети. Оценка сложности алгоритма.
Минимальный разрез сети. Величина разреза.
Алгоритм Эдмондса-Карпа построения максимального потока в сети. Оценка сложности алгоритма.

Нахождение максимального паросочетания в двудольном графе: алгоритм Куна. Оценка сложности алгоритма.

Деревья поиска, их представление в компьютере. Алгоритм поиска элемента. Добавление элемента в дерево. Удаление элемента из дерева. АВЛ-деревья. Алгоритм добавления элемента и балансировки АВЛ-дерева. Оценка высоты АВЛ-дерева.