Алгоритмы и структуры данных 2 2020/2021 — различия между версиями
Poldnev (обсуждение | вклад) (Поменял контрольную и следующую лекцию) |
Poldnev (обсуждение | вклад) (Чат пересдачи) |
||
(не показано 29 промежуточных версии 2 участников) | |||
Строка 11: | Строка 11: | ||
hse@poldnev.ru | hse@poldnev.ru | ||
− | ''' | + | '''Оценки:'''<br/> |
− | + | https://docs.google.com/spreadsheets/d/1Xc84600TFxccMM2Kvai1jtQ6bMDm0bFwe9FksJWW_-Y/ | |
= Лекции = | = Лекции = | ||
# 1 сентября. Задачи RSQ и RMQ. Дерево отрезков. [https://www.youtube.com/watch?v=glwzAxHhe14&list=PLEwK9wdS5g0rBPRiw6jl6fnIMY2vne-hM&index=2&t=0s Лекция], [https://drive.google.com/file/d/1rh09JQR4k5MAgWgM_Xce06Pbg5m30pIx/view?usp=sharing презентация] | # 1 сентября. Задачи RSQ и RMQ. Дерево отрезков. [https://www.youtube.com/watch?v=glwzAxHhe14&list=PLEwK9wdS5g0rBPRiw6jl6fnIMY2vne-hM&index=2&t=0s Лекция], [https://drive.google.com/file/d/1rh09JQR4k5MAgWgM_Xce06Pbg5m30pIx/view?usp=sharing презентация] | ||
− | # 5 сентября. Дерево отрезков с обновлением на отрезке. Дерево Фенвика.[https://www.youtube.com/watch?v=tIh-MJG0afk&list=PLEwK9wdS5g0rBPRiw6jl6fnIMY2vne-hM&index=2 Лекция], [https://drive.google.com/file/d/1j_eks20ZXpV2zxN_vtju7TwsR6H4eyHE/view?usp=sharing презентация] | + | # 5 сентября. Дерево отрезков с обновлением на отрезке. Дерево Фенвика. [https://www.youtube.com/watch?v=tIh-MJG0afk&list=PLEwK9wdS5g0rBPRiw6jl6fnIMY2vne-hM&index=2 Лекция], [https://drive.google.com/file/d/1j_eks20ZXpV2zxN_vtju7TwsR6H4eyHE/view?usp=sharing презентация] |
− | # 8 сентября. Префикс- и z-функция. [https://drive.google.com/file/d/ | + | # 8 сентября. Префикс- и z-функция. [https://youtu.be/mX4BThZiPhY?t=1623 Лекция], [https://drive.google.com/file/d/1I0UnWivOcdsgxVxN90es2o5Ym0XJ2Xgd/view?usp=sharing презентация] |
− | # 12 сентября. Алгоритм Ахо — Корасик. | + | # 12 сентября. Алгоритм Ахо — Корасик. [https://www.youtube.com/watch?v=TUuEMAjygGA&list=PLEwK9wdS5g0rBPRiw6jl6fnIMY2vne-hM&index=8 Лекция], [https://drive.google.com/file/d/1q0fHCP69HmCBHBP59rPed2jCjwONGSPn/view?usp=sharing презентация], [https://drive.google.com/file/d/1k3A1oly5ZYBbtVwC_GwH_0AcVAzHgcaB/view?usp=sharing, код] |
− | # 15 сентября. Паросочетания. Алгоритм Куна. | + | # 15 сентября. Паросочетания. Алгоритм Куна. [https://www.youtube.com/watch?v=f1Cr9yXAePk&list=PLEwK9wdS5g0rBPRiw6jl6fnIMY2vne-hM&index=9 Лекция], [https://drive.google.com/file/d/1lSZRZAkHUD-7ACc4zvsfiq8s9TJLppFp/view?usp=sharing презентация] |
− | # 19 сентября. Потоки. Алгоритм Форда — Фалкерсона. | + | # 19 сентября. Потоки. Алгоритм Форда — Фалкерсона. [https://www.youtube.com/watch?v=e5_bZptjbcI&list=PLEwK9wdS5g0rBPRiw6jl6fnIMY2vne-hM&index=13 Лекция], [https://drive.google.com/file/d/1AZYIW5AIGtNlw3kg0yILvXKPlgycDJzH/view?usp=sharing презентация] |
− | # 22 сентября. Параллельность в C++. | + | # 22 сентября. Параллельность в C++. [https://www.youtube.com/watch?v=tyAFU7H_Z-E&list=PLEwK9wdS5g0rBPRiw6jl6fnIMY2vne-hM&index=14 Лекция], [https://drive.google.com/file/d/19oARvl7S7vraE2wACS75qxf8Bf_HxMT7/view?usp=sharing презентация], [https://drive.google.com/file/d/1Jp7lyIv1xgnrWE7nG6KSIWG4gD1Y50ql/view?usp=sharing код], [https://drive.google.com/file/d/1eNE-vxRH2UeSUXqJelvtDIyluThkLC5K/view?usp=sharing код с семинара] |
− | # 26 сентября. Контрольная работа по первым 6 лекциям: задачи на отрезках, строки, паросочетания и потоки. | + | # 26 сентября. [https://official.contest.yandex.ru/contest/19945/enter/ Контрольная работа] по первым 6 лекциям: задачи на отрезках, строки, паросочетания и потоки. |
− | # 29 сентября. Параллельные алгоритмы. | + | # 29 сентября. Параллельные алгоритмы. [https://www.youtube.com/watch?v=NmBsOThRt9U&list=PLEwK9wdS5g0rBPRiw6jl6fnIMY2vne-hM&index=21 Лекция], [https://drive.google.com/file/d/1JZlr7nu8-BdpvD4rtR2eqkvo4yc2fMVL/view?usp=sharing презентация], [https://drive.google.com/file/d/1RHJKMmrzS1Ls_UeroJMyz5abdM1BCkjN/view?usp=sharing код c лекции], [https://drive.google.com/file/d/1Y1U9JIalGpKvHyStAlVEJEd224b_D81k/view?usp=sharing код с семинара] |
− | # 3 октября. P и NP. | + | # 3 октября. P и NP [https://www.youtube.com/watch?v=uA6Ms2r2FgI&list=PLEwK9wdS5g0rBPRiw6jl6fnIMY2vne-hM&index=23 Лекция], [https://drive.google.com/file/d/1dVOqtNKvLs1c1j_ps9o7H-h4tscJGtG3/view?usp=sharing презентация]. |
− | # 6 октября. | + | # 6 октября. Выполнимость и 2-выполнимость. [https://drive.google.com/file/d/1VQe3Pmzap4ZebStnI1mDDuG1Iw8sKbjb/view?usp=sharing презентация], [https://drive.google.com/file/d/1R4WRuP0q3WPLogZzP1ed9cxBSpdGAJ05/view?usp=sharing код c лекции] |
− | # 10 октября. Эвристики в рекурсивном переборе. | + | # 10 октября. Эвристики в рекурсивном переборе. [https://drive.google.com/file/d/1Pnle743XJNbgReoo9gqmtj_1Gqzx_ADp/view?usp=sharing презентация], [https://drive.google.com/file/d/1hd5rR9kgJQBsZD2mGhx7nWwGDB-sBt5P/view?usp=sharing код c лекции] |
− | # 13 октября. Рандомизированные структуры. Хеширование кукушки. Фильтр Блума. Count-min sketch. | + | # 13 октября. Рандомизированные структуры. Хеширование кукушки. Фильтр Блума. Count-min sketch. [https://drive.google.com/file/d/1m79BYBZ3YibnrozYMTwxADpkb_x16JQ8/view?usp=sharing презентация] |
# 17 октября. Подготовка к экзамену. | # 17 октября. Подготовка к экзамену. | ||
Строка 35: | Строка 35: | ||
# [https://official.contest.yandex.ru/contest/19611/enter/ Задачи на отрезках]. 05.09 12:30 — 19.09 23:59 | # [https://official.contest.yandex.ru/contest/19611/enter/ Задачи на отрезках]. 05.09 12:30 — 19.09 23:59 | ||
− | # Задачи на строках. 12.09 12:30 — 26.09 23:59 | + | # [https://official.contest.yandex.ru/contest/19688/enter/ Задачи на строках]. 12.09 12:30 — 26.09 23:59 |
+ | # [https://official.contest.yandex.ru/contest/19820/enter/ Паросочетания и потоки]. 19.09 12:30 — 03.10 23:59 | ||
+ | # [https://official.contest.yandex.ru/contest/20247/enter/ Параллельность]. 29.09 10:50 — 11.10 23:59 (ручная проверка, одна задача засчитывается за две) | ||
+ | # [https://official.contest.yandex.ru/contest/20771/enter/ Перебор]. 10.10 12:30 — 16.10 23:59 | ||
+ | Оценка за ДЗ = 10 * min(1, (HW1 + HW2 + HW3 + 2×HW4 + HW5) / 25), где HWi — количество задач, решённых в соответствующем ДЗ. | ||
+ | |||
+ | |||
+ | = Контрольная работа 26.09 = | ||
+ | [https://official.contest.yandex.ru/contest/19945/enter/ Контест] | ||
+ | * 26.09 11:10 — 12:30 | ||
+ | * 5 задач: RMQ, строки, паросочетания и потоки | ||
+ | * Оценка зависит от количества решённых задач, штрафов нет | ||
+ | * 0 задач → 0 баллов, 1 задача → 4 балла, 2 задачи → 7 баллов, 3 задачи → 9 баллов, 4 или 5 задач → 10 баллов | ||
+ | * Таблица результатов доступна | ||
+ | * Свой код использовать можно, чужой — нельзя | ||
+ | |||
+ | |||
+ | = Экзамен 19.10 = | ||
+ | * Проходит очно для всех студентов, не находящихся на дистанционном обучении | ||
+ | * Возможность дистанционной сдачи в противном случае нужно согласовать с лектором | ||
+ | |||
+ | == Практическая часть ([https://official.contest.yandex.ru/contest/20934/enter/ контест]) == | ||
+ | * 09:30 — 11:00 | ||
+ | * Оценка зависит от количества решённых задач, штрафов нет | ||
+ | * 0 задач → 0 баллов, 1 задача → 4 балла, 2 задачи → 7 баллов, 3 задачи → 9 баллов, 4 или больше задач → 10 баллов | ||
+ | * Таблица результатов доступна | ||
+ | * Свой код использовать можно, чужой — нельзя | ||
+ | * Темы всего курса, кроме параллельности и рандомизированных структур | ||
+ | |||
+ | Оценка за практическую часть по желанию студента считается оценкой за экзамен. Участие в теоретической части считается отказом от этого и влечёт за собой учёт оценки за теоретическую часть в оценке за экзамен (см. ниже). | ||
+ | |||
+ | == Теоретическая часть == | ||
+ | * 11:10, но не все сразу | ||
+ | * Ответ без подготовки и использования дополнительных материалов | ||
+ | * Ориентировочное время ответа — 15 минут | ||
+ | * По усмотрению экзаменатора выдаётся один вопрос из списка простых и один вопрос из списка сложных | ||
+ | * Могут быть заданы дополнительные вопросы по теме | ||
+ | * Оценка за теоретическую часть = (П + 2 * С) / 3, где П — оценка ответа на простой вопрос, С — оценка ответа на сложный вопрос | ||
+ | * В случае участия в теоретической части оценка за экзамен = (0,25 * П + 0,15 * Т) / 0,4, где П — оценка за практическую часть, Т — оценка за теоретическую часть | ||
+ | |||
+ | === Простые вопросы === | ||
+ | # Решение задач static RMQ и RSQ с константной сложностью ответа на запрос | ||
+ | # Доказательство оценки O(log N) выполнения запросов к дереву отрезков | ||
+ | # Доказательство оценки O(N) вычисления префикс-функции | ||
+ | # Бор. Хранение переходов в виде словаря и массива, сложность операций | ||
+ | # Связь вершинного покрытия, независимого множества и клики | ||
+ | # Определения потока, остаточной сети и дополняющего пути. Лемма о сложении потоков (с доказательством) | ||
+ | # Понятие разреза. Лемма о величине потока через разрез | ||
+ | # Сведение обобщённой задачи о паросочетании (с ограничением на количество покрывающих рёбер для каждой вершины) к задаче поиска максимального потока | ||
+ | # Сведение задачи о выполнимости 3-КНФ к задаче проверки существования независимого множества заданного размера | ||
+ | # Структура фильтра Блума | ||
+ | === Сложные === | ||
+ | # Алгоритм КМП (версия, требующая O(|P|) памяти), доказательство корректности | ||
+ | # Автомат Ахо — Корасик: структура, построение за O(|A|×Σ|Pi|)) | ||
+ | # Теорема о дополняющей цепи | ||
+ | # Определения классов NP и Σ₁. Доказательство их эквивалентности. | ||
+ | # Сведение задачи выполнимости 2-КНФ к поиску компонент сильной связности | ||
+ | |||
+ | == Пересдачи == | ||
+ | |||
+ | * Даты пересдач: субботы 23.01 и 06.02. | ||
+ | * Координация пересдачи 06.02 — в чате https://t.me/joinchat/Hi0a3nI5I69-NLVF | ||
+ | * Пересдаётся только экзамен. | ||
+ | * Формат прежний: практическая часть, затем по желанию теоретическая. Оценка вычисляется так же. | ||
+ | * Задачи практической части частично будут заменены. | ||
+ | * Рекомендация по подготовке к практической части прежняя: прорешать домашки. | ||
= Оценки = | = Оценки = | ||
Строка 43: | Строка 108: | ||
* С — работа на семинаре <br /> | * С — работа на семинаре <br /> | ||
* КР — контрольная в середине модуля (контест) <br /> | * КР — контрольная в середине модуля (контест) <br /> | ||
− | * Э — экзамен (контест и теория) | + | * Э — экзамен (контест и теория) <br /> |
+ | Округление арифметическое. | ||
+ | |||
+ | |||
'''Возможность получить автомат''' | '''Возможность получить автомат''' | ||
Если в конце модуля выполнены следующие условия: | Если в конце модуля выполнены следующие условия: | ||
− | * (0,25×ДЗ + 0,1×С + 0,25×КР)/0,6 получается 8 и выше | + | * (0,25×ДЗ + 0,1×С + 0,25×КР)/0,6 после округления получается 8 и выше |
* Оценка за работу на семинаре не ниже 5 | * Оценка за работу на семинаре не ниже 5 | ||
− | то можно получить автомат: О<sub>итог</sub> = | + | то можно получить автомат: О<sub>итог</sub> = Oкр((0,25×ДЗ + 0,1×С + 0,25×КР)/0,6) |
+ | |||
+ | Оценки будут финализированы на лекции 17.10. Об отказе от автомата нужно сообщить лектору до 19:00 17.10. |
Текущая версия на 08:43, 3 февраля 2021
Лектор: Антон Полднев
Расписание лекций:
вторник 09:30 – 10:50
суббота 11:10 – 12:30
Канал для объявлений:
https://t.me/aisd2_20
Консультации:
hse@poldnev.ru
Оценки:
https://docs.google.com/spreadsheets/d/1Xc84600TFxccMM2Kvai1jtQ6bMDm0bFwe9FksJWW_-Y/
Содержание
Лекции
- 1 сентября. Задачи RSQ и RMQ. Дерево отрезков. Лекция, презентация
- 5 сентября. Дерево отрезков с обновлением на отрезке. Дерево Фенвика. Лекция, презентация
- 8 сентября. Префикс- и z-функция. Лекция, презентация
- 12 сентября. Алгоритм Ахо — Корасик. Лекция, презентация, код
- 15 сентября. Паросочетания. Алгоритм Куна. Лекция, презентация
- 19 сентября. Потоки. Алгоритм Форда — Фалкерсона. Лекция, презентация
- 22 сентября. Параллельность в C++. Лекция, презентация, код, код с семинара
- 26 сентября. Контрольная работа по первым 6 лекциям: задачи на отрезках, строки, паросочетания и потоки.
- 29 сентября. Параллельные алгоритмы. Лекция, презентация, код c лекции, код с семинара
- 3 октября. P и NP Лекция, презентация.
- 6 октября. Выполнимость и 2-выполнимость. презентация, код c лекции
- 10 октября. Эвристики в рекурсивном переборе. презентация, код c лекции
- 13 октября. Рандомизированные структуры. Хеширование кукушки. Фильтр Блума. Count-min sketch. презентация
- 17 октября. Подготовка к экзамену.
Домашние задания
Штрафов за неверные посылки нет, учитывается лишь количество успешно сданных задач
- Задачи на отрезках. 05.09 12:30 — 19.09 23:59
- Задачи на строках. 12.09 12:30 — 26.09 23:59
- Паросочетания и потоки. 19.09 12:30 — 03.10 23:59
- Параллельность. 29.09 10:50 — 11.10 23:59 (ручная проверка, одна задача засчитывается за две)
- Перебор. 10.10 12:30 — 16.10 23:59
Оценка за ДЗ = 10 * min(1, (HW1 + HW2 + HW3 + 2×HW4 + HW5) / 25), где HWi — количество задач, решённых в соответствующем ДЗ.
Контрольная работа 26.09
- 26.09 11:10 — 12:30
- 5 задач: RMQ, строки, паросочетания и потоки
- Оценка зависит от количества решённых задач, штрафов нет
- 0 задач → 0 баллов, 1 задача → 4 балла, 2 задачи → 7 баллов, 3 задачи → 9 баллов, 4 или 5 задач → 10 баллов
- Таблица результатов доступна
- Свой код использовать можно, чужой — нельзя
Экзамен 19.10
- Проходит очно для всех студентов, не находящихся на дистанционном обучении
- Возможность дистанционной сдачи в противном случае нужно согласовать с лектором
Практическая часть (контест)
- 09:30 — 11:00
- Оценка зависит от количества решённых задач, штрафов нет
- 0 задач → 0 баллов, 1 задача → 4 балла, 2 задачи → 7 баллов, 3 задачи → 9 баллов, 4 или больше задач → 10 баллов
- Таблица результатов доступна
- Свой код использовать можно, чужой — нельзя
- Темы всего курса, кроме параллельности и рандомизированных структур
Оценка за практическую часть по желанию студента считается оценкой за экзамен. Участие в теоретической части считается отказом от этого и влечёт за собой учёт оценки за теоретическую часть в оценке за экзамен (см. ниже).
Теоретическая часть
- 11:10, но не все сразу
- Ответ без подготовки и использования дополнительных материалов
- Ориентировочное время ответа — 15 минут
- По усмотрению экзаменатора выдаётся один вопрос из списка простых и один вопрос из списка сложных
- Могут быть заданы дополнительные вопросы по теме
- Оценка за теоретическую часть = (П + 2 * С) / 3, где П — оценка ответа на простой вопрос, С — оценка ответа на сложный вопрос
- В случае участия в теоретической части оценка за экзамен = (0,25 * П + 0,15 * Т) / 0,4, где П — оценка за практическую часть, Т — оценка за теоретическую часть
Простые вопросы
- Решение задач static RMQ и RSQ с константной сложностью ответа на запрос
- Доказательство оценки O(log N) выполнения запросов к дереву отрезков
- Доказательство оценки O(N) вычисления префикс-функции
- Бор. Хранение переходов в виде словаря и массива, сложность операций
- Связь вершинного покрытия, независимого множества и клики
- Определения потока, остаточной сети и дополняющего пути. Лемма о сложении потоков (с доказательством)
- Понятие разреза. Лемма о величине потока через разрез
- Сведение обобщённой задачи о паросочетании (с ограничением на количество покрывающих рёбер для каждой вершины) к задаче поиска максимального потока
- Сведение задачи о выполнимости 3-КНФ к задаче проверки существования независимого множества заданного размера
- Структура фильтра Блума
Сложные
- Алгоритм КМП (версия, требующая O(|P|) памяти), доказательство корректности
- Автомат Ахо — Корасик: структура, построение за O(|A|×Σ|Pi|))
- Теорема о дополняющей цепи
- Определения классов NP и Σ₁. Доказательство их эквивалентности.
- Сведение задачи выполнимости 2-КНФ к поиску компонент сильной связности
Пересдачи
- Даты пересдач: субботы 23.01 и 06.02.
- Координация пересдачи 06.02 — в чате https://t.me/joinchat/Hi0a3nI5I69-NLVF
- Пересдаётся только экзамен.
- Формат прежний: практическая часть, затем по желанию теоретическая. Оценка вычисляется так же.
- Задачи практической части частично будут заменены.
- Рекомендация по подготовке к практической части прежняя: прорешать домашки.
Оценки
Итоговая оценка: 0,25×ДЗ + 0,1×С + 0,25×КР + 0,4×Э, где:
- ДЗ — домашние задания (контесты)
- С — работа на семинаре
- КР — контрольная в середине модуля (контест)
- Э — экзамен (контест и теория)
Округление арифметическое.
Возможность получить автомат
Если в конце модуля выполнены следующие условия:
- (0,25×ДЗ + 0,1×С + 0,25×КР)/0,6 после округления получается 8 и выше
- Оценка за работу на семинаре не ниже 5
то можно получить автомат: Оитог = Oкр((0,25×ДЗ + 0,1×С + 0,25×КР)/0,6)
Оценки будут финализированы на лекции 17.10. Об отказе от автомата нужно сообщить лектору до 19:00 17.10.