Графы, алгоритм Дейкстры и динамическое программирование — тест

Маршрут в навигаторе, рекомендации друзей в соцсети, расписание с зависимостями задач — всё это задачи на графах. Модуль одиннадцатого класса курса «Программирование» собирает главные алгоритмические идеи: обходы графа, кратчайшие пути, жадный выбор и динамическое программирование. Работа проверяет, умеет ли ученик выбрать подходящую идею и проследить её на маленьком примере.

Содержание

Граф, вершины и рёбра, ориентированные и взвешенные графы; матрица смежности и списки смежности и их затраты памяти. Обход в ширину с очередью и обход в глубину со стеком или рекурсией, кратчайший путь по числу рёбер в невзвешенном графе. Алгоритм Дейкстры и условие неотрицательности весов. Жадные алгоритмы — выдача сдачи, выбор заявок — и пример, когда жадный выбор ошибается. Динамическое программирование: подзадачи, рекуррентное соотношение, таблица значений; число путей по клеткам, «лесенка», рюкзак. Целочисленные алгоритмы — алгоритм Евклида.

Задания

Пятнадцать заданий: найти длину кратчайшего пути по таблице весов, посчитать число способов по рекуррентной формуле, назвать порядок вершин при обходе в ширину, сопоставить задачу и алгоритм, восстановить шаги алгоритма Дейкстры, заполнить пропуски в описании динамического программирования. Тридцать минут.

Разбор

Пояснения к каждому заданию показывают ход вычисления: какие вершины уже зафиксированы у Дейкстры, почему жадная сдача монетами 1, 3 и 4 ошибается для суммы 6 и как таблица динамики избавляет от повторного решения одних и тех же подзадач.

Применение

Работа рассчитана на одиннадцатый класс после модуля об алгоритмах и структурах данных; её можно использовать и как диагностику перед подготовкой к олимпиадам и профильному экзамену, где эти идеи встречаются постоянно.

Организация тестирования

Ученик отвечает как с компьютера, так и с телефона; специальные программы не требуются — тест открывается в обычном браузере. Период выполнения задаётся гибко, поэтому работу проводят и в классе, и дома. Система контроля добросовестности регистрирует переходы в посторонние вкладки и приложения во время выполнения.