Алгоритмы и структуры данных 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. 1 сентября. Задачи RSQ и RMQ. Дерево отрезков. Лекция, презентация
2. 5 сентября. Дерево отрезков с обновлением на отрезке. Дерево Фенвика. Лекция, презентация
3. 8 сентября. Префикс- и z-функция. Лекция, презентация
4. 12 сентября. Алгоритм Ахо — Корасик. Лекция, презентация, код
5. 15 сентября. Паросочетания. Алгоритм Куна. Лекция, презентация
6. 19 сентября. Потоки. Алгоритм Форда — Фалкерсона. Лекция, презентация
7. 22 сентября. Параллельность в C++. Лекция, презентация, код, код с семинара
8. 26 сентября. Контрольная работа по первым 6 лекциям: задачи на отрезках, строки, паросочетания и потоки.
9. 29 сентября. Параллельные алгоритмы. Лекция, презентация, код c лекции, код с семинара
10. 3 октября. P и NP Лекция, презентация.
11. 6 октября. Выполнимость и 2-выполнимость. презентация, код c лекции
12. 10 октября. Эвристики в рекурсивном переборе. презентация, код c лекции
13. 13 октября. Рандомизированные структуры. Хеширование кукушки. Фильтр Блума. Count-min sketch. презентация
14. 17 октября. Подготовка к экзамену.

Домашние задания

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

1. Задачи на отрезках. 05.09 12:30 — 19.09 23:59
2. Задачи на строках. 12.09 12:30 — 26.09 23:59
3. Паросочетания и потоки. 19.09 12:30 — 03.10 23:59
4. Параллельность. 29.09 10:50 — 11.10 23:59 (ручная проверка, одна задача засчитывается за две)
5. Перебор. 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, где П — оценка за практическую часть, Т — оценка за теоретическую часть

Простые вопросы

1. Решение задач static RMQ и RSQ с константной сложностью ответа на запрос
2. Доказательство оценки O(log N) выполнения запросов к дереву отрезков
3. Доказательство оценки O(N) вычисления префикс-функции
4. Бор. Хранение переходов в виде словаря и массива, сложность операций
5. Связь вершинного покрытия, независимого множества и клики
6. Определения потока, остаточной сети и дополняющего пути. Лемма о сложении потоков (с доказательством)
7. Понятие разреза. Лемма о величине потока через разрез
8. Сведение обобщённой задачи о паросочетании (с ограничением на количество покрывающих рёбер для каждой вершины) к задаче поиска максимального потока
9. Сведение задачи о выполнимости 3-КНФ к задаче проверки существования независимого множества заданного размера
10. Структура фильтра Блума

Сложные

1. Алгоритм КМП (версия, требующая O(|P|) памяти), доказательство корректности
2. Автомат Ахо — Корасик: структура, построение за O(|A|×Σ|Pi|))
3. Теорема о дополняющей цепи
4. Определения классов NP и Σ₁. Доказательство их эквивалентности.
5. Сведение задачи выполнимости 2-КНФ к поиску компонент сильной связности

Оценки

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