imported>Pankovamg: Migrated current public revision from wiki.cs.hse.ru

2026-06-03T15:19:25Z

Migrated current public revision from wiki.cs.hse.ru

Новая страница

== Лекции ==

Лектор: [https://www.hse.ru/org/persons/859152775 Панькова Марина Геннадьевна]

Лекции по '''понедельникам''' с 11:10 до 12:30 и по '''пятницам''' с 16:20 до 17:40.

[https://disk.yandex.ru/d/iwFlha6NmnWZ-A Ссылка на папку с записями лекций]

== Преподаватели и учебные ассистенты ==

{| class="wikitable" style="text-align:center"
|-
! Группа !! БКНАД251 || БКНАД252 || ББКНАД253
|-
|| Лектор ||colspan="3"| Панькова Марина Геннадьевна
|-
|| Семинарист || Горденко Мария Константиновна || Блинов Илья Игоревич || Кондаков Семен Васильевич
|-
|| Ассистенты || Сильвестров Василий || Латышев Иван || Шкулева Ксения
|}

== Домашние задания ==

{| class="wikitable"
|-
! № !! Публикация !! Дедлайн !! Тема !! Ссылка
|-
| 1 || 04.04.2026 || 13.04.2026 || ДЗ-1 Представление графов, обработка графов || [https://official.contest.yandex.ru/contest/92937/enter/ ДЗ-1]
|-
| 2 || 10.04.2026 || 19.04.2026 || ДЗ-2 DFS на неориентированных графах || [https://official.contest.yandex.ru/contest/93167/enter/ ДЗ-2]
|-
| 3 || 13.04.2026 || 24.04.2026 || ДЗ-3 DFS на ориентированных графах || [https://official.contest.yandex.ru/contest/93246/enter/ ДЗ-3]
|-
| 4 || 17.04.2026 || 26.04.2026 || ДЗ-4 Применение BFS || [https://official.contest.yandex.ru/contest/93495/enter/ ДЗ-4]
|-
| 5 || 22.04.2026 || 04.05.2026 || ДЗ-5 Кратчайшие пути || [https://official.contest.yandex.ru/contest/93616/enter/ ДЗ-5]
|-
| 6 || 11.05.2026 || 20.05.2026 || ДЗ-6 MST и DSU || [https://official.contest.yandex.ru/contest/94199/enter/ ДЗ-6]
|-
| 7 || 22.05.2026 || 07.06.2026 || ДЗ-7 Реализация структур || [https://official.contest.yandex.ru/contest/94278/enter/ ДЗ-7]
|-
| 8 || 22.05.2026 || 07.06.2026 || ДЗ-8 Решаем задачи запросов/изменений на отрезке || [https://official.contest.yandex.ru/contest/94280/enter/ ДЗ-8]
|-
| 9 || 03.06.2026 || 11.06.2026 || ДЗ-9 Хеши || [https://official.contest.yandex.ru/contest/94282/enter/ ДЗ-9]
|-
| 10 || 05.06.2026 || 19.06.2026 || ДЗ-10 Применение строковых алгоритмов || [https://official.contest.yandex.ru/contest/94284/enter/ ДЗ-10]
|}

== График лекций ==

{| class="wikitable"
|-
! № !! Дата !! Тема
|-
| 1 || 03.04.2026 (16:20 - 17:40)|| Представление графов в компьютере
|-
| 2 || 06.04.2026 (11:10 - 12:30)|| DFS. Связность. Поиск компонент связности в графе
|-
| 3 || 10.04.2026 (16:20 - 12:30)|| DFS. Проверка графа на двудольность. Диаметр и центр дерева. Поиск цикла в графе
|-
| 4 || 13.04.2026 (11:10 - 12:30)|| DFS. Топологическая сортировка. Конденсация графа
|-
| 5 || 17.04.2026 (16:20 - 12:30)|| Задача построения дерева кратчайших расстояний: обход в ширину
|-
| 6 || 20.04.2026 (11:10 - 12:30)|| Поиск кратчайшего пути во взвешенном графе. Алгоритм Дейкстры
|-
| 7 || 24.04.2026 (16:20 - 12:30)|| Алгоритмы Флойда и Форда-Беллмана. Поиск циклов отрицательного веса
|-
| 8 || 27.04.2026 (11:10 - 12:30)|| '''Контрольная работа'''
|-
| 9 || 11.05.2026 (11:10 - 12:30)|| Поиск минимального остовного дерева с помощью алгоритма Прима
|-
| 10 || 15.05.2026(16:20 - 12:30)|| Задача объединить-найти. Система непересекающихся множеств. Алгоритм Краскала
|-
| 11 || 18.05.2026 (11:10 - 12:30)|| Решение задачи запроса на отрезке. Разреженные таблицы
|-
| 12 || 22.05.2026 (16:20 - 12:30)|| Реализация структуры дерево отрезков
|-
| 13 || 25.05.2026 (11:10 - 12:30)|| Групповые операции на дереве отрезков
|-
| 14 || 29.05.2026 (16:20 - 12:30)|| Построение дерева Фенвика, применение для решения задач
|-
| || 30.05.2026 (уточняется) || '''Коллоквиум'''
|-
| 15 || 01.05.2026 (11:10 - 12:30)|| Хеширование. построение префиксных хешей.
|-
| 16 || 03.06.2026 (18:10 - 19:30)|| Хеширование (продолжение). Построение префикс-функции от строки
|-
| 17 || 05.06.2026 (16:20 - 12:30)|| Решение задачи КМП с помощью z-функции
|-
| 18 || 08.06.2026 (11:10 - 12:30)|| Построение префиксного дерева бора для обработки строк
|-
| 19 || 15.06.2026 (11:10 - 12:30)|| sqrt-декомпозиция
|-
| 20 || 19.06.2026 (16:20 - 12:30)|| Консультационное занятие
|}

== Система оценки ==

Оценка за весь курс: Минимум (10, Округление(0.3 * ДЗ + 0.2 * КР + 0.2 * Коллоквиум + 0.3 * Экзамен + 0.1 * Семинары))

Блокирующих работ и автоматов за курс не предусмотрено.

Ведомости: [https://docs.google.com/spreadsheets/d/1LthrKH_AD4Nty9CK4EO_hzSKLQQZ5HYG7K8T9WIyH1c/edit?gid=437380964#gid=437380964 251], [https://docs.google.com/spreadsheets/d/1yOHumwmWxElCLyFdw9OZHFd0AG_yF7S5iAUvKD09lhk/edit?gid=437380964#gid=437380964 252], [https://docs.google.com/spreadsheets/d/15J9gXb4WOBI7POM8a1x1fHoRIr4TxArV-W3SE-Lf_m8/edit?gid=437380964#gid=437380964 253]

== Домашние работы ==

Все домашние работы - контесты на Яндекс.Контесте.

За контест из k задач - 10 баллов. Балл за каждую задачу = 10 / k

Если в контесте есть бонусная задача, то балл за ДЗ = баллы за контест + баллы за доп.задачу

Вес работы = Минимум(3, 0.3 * (сумма баллов за все ДЗ) / 10)

== Контрольная работа ==

Подробная информация о проведении КР на [[Контрольная работа АиСД 4 2025/2026|wiki]]

Контрольная работа (1 вариант) будет в формате контеста по теме "Алгоритмы на графах" 27 апреля на лекции.
Контрольная работа (2 вариант) будет в формате контеста по теме "Алгоритмы на графах" 16 мая c 16.30 до 18.00
[https://official.contest.yandex.ru/contest/94047/enter/ КР-2 вариант]

Вес работы - 2 балла.

Если вы не написали КР 27 апреля, или хотите повысить результат, то переписать КР можно будет на неделе с 11.05 по 16.05
(дата и время переписывания будет определено позже).

Если вы не писали КР 27.04, то вы получаете оценку, которую получили на переписывании, иначе вы получаете за КР максимальный бал из двух попыток.

== Коллоквиум ==

Коллоквиум подразумевает устный ответ на теоретические вопросы по изученному материалу (кроме sqrt-декомпозиция).

Подробности проведения и вопросы для подготовки будут опубликованы позже.

Вес работы - 2 балла.

Правила коллоквиума, билеты, ссылка, таблица записи - [https://docs.google.com/spreadsheets/d/1VHB21KgweFT8O5Wt9gbRsJQjUg-CX6yLG97wRbu1GJY/edit?gid=495272971#gid=495272971 всё здесь].

== Экзамен ==

Экзамен по итогам модуля состоит из двух независимых частей.

Итоговой балл = Минимум(3, Теоретическая часть + Контест)

'''Часть 1:''' Теоретическая часть
15-25 теоретических вопросов с открытым вариантом или с выбором ответа по темам модуля.

'''Часть 2:''' Контест
3-8 задач с автоматической проверкой решения с Яндекс.Контест.

== Списывание ==

Все ваши домашние задания будут проверены на плагиат.
При выявлении несамостоятельного выполнения (списывания или использования LLM) баллы за задачу обнуляются.

Алгоритмы и структуры данных 2025/2026 4 модуль КНАД - История изменений

imported>Pankovamg: Migrated current public revision from wiki.cs.hse.ru