Алгоритмы и структуры данных 2 2020/2021 — различия между версиями

Материал из Wiki - Факультет компьютерных наук
Перейти к: навигация, поиск
(→‎Лекции)
(→‎Лекции)
Строка 24: Строка 24:
 
# 22 сентября. Параллельность в C++. [https://www.youtube.com/watch?v=tyAFU7H_Z-E&list=PLEwK9wdS5g0rBPRiw6jl6fnIMY2vne-hM&index=14 Лекция], [https://drive.google.com/file/d/19oARvl7S7vraE2wACS75qxf8Bf_HxMT7/view?usp=sharing презентация], [https://drive.google.com/file/d/1Jp7lyIv1xgnrWE7nG6KSIWG4gD1Y50ql/view?usp=sharing код], [https://drive.google.com/file/d/1eNE-vxRH2UeSUXqJelvtDIyluThkLC5K/view?usp=sharing код  с семинара]
 
# 22 сентября. Параллельность в C++. [https://www.youtube.com/watch?v=tyAFU7H_Z-E&list=PLEwK9wdS5g0rBPRiw6jl6fnIMY2vne-hM&index=14 Лекция], [https://drive.google.com/file/d/19oARvl7S7vraE2wACS75qxf8Bf_HxMT7/view?usp=sharing презентация], [https://drive.google.com/file/d/1Jp7lyIv1xgnrWE7nG6KSIWG4gD1Y50ql/view?usp=sharing код], [https://drive.google.com/file/d/1eNE-vxRH2UeSUXqJelvtDIyluThkLC5K/view?usp=sharing код  с семинара]
 
# 26 сентября. [https://official.contest.yandex.ru/contest/19945/enter/ Контрольная работа] по первым 6 лекциям: задачи на отрезках, строки, паросочетания и потоки.
 
# 26 сентября. [https://official.contest.yandex.ru/contest/19945/enter/ Контрольная работа] по первым 6 лекциям: задачи на отрезках, строки, паросочетания и потоки.
−
# 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 код]
+
# 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 октября. P и NP.
 
# 6 октября. P и NP.

Версия 18:23, 5 октября 2020

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

Расписание лекций:
вторник 09:30 – 10:50
суббота 11:10 – 12:30

Канал для объявлений:
https://t.me/aisd2_20

Консультации:
hse@poldnev.ru

Ассистенты:


Лекции

  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 октября. P и NP.
  12. 10 октября. Эвристики в рекурсивном переборе.
  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 — 10.10 23:59 (ручная проверка, одна задача засчитывается за две)
  5. Перебор. 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)

Источник — «http://wiki.cs.hse.ru/index.php?title=Алгоритмы_и_структуры_данных_2_2020/2021&oldid=45678»