Алгоритмы и структуры данных 2 2020/2021

Материал из Wiki - Факультет компьютерных наук
Перейти к: навигация, поиск

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

Расписание лекций:
вторник 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-КНФ к поиску компонент сильной связности

Пересдачи

  • Даты пересдач: субботы 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.