Алгоритмы и структуры данных 2 2020/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.