Алгоритмы и структуры данных 2 КНАД 24/25: различия между версиями

Текущая версия от 06:46, 22 октября 2024

Лекции и ДЗ

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

№	Дата	Тема	ДЗ
1	07.09	Хэш-функция.	ДЗ 1
2	10.09	Z-функция. Префикс функция.	ДЗ 2
3	14.09	Суффиксный массив.	ДЗ 3
4	17.09	Бор. Алгоритм Ахо-Карасика	ДЗ 4
5	21.09	Метод имитации отжига. Перебор.	ДЗ 5
6	24.09	Задача нахождения максимального потока в транспортной сети. Алгоритмы: Форда-Фалкерсона, Эдмондса — Карпа.	-
7	28.09	Нахождение максимального паросочетания в двудольном графе: алгоритм Куна.	-
8	01.10	Алгоритм Диницы.	ДЗ 6
9	05.10	Сбалансированные деревья поиска. АВЛ - дерево. Splay - дерево.	-
10	08.10	Длинная арифметика.	ДЗ 7
11	12.10	Быстрое преобразование Фурье.	-
12	15.10	-	-
13	19.10	Контрольная работа в формате теста.	К.Р.
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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

@@ Строка 4: / Строка 4: @@
 Лектор: [https://www.hse.ru/org/persons/191485259 Куренков Владимир Вячеславович]
+Запись лекций:
+https://disk.yandex.ru/d/SYzrnC3HeOJIDA
 {| class="wikitable"
@@ Строка 23: / Строка 26: @@
 | 7 || 28.09 || Нахождение максимального паросочетания в двудольном графе: алгоритм Куна. || -
 |-
-| 8 || 01.10 || Алгоритм Диницы. || -
+| 8 || 01.10 || Алгоритм Диницы. || [https://official.contest.yandex.ru/contest/69235/standings ДЗ 6]
 |-
 | 9 || 05.10 || Сбалансированные деревья поиска. АВЛ - дерево. Splay - дерево. || -
 |-
-| 10 || 08.10 || Красно-черное дерево. || -
+| 10 || 08.10 || Длинная арифметика. || [https://official.contest.yandex.ru/contest/69532/standings/ ДЗ 7]
 |-
-| 11 || 12.10 || Длинная арифметика. || -
+| 11 || 12.10 || Быстрое преобразование Фурье. || -
 |-
-| 12 || 15.10 || Быстрое преобразование Фурье. || -
+| 12 || 15.10 || - || -
 |-
-| 13 || 19.10 || Контрольная работа в формате теста. || -
+| 13 || 19.10 || Контрольная работа в формате теста. || [https://official.contest.yandex.ru/contest/69741/ К.Р.]
 |-
 | 14 || 22.10 || Запасная лекция. || -
@@ Строка 60: / Строка 63: @@
 == К.Р. Общие положения ==
+https://official.contest.yandex.ru/contest/69741
+== Темы для Экзамена ==
+Будет предложено решить 5 задач за 1:30 - 2:00
+. Строки. Хэш функция, префикс функция, z-функция.
+. Строки. Бор.
+. Деревья поиска.
+. Паросочетания. Алгоритм Куна.
+. Сложная на любую из пройденных тем.
+== Темы для коллоквиума ==
+Хэш-функция. Полиномиальное хеширование.
+Применение: Количество разных подстрок.
+Поиск подстроки в строке. Сравнение подстрок.
+Палиндромность подстроки. Количество палиндромов.
+Z-функция. Префикс функция. Построение за линейное время.
+Применение: Поиск подстроки в строке.
+Количество различных подстрок в строке.
+Сжатие строки(Период строки).
+Алгоритм Ахо-Карасик. Построение дерева. Оценка трудоёмкости алгоритма. Применение.
+Суффиксный массив. Сортировка суффиксов. Оценка трудоёмкости алгоритма. Применение в задачах на строки. Поиск lcp.
+Задача построения максимального потока в сети.
+Алгоритм Форда-Фалкерсона построения максимального потока  в сети. Оценка сложности алгоритма.
+Минимальный разрез сети. Величина разреза.
+Алгоритм Эдмондса-Карпа построения максимального потока в сети. Оценка сложности алгоритма.
+Нахождение максимального паросочетания в двудольном графе: алгоритм Куна. Оценка сложности алгоритма.
+Деревья поиска, их представление в компьютере. Алгоритм поиска элемента. Добавление элемента в дерево. Удаление элемента из дерева. АВЛ-деревья. Алгоритм добавления элемента и балансировки АВЛ-дерева. Оценка высоты АВЛ-дерева.