Алгоритмы и структуры данных 2 2020/2021 — различия между версиями
Материал из Wiki - Факультет компьютерных наук
(исправлена презентация от 8-09) |
Poldnev (обсуждение | вклад) (Контесты) |
||
| Строка 19: | Строка 19: | ||
# 5 сентября. Дерево отрезков с обновлением на отрезке. Дерево Фенвика. [https://www.youtube.com/watch?v=tIh-MJG0afk&list=PLEwK9wdS5g0rBPRiw6jl6fnIMY2vne-hM&index=2 Лекция], [https://drive.google.com/file/d/1j_eks20ZXpV2zxN_vtju7TwsR6H4eyHE/view?usp=sharing презентация] | # 5 сентября. Дерево отрезков с обновлением на отрезке. Дерево Фенвика. [https://www.youtube.com/watch?v=tIh-MJG0afk&list=PLEwK9wdS5g0rBPRiw6jl6fnIMY2vne-hM&index=2 Лекция], [https://drive.google.com/file/d/1j_eks20ZXpV2zxN_vtju7TwsR6H4eyHE/view?usp=sharing презентация] | ||
# 8 сентября. Префикс- и z-функция. [https://youtu.be/mX4BThZiPhY?t=1623 Лекция], [https://drive.google.com/file/d/1I0UnWivOcdsgxVxN90es2o5Ym0XJ2Xgd/view?usp=sharing презентация] | # 8 сентября. Префикс- и z-функция. [https://youtu.be/mX4BThZiPhY?t=1623 Лекция], [https://drive.google.com/file/d/1I0UnWivOcdsgxVxN90es2o5Ym0XJ2Xgd/view?usp=sharing презентация] | ||
| − | # 12 сентября. Алгоритм Ахо — Корасик [https://www.youtube.com/watch?v=TUuEMAjygGA&list=PLEwK9wdS5g0rBPRiw6jl6fnIMY2vne-hM&index=8 Лекция], [https://drive.google.com/file/d/1q0fHCP69HmCBHBP59rPed2jCjwONGSPn/view?usp=sharing презентация] | + | # 12 сентября. Алгоритм Ахо — Корасик. [https://www.youtube.com/watch?v=TUuEMAjygGA&list=PLEwK9wdS5g0rBPRiw6jl6fnIMY2vne-hM&index=8 Лекция], [https://drive.google.com/file/d/1q0fHCP69HmCBHBP59rPed2jCjwONGSPn/view?usp=sharing презентация] |
| − | # 15 сентября. Паросочетания. Алгоритм Куна [https://www.youtube.com/watch?v=f1Cr9yXAePk&list=PLEwK9wdS5g0rBPRiw6jl6fnIMY2vne-hM&index=9 Лекция], [https://drive.google.com/file/d/1lSZRZAkHUD-7ACc4zvsfiq8s9TJLppFp/view?usp=sharing презентация] | + | # 15 сентября. Паросочетания. Алгоритм Куна. [https://www.youtube.com/watch?v=f1Cr9yXAePk&list=PLEwK9wdS5g0rBPRiw6jl6fnIMY2vne-hM&index=9 Лекция], [https://drive.google.com/file/d/1lSZRZAkHUD-7ACc4zvsfiq8s9TJLppFp/view?usp=sharing презентация] |
# 19 сентября. Потоки. Алгоритм Форда — Фалкерсона. | # 19 сентября. Потоки. Алгоритм Форда — Фалкерсона. | ||
# 22 сентября. Параллельность в C++. | # 22 сентября. Параллельность в C++. | ||
| Строка 36: | Строка 36: | ||
# [https://official.contest.yandex.ru/contest/19611/enter/ Задачи на отрезках]. 05.09 12:30 — 19.09 23:59 | # [https://official.contest.yandex.ru/contest/19611/enter/ Задачи на отрезках]. 05.09 12:30 — 19.09 23:59 | ||
# [https://official.contest.yandex.ru/contest/19688/enter/ Задачи на строках]. 12.09 12:30 — 26.09 23:59 | # [https://official.contest.yandex.ru/contest/19688/enter/ Задачи на строках]. 12.09 12:30 — 26.09 23:59 | ||
| − | # Паросочетания и потоки. 19.09 12:30 — 03.10 23:59 | + | # [https://official.contest.yandex.ru/contest/19820/enter/ Паросочетания и потоки]. 19.09 12:30 — 03.10 23:59 |
| + | # Параллельность. 29.09 12:30 — 17.10 23:59 | ||
| + | # Перебор. 10.10 12:30 — 17.10 23:59 | ||
Версия 10:41, 19 сентября 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 12:30 — 17.10 23:59
- Перебор. 10.10 12:30 — 17.10 23:59
Оценки
Итоговая оценка: 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
