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

Карта дорог, схема связей и дерево вариантов — для программы это один и тот же объект. Научившись работать с графом, вы решаете сразу целый класс задач.

Что проверяется

Деревья: корень, узлы и листья, родитель и потомки, высота дерева. Двоичные деревья поиска: правило размещения ключей, добавление и поиск, зависимость числа шагов от высоты, сбалансированность. Обходы дерева и вычисление выражений по дереву разбора. Графы: вершины и рёбра, ориентированные и неориентированные, взвешенные графы, степень вершины, путь и цикл, связность. Представление графа: матрица смежности, список рёбер, списки смежности, выбор представления по плотности. Алгоритмы на графах: обход в ширину и в глубину, поиск кратчайшего пути алгоритмом Дейкстры, каркас минимального веса. Динамическое программирование: разбиение задачи на перекрывающиеся подзадачи, таблица промежуточных результатов, числа Фибоначчи, задача о лестнице, наибольшая общая подпоследовательность.

Почему рекурсия без таблицы медленна

Прямой рекурсивный расчёт чисел Фибоначчи пересчитывает одни и те же значения многократно. Сохранение уже вычисленного превращает экспоненциальный алгоритм в линейный.

Матрица смежности или списки

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

Как устроена работа

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

Где и как проходить тест

Комплект работает и на школьном компьютере, и на личном смартфоне ученика. Период выполнения задаётся гибко, поэтому работу проводят и в классе, и дома. Для честности предусмотрена защита от списывания: система отслеживает переходы ученика на другие вкладки и в сторонние приложения.