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

Материал из Wiki - Факультет компьютерных наук
Перейти к: навигация, поиск
 
(не показано 11 промежуточных версии этого же участника)
Строка 4: Строка 4:
  
 
Лектор: [https://www.hse.ru/org/persons/191485259 Куренков Владимир Вячеславович]
 
Лектор: [https://www.hse.ru/org/persons/191485259 Куренков Владимир Вячеславович]
 +
 +
Запись лекций:
 +
https://disk.yandex.ru/d/SYzrnC3HeOJIDA
  
 
{| class="wikitable"
 
{| class="wikitable"
 
|-
 
|-
! № !! Дата !! Тема !! ДЗ !! Дедлайн
+
! № !! Дата !! Тема !! ДЗ
 
|-
 
|-
| 1 || 07.09 || Хэш-функция. || [https://official.contest.yandex.ru/contest/67753 ДЗ 1] || -
+
| 1 || 07.09 || Хэш-функция. || [https://official.contest.yandex.ru/contest/67753 ДЗ 1]
 
|-
 
|-
| 2 || 10.09 || Z-функция. Префикс функция. || [https://official.contest.yandex.ru/contest/67809 ДЗ 2] || -
+
| 2 || 10.09 || Z-функция. Префикс функция. || [https://official.contest.yandex.ru/contest/67809 ДЗ 2]
 
|-
 
|-
| 3 || 14.09 || Суффиксный массив. || [https://official.contest.yandex.ru/contest/68181 ДЗ 3] || -
+
| 3 || 14.09 || Суффиксный массив. || [https://official.contest.yandex.ru/contest/68181 ДЗ 3]
 
|-
 
|-
| 4 || 17.09 || Бор. Алгоритм Ахо-Карасика || [https://official.contest.yandex.ru/contest/68182 ДЗ 4] || -
+
| 4 || 17.09 || Бор. Алгоритм Ахо-Карасика || [https://official.contest.yandex.ru/contest/68182 ДЗ 4]
 
|-
 
|-
| 5 || 21.09 || Метод имитации отжига. Перебор. || - || -
+
| 5 || 21.09 || Метод имитации отжига. Перебор. || [https://official.contest.yandex.ru/contest/68699 ДЗ 5]
 
|-
 
|-
| 6 || 24.09 || Задача нахождения максимального потока в транспортной сети. Алгоритмы: Форда-Фалкерсона, Эдмондса — Карпа. || - || -
+
| 6 || 24.09 || Задача нахождения максимального потока в транспортной сети. Алгоритмы: Форда-Фалкерсона, Эдмондса — Карпа. || -
 
|-
 
|-
| 7 || 28.09 || Нахождение максимального паросочетания в двудольном графе: алгоритм Куна. || - || -
+
| 7 || 28.09 || Нахождение максимального паросочетания в двудольном графе: алгоритм Куна. || -
 
|-  
 
|-  
| 8 || 01.10 || Алгоритм Диницы. || - || -
+
| 8 || 01.10 || Алгоритм Диницы. || [https://official.contest.yandex.ru/contest/69235/standings ДЗ 6]
 
|-  
 
|-  
| 9 || 05.10 || Сбалансированные деревья поиска. АВЛ - дерево. Splay - дерево. || - || -
+
| 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 || Запасная лекция. || - ||
+
| 14 || 22.10 || Запасная лекция. || -
 
|}
 
|}
  
Строка 60: Строка 63:
  
 
== К.Р. Общие положения ==
 
== К.Р. Общие положения ==
 +
 +
https://official.contest.yandex.ru/contest/69741
 +
 +
== Темы для Экзамена ==
 +
 +
Будет предложено решить 5 задач за 1:30 - 2:00
 +
 +
1. Строки. Хэш функция, префикс функция, z-функция.
 +
 +
2. Строки. Бор.
 +
 +
3. Деревья поиска.
 +
 +
4. Паросочетания. Алгоритм Куна.
 +
 +
5. Сложная на любую из пройденных тем.
 +
 +
== Темы для коллоквиума ==
 +
 +
Хэш-функция. Полиномиальное хеширование.
 +
Применение: Количество разных подстрок.
 +
Поиск подстроки в строке. Сравнение подстрок.
 +
Палиндромность подстроки. Количество палиндромов.
 +
   
 +
Z-функция. Префикс функция. Построение за линейное время.
 +
Применение: Поиск подстроки в строке.
 +
Количество различных подстрок в строке.
 +
Сжатие строки(Период строки).
 +
 +
Алгоритм Ахо-Карасик. Построение дерева. Оценка трудоёмкости алгоритма. Применение.
 +
 +
Суффиксный массив. Сортировка суффиксов. Оценка трудоёмкости алгоритма. Применение в задачах на строки. Поиск lcp.
 +
 +
Задача построения максимального потока в сети.
 +
Алгоритм Форда-Фалкерсона построения максимального потока  в сети. Оценка сложности алгоритма.
 +
Минимальный разрез сети. Величина разреза.
 +
Алгоритм Эдмондса-Карпа построения максимального потока в сети. Оценка сложности алгоритма.
 +
 +
Нахождение максимального паросочетания в двудольном графе: алгоритм Куна. Оценка сложности алгоритма.
 +
 +
Деревья поиска, их представление в компьютере. Алгоритм поиска элемента. Добавление элемента в дерево. Удаление элемента из дерева. АВЛ-деревья. Алгоритм добавления элемента и балансировки АВЛ-дерева. Оценка высоты АВЛ-дерева.

Текущая версия на 09: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.

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

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

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