Алгоритмы и структуры данных 2 2020/2021 — различия между версиями
Материал из Wiki - Факультет компьютерных наук
(→Лекции) |
Poldnev (обсуждение | вклад) (Про экзамен) |
||
Строка 26: | Строка 26: | ||
# 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 код с семинара] | # 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 презентация]. | # 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-выполнимость. |
# 10 октября. Эвристики в рекурсивном переборе. | # 10 октября. Эвристики в рекурсивном переборе. | ||
# 13 октября. Рандомизированные структуры. Хеширование кукушки. Фильтр Блума. Count-min sketch. | # 13 октября. Рандомизированные структуры. Хеширование кукушки. Фильтр Блума. Count-min sketch. | ||
Строка 52: | Строка 52: | ||
= Экзамен 19.10 = | = Экзамен 19.10 = | ||
− | == [https://official.contest.yandex.ru/contest/???/enter/ | + | * Проходит очно для всех студентов, не находящихся на дистанционном обучении |
− | * 09:30 — | + | * Возможность дистанционной сдачи в противном случае нужно согласовать с лектором |
+ | |||
+ | == Практическая часть ([https://official.contest.yandex.ru/contest/???/enter/ контест]) == | ||
+ | * 09:30 — 11:00 | ||
* Оценка зависит от количества решённых задач, штрафов нет | * Оценка зависит от количества решённых задач, штрафов нет | ||
− | * 0 задач → 0 баллов, 1 задача → 4 балла, 2 задачи → 7 баллов, 3 задачи → 9 баллов, 4 или | + | * 0 задач → 0 баллов, 1 задача → 4 балла, 2 задачи → 7 баллов, 3 задачи → 9 баллов, 4 или больше задач → 10 баллов |
* Таблица результатов доступна | * Таблица результатов доступна | ||
* Свой код использовать можно, чужой — нельзя | * Свой код использовать можно, чужой — нельзя | ||
+ | * Темы всего курса | ||
+ | |||
+ | Оценка за практическую часть по желанию студента считается оценкой за экзамен. Участие в теоретической части считается отказом от этого и влечёт за собой учёт оценки за теоретическую часть в оценке за экзамен (см. ниже). | ||
== Теоретическая часть == | == Теоретическая часть == | ||
* 11: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-КНФ к поиску компонент сильной связности | ||
+ | |||
Версия 09:25, 9 октября 2020
Лектор: Антон Полднев
Расписание лекций:
вторник 09:30 – 10:50
суббота 11:10 – 12:30
Канал для объявлений:
https://t.me/aisd2_20
Консультации:
hse@poldnev.ru
Ассистенты:
Содержание
Лекции
- 1 сентября. Задачи RSQ и RMQ. Дерево отрезков. Лекция, презентация
- 5 сентября. Дерево отрезков с обновлением на отрезке. Дерево Фенвика. Лекция, презентация
- 8 сентября. Префикс- и z-функция. Лекция, презентация
- 12 сентября. Алгоритм Ахо — Корасик. Лекция, презентация, код
- 15 сентября. Паросочетания. Алгоритм Куна. Лекция, презентация
- 19 сентября. Потоки. Алгоритм Форда — Фалкерсона. Лекция, презентация
- 22 сентября. Параллельность в C++. Лекция, презентация, код, код с семинара
- 26 сентября. Контрольная работа по первым 6 лекциям: задачи на отрезках, строки, паросочетания и потоки.
- 29 сентября. Параллельные алгоритмы. Лекция, презентация, код c лекции, код с семинара
- 3 октября. P и NP Лекция, презентация.
- 6 октября. Выполнимость и 2-выполнимость.
- 10 октября. Эвристики в рекурсивном переборе.
- 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 — 10.10 23:59 (ручная проверка, одна задача засчитывается за две)
- Перебор. 10.10 12:30 — 16.10 23:59
Контрольная работа 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-КНФ к поиску компонент сильной связности
Оценки
Итоговая оценка: 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)