Алгоритмы и структуры данных 2025/2026 4 модуль КНАД
Дополнительные действия
Лекции
Лектор: Панькова Марина Геннадьевна
Лекции по понедельникам с 11:10 до 12:30 и по пятницам с 16:20 до 17:40.
Преподаватели и учебные ассистенты
| Группа | БКНАД251 | БКНАД252 | ББКНАД253 |
|---|---|---|---|
| Лектор | Панькова Марина Геннадьевна | ||
| Семинарист | Горденко Мария Константиновна | Блинов Илья Игоревич | Кондаков Семен Васильевич |
| Ассистенты | Сильвестров Василий | Латышев Иван | Шкулева Ксения |
Домашние задания
| № | Публикация | Дедлайн | Тема | Ссылка |
|---|---|---|---|---|
| 1 | 04.04.2026 | 13.04.2026 | ДЗ-1 Представление графов, обработка графов | ДЗ-1 |
| 2 | 10.04.2026 | 19.04.2026 | ДЗ-2 DFS на неориентированных графах | ДЗ-2 |
| 3 | 13.04.2026 | 24.04.2026 | ДЗ-3 DFS на ориентированных графах | ДЗ-3 |
| 4 | 17.04.2026 | 26.04.2026 | ДЗ-4 Применение BFS | ДЗ-4 |
| 5 | 22.04.2026 | 04.05.2026 | ДЗ-5 Кратчайшие пути | ДЗ-5 |
| 6 | 11.05.2026 | 20.05.2026 | ДЗ-6 MST и DSU | ДЗ-6 |
| 7 | 22.05.2026 | 07.06.2026 | ДЗ-7 Реализация структур | ДЗ-7 |
| 8 | 22.05.2026 | 07.06.2026 | ДЗ-8 Решаем задачи запросов/изменений на отрезке | ДЗ-8 |
| 9 | 03.06.2026 | 11.06.2026 | ДЗ-9 Хеши | ДЗ-9 |
| 10 | 05.06.2026 | 19.06.2026 | ДЗ-10 Применение строковых алгоритмов | ДЗ-10 |
График лекций
| № | Дата | Тема |
|---|---|---|
| 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 * Семинары))
Блокирующих работ и автоматов за курс не предусмотрено.
Домашние работы
Все домашние работы - контесты на Яндекс.Контесте.
За контест из k задач - 10 баллов. Балл за каждую задачу = 10 / k
Если в контесте есть бонусная задача, то балл за ДЗ = баллы за контест + баллы за доп.задачу
Вес работы = Минимум(3, 0.3 * (сумма баллов за все ДЗ) / 10)
Контрольная работа
Подробная информация о проведении КР на wiki
Контрольная работа (1 вариант) будет в формате контеста по теме "Алгоритмы на графах" 27 апреля на лекции. Контрольная работа (2 вариант) будет в формате контеста по теме "Алгоритмы на графах" 16 мая c 16.30 до 18.00
КР-2 вариант
Вес работы - 2 балла.
Если вы не написали КР 27 апреля, или хотите повысить результат, то переписать КР можно будет на неделе с 11.05 по 16.05 (дата и время переписывания будет определено позже).
Если вы не писали КР 27.04, то вы получаете оценку, которую получили на переписывании, иначе вы получаете за КР максимальный бал из двух попыток.
Коллоквиум
Коллоквиум подразумевает устный ответ на теоретические вопросы по изученному материалу (кроме sqrt-декомпозиция).
Подробности проведения и вопросы для подготовки будут опубликованы позже.
Вес работы - 2 балла.
Правила коллоквиума, билеты, ссылка, таблица записи - всё здесь.
Экзамен
Экзамен по итогам модуля состоит из двух независимых частей.
Итоговой балл = Минимум(3, Теоретическая часть + Контест)
Часть 1: Теоретическая часть 15-25 теоретических вопросов с открытым вариантом или с выбором ответа по темам модуля.
Часть 2: Контест 3-8 задач с автоматической проверкой решения с Яндекс.Контест.
Списывание
Все ваши домашние задания будут проверены на плагиат. При выявлении несамостоятельного выполнения (списывания или использования LLM) баллы за задачу обнуляются.