imported>Mibig: Migrated current public revision from wiki.cs.hse.ru

2025-10-27T12:13:01Z

Migrated current public revision from wiki.cs.hse.ru

Новая страница

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

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

Лектор: [https://www.hse.ru/staff/mibig/ Мамай Игорь Борисович]

Записи лекций Куренкова В.В. 2024/2025 учебного года:
https://disk.yandex.ru/d/SYzrnC3HeOJIDA

{| class="wikitable"
|-
! № !! Дата !! Тема !! ДЗ
|-
| 1 || 05.09 || Хеш-функция. || [https://official.contest.yandex.ru/contest/81080 ДЗ 1]
|-
| 2 || 08.09 || Z-функция. Префикс функция. || [https://official.contest.yandex.ru/contest/81313 ДЗ 2]
|-
| 3 || 12.09 || Суффиксный массив. || [https://official.contest.yandex.ru/contest/81475 ДЗ 3]
|-
| 4 || 15.09 || Бор. Алгоритм Ахо-Корасик. || [https://official.contest.yandex.ru/contest/81720 ДЗ 4]
|-
| 5 || 19.09 || Метод имитации отжига. Перебор. || [https://official.contest.yandex.ru/contest/81721 ДЗ 5]
|-
| 6 || 22.09 || Задача нахождения максимального потока в транспортной сети. Алгоритмы Форда-Фалкерсона и Эдмондса-Карпа. || -
|-
| 7 || 26.09 || Нахождение максимального паросочетания в двудольном графе. Алгоритм Куна. || [https://official.contest.yandex.ru/contest/82086 ДЗ 6]
|-
| 8 || 29.09 || Алгоритм Диница. || -
|-
| 9 || 03.10 || Сбалансированные двоичные деревья поиска. || -
|-
| 10 || 06.10 || Длинная арифметика. || [https://official.contest.yandex.ru/contest/82735 ДЗ 7]
|-
| 11 || 08.10 || Коллоквиум. День 1. || -
|-
| 12 || 10.10 || Коллоквиум. День 2. || -
|-
| 13 || 13.10 || Алгоритм Карацубы.  || -
|-
| 14 || 17.10 || Контрольная работа в формате теста. || - 
|-
| 15 || 20.10 || Запасная лекция. || -
|}

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

Итоговая оценка = 0.4 * ДЗ + 0.15 * Коллоквиум + 0.15 * К.Р. + 0.1 * Семинары + 0.2 * Экзамен

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

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

Бонусные баллы можно получить за участие в 1/8 финала ICPC:

Бонус = 0.15 * min(5, Количество решенных задач).

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

Длительность выполнения контеста 10 дней. Начало и окончание в 12:00.

Оценка за контест из K задач вычисляется по формуле: 10 * Количество_Решенных_Задач / K.

== Темы для Экзамена ==

[https://official.contest.yandex.ru/contest/83950 Ссылка на Экзамен]

Экзамен пройдет 27 октября в 13:00.

Будет предложено решить 5 задач за 1:30 - 2:00

1. Строки. Хэш функция, префикс функция, z-функция.

2. Строки. Бор.

3. Деревья поиска.

4. Паросочетания. Алгоритм Куна.

5. Сложная на любую из пройденных тем.

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

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

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

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

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

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

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

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

Декартово дерево с поворотами. Единственность. Вставка элемента. Удаление элемента.

Алгоритмы и структуры данных 2 ЭАД 25/26 - История изменений

imported>Mibig: Migrated current public revision from wiki.cs.hse.ru