imported>Poldnev: Чат пересдачи

2021-02-03T05:43:32Z

Чат пересдачи

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

'''Лектор:''' Антон Полднев

'''Расписание лекций:''' 
вторник 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. Дерево отрезков. [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 презентация]
# 8 сентября. Префикс- и z-функция. [https://youtu.be/mX4BThZiPhY?t=1623 Лекция], [https://drive.google.com/file/d/1I0UnWivOcdsgxVxN90es2o5Ym0XJ2Xgd/view?usp=sharing презентация]
# 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 сентября. Паросочетания. Алгоритм Куна. [https://www.youtube.com/watch?v=f1Cr9yXAePk&list=PLEwK9wdS5g0rBPRiw6jl6fnIMY2vne-hM&index=9 Лекция], [https://drive.google.com/file/d/1lSZRZAkHUD-7ACc4zvsfiq8s9TJLppFp/view?usp=sharing презентация]
# 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++. [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 сентября. [https://official.contest.yandex.ru/contest/19945/enter/ Контрольная работа] по первым 6 лекциям: задачи на отрезках, строки, паросочетания и потоки.
# 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 [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 октября. Выполнимость и 2-выполнимость. [https://drive.google.com/file/d/1VQe3Pmzap4ZebStnI1mDDuG1Iw8sKbjb/view?usp=sharing презентация], [https://drive.google.com/file/d/1R4WRuP0q3WPLogZzP1ed9cxBSpdGAJ05/view?usp=sharing код c лекции]
# 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. [https://drive.google.com/file/d/1m79BYBZ3YibnrozYMTwxADpkb_x16JQ8/view?usp=sharing презентация]
# 17 октября. Подготовка к экзамену.

= Домашние задания =
Штрафов за неверные посылки нет, учитывается лишь количество успешно сданных задач

# [https://official.contest.yandex.ru/contest/19611/enter/ Задачи на отрезках]. 05.09 12:30 — 19.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
* Пересдаётся только экзамен.
* Формат прежний: практическая часть, затем по желанию теоретическая. Оценка вычисляется так же.
* Задачи практической части частично будут заменены.
* Рекомендация по подготовке к практической части прежняя: прорешать домашки.

= Оценки =
Итоговая оценка: 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.

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

imported>Poldnev: Чат пересдачи