Алгоритмы и структуры данных 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 | 18.05.2026 | 03.06.2026 | ДЗ-7 Реализация структур | |
| 8 | 18.05.2026 | 03.06.2026 | ДЗ-8 Решаем задачи запросов/изменений на отрезке | |
| 9 | 03.06.2026 | 10.06.2026 | ДЗ-9 Хеши | |
| 10 | 05.06.2026 | 19.06.2026 | ДЗ-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) | sqrt-декомпозиция |
| 15 | 30.05.2026 (уточняется) | Коллоквиум |
| 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) | Построение префиксного дерева бора для обработки строк |
| 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
Контрольная работа будет в формате контеста по теме "Алгоритмы на графах" 27 апреля на лекции.
Вес работы - 2 балла.
Если вы не написали КР 27 апреля, или хотите повысить результат, то переписать КР можно будет на неделе с 11.05 по 16.05 (дата и время переписывания будет определено позже).
Если вы не писали КР 27.04, то вы получаете оценку, которую получили на переписывании, иначе вы получаете за КР максимальный бал из двух попыток.
Коллоквиум
Коллоквиум подразумевает устный ответ на теоретические вопросы по изученному материалу (кроме sqrt-декомпозиция).
Подробности проведения и вопросы для подготовки будут опубликованы позже.
Вес работы - 2 балла.
Экзамен
Экзамен по итогам модуля состоит из двух независимых частей.
Итоговой балл = Минимум(3, Теоретическая часть + Контест)
Часть 1: Теоретическая часть 15-25 теоретических вопросов с открытым вариантом или с выбором ответа по темам модуля.
Часть 2: Контест 3-8 задач с автоматической проверкой решения с Яндекс.Контест.
Списывание
Все ваши домашние задания будут проверены на плагиат. При выявлении несамостоятельного выполнения (списывания или использования LLM) баллы за задачу обнуляются.