Алгоритмы и структуры данных-1 2021/2022 4 модуль (КНАД)
Страница 2 модуля: Алгоритмы и структуры данных – 1
Содержание
Лекции и ДЗ
Лектор: Куренков Владимир Вячеславович
| № | Дата | Тема | ДЗ | Дедлайн |
|---|---|---|---|---|
| 1 | 05.04 | Теория чисел. Алгоритм Евклида. Быстрое возведение в степень. Решето Эратосфена. | ДЗ1 | 20.04 |
| 2 | 07.04 | Повтор. Бинарный поиск, бинпоиск по ответу. Тернарный поиск. Взвешенная дихотомия. | ДЗ2 | 22.04 |
| 3 | 12.04 | Задача RMQ/RSQ. Префиксные суммы, разреженные таблицы. | ДЗ3 | 30.04 |
| 4 | 14.04 | Корневая эвристика. Алгоритм МО. | ДЗ3 | - |
| 5 | 19.04 | Повтор. Куча. Дерево отрезков. | ДЗ4 | - |
| 6 | 21.04 | Дерево отрезков. Групповые операции. | ДЗ4 | 11.05 |
| 7 | 26.04 | Обход в глубину: связность, циклы, двудольность. | ДЗ5 | 18.05 |
| 8 | 28.04 | Динамика на деревьях. Диаметр дерева. Центр дерева. | - | - |
| - | 12.05 | Защита ДЗ 1-4 | Защита ДЗ1-4 | 14.06 |
| 9 | 14.05 | Задача нахождения кратчайших путей в графе. Общий алгоритм. Обход в ширину. | ДЗ6 | - |
| 10 | 17.05 | Алгоритм Дейкстры. | ДЗ6 | 12.06 |
| 11 | 19.05 | Алгоритм Форда-Беллмана. Алгоритм Левита. | ДЗ7 | 18.06 |
| 12 | 24.05 | Алгоритм Флойда. | ДЗ7 | - |
| 13 | 26.05 | Система непересекающихся множеств. | ДЗ8 | 20.06 |
| 14 | 31.05 | Алгоритм Краскала | ДЗ8 | - |
| 15 | 07.06 | Структуры данных. Куча. Дерево поиска. Декартово дерево | - | - |
| 16 | 09.06 | Защита ДЗ 5-6 | - | - |
| 17 | 11.06 | Двоичные деревья поиска. Балансировка | - | - |
| - | 14.06 | Защита ДЗ 7-8 | - | - |
| - | 16.06 | Переписывание защиты по выбору студента | - | - |
Система оценки
Итоговой оценкой за курс является оценка за модуль 4.
Оценка за модуль 4: 0.2 * ДЗ1-4 + 0.2 * ДЗ5-6 + 0.2 * ДЗ7-8 + 0.1 * Семинары + 0.3 * Экзамен + 0,1 * Бонус
Оценка за модуль 4 может быть выставлена автоматом, если выполнены два условия:
- текущая оценка ((0.2 * ДЗ1-4 + 0.2 * ДЗ5-6 + 0.2 * ДЗ7-8 + 0.1 * Семинары + 0,1 * Бонус) / 0.7) >= 8
- оценка за семинары >= 8
Автоматом выставляется текущая оценка.
Таблица с оценками: https://docs.google.com/spreadsheets/d/15JlUgoYD14KAEuObkgZ-BQ04MhSUmguU8jkMIPn1mOo/edit#gid=0
Записи лекций и семинаров
https://disk.yandex.ru/d/lM4ozaqE7wQ9Rw
Бонусные баллы
Бонусные баллы можно получить следующим образом:
- Решение задачи со звездочкой из домашнего контеста: 1 балл
- Дорешка контеста защиты ДЗ1-4: по 1 баллу за каждую задачу, кроме задачи А. Её дорешивание даёт 0,5 балла.
- Если на защите ДЗ5-6 или ДЗ7-8 Ваша оценка до применения операции МИН будет больше 10, то дополнительные баллы идут в бонус. Например, если Вы получили 11 баллов, то за блок ДЗ выставляется 10 и Вы получаете 1 бонусный балл.
Выполнение ДЗ. Правила оценивания
После каждой лекции выдается контест, как правило, состоящий из 10 задач. Дедлайн - в 23:59, дня, указанного в таблице. В течение недели после дедлайна разрешается дорешивать задачи домашнего контеста за половину стоимости.
Защита ДЗ. Общие положения
Защита ДЗ происходит, как во 2 модуле, в онлайн-формате с использованием прокторинга. Прокторинг как на курсах ОиМП: http://wiki.cs.hse.ru/%D0%9A%D0%A0_1_%D0%9E%D0%B8%D0%9C%D0%9F-3_2021
На защите ДЗ разрешается использовать эту вики-страницу, конспект, сайт https://en.cppreference.com/w/, а также свои решения задач из контестов с домашними заданиями.
Предварительная оценка за блок ДЗ (обозначатся в формулах как ДЗ) считается как средняя оценка за все ДЗ этого блока.
Защита ДЗ1-4
Защита состоит из 6 задач, 3 из которых бонусные. Итоговая оценка за блок ДЗ определяется следующим образом:
- Если на защите решено 0 задач: max(ДЗ * 0.9, ДЗ - 0.15)
- Если на защите решена 1 задача: ДЗ
- Если на защите решено больше 1 задачи: ДЗ + бонус к итоговой оценке
Защита ДЗ5-6
Пройдёт в устном формате. Вы подключитесь к конференции в зуме в указанное время (распределение будет позже). За смелость Вам тут же будет отдан 1 балл. После этого Вам зададут 3 простых вопроса по пройденным темам, ответ на которые не предполагает длительной подготовки. Каждый ответ оценивается по 3ех балльной шкале. За частично верный ответ можно получить дробные баллы (например, 2.5). Сумма баллов за ответы на вопросы и будет итоговой оценкой за защиту. Формулы вычисления итоговой оценки за ДЗ5-6:
- При оценке 0 (защита пропущена по неуважительной причине): ДЗ * 0,7
- Если получено 1 - 4,5 балла: ДЗ * 0,8 + ОЗ * 0,3
- Если получено 5 - 8 баллов: МИН(10, ДЗ * 0,9 + ОЗ * 0,2)
- Если получено 8,5 - 10 баллов: МИН(10, ДЗ + ОЗ * 0,2)
ДЗ - средняя неокругленная оценка за ДЗ5-6, ОЗ - оценка за защиту
Защита ДЗ7-8
Пройдет в том же формате, что и защита ДЗ5-6. Формулы итоговой оценки за блок ДЗ те же.
Экзамен
Состоится 25.06 в устном формате.
Формат проведения экзамена: https://docs.google.com/document/d/1lHj5pLjN9uX4FH4GcT5e_LtyNl90LkdG-uy_eJ0P3EU/edit?usp=sharing
