Алгоритмы и структуры данных 2 2020/2021 — различия между версиями
Материал из Wiki - Факультет компьютерных наук
(код с семинара) |
Poldnev (обсуждение | вклад) |
||
Строка 30: | Строка 30: | ||
# 13 октября. Рандомизированные структуры. Хеширование кукушки. Фильтр Блума. Count-min sketch. | # 13 октября. Рандомизированные структуры. Хеширование кукушки. Фильтр Блума. Count-min sketch. | ||
# 17 октября. Подготовка к экзамену. | # 17 октября. Подготовка к экзамену. | ||
+ | |||
= Домашние задания = | = Домашние задания = | ||
Строка 49: | Строка 50: | ||
* Таблица результатов доступна | * Таблица результатов доступна | ||
* Свой код использовать можно, чужой — нельзя | * Свой код использовать можно, чужой — нельзя | ||
+ | |||
+ | |||
+ | = Экзамен 19.10 = | ||
+ | == [https://official.contest.yandex.ru/contest/???/enter/ Контест] == | ||
+ | * 09:30 — 10:50, по возможности очно | ||
+ | * Оценка зависит от количества решённых задач, штрафов нет | ||
+ | * 0 задач → 0 баллов, 1 задача → 4 балла, 2 задачи → 7 баллов, 3 задачи → 9 баллов, 4 или 5 задач → 10 баллов | ||
+ | * Таблица результатов доступна | ||
+ | * Свой код использовать можно, чужой — нельзя | ||
+ | |||
+ | == Теоретическая часть == | ||
+ | * 11:10, но не все сразу | ||
+ | * Здесь будет список вопросов. | ||
Версия 06:33, 1 октября 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 сентября. Параллельные алгоритмы.
- 3 октября. P и NP.
- 6 октября. P и NP.
- 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 — 10:50, по возможности очно
- Оценка зависит от количества решённых задач, штрафов нет
- 0 задач → 0 баллов, 1 задача → 4 балла, 2 задачи → 7 баллов, 3 задачи → 9 баллов, 4 или 5 задач → 10 баллов
- Таблица результатов доступна
- Свой код использовать можно, чужой — нельзя
Теоретическая часть
- 11:10, но не все сразу
- Здесь будет список вопросов.
Оценки
Итоговая оценка: 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)