Базовые и "продвинутые" алгоритмы для школьников - тест 7

Для чего используется алгоритм Прима?

Граф в алгоритме Прима является

Каким должен быть граф в алгоритме Прима?

Входом алгоритма Прима является

Выходом алгоритма Прима является

От чего зависит асимптотика алгоритма Прима?

Если приоритетная очередь вершин графа реализована как обычный массив, то операция извлечения минимальных вершин выполняется

Если приоритетная очередь вершин графа реализована как бинарная пирамида, то операция извлечения минимальных вершин выполняется

Если приоритетная очередь вершин графа реализована как фибоначчиевая пирамида, то операция извлечения минимальных вершин выполняется

Метод решения задач с оптимальной подструктурой и перекрывающимися подзадачами носит название

Задачи динамического программирования характеризуются

Формулировка оптимизационной задачи в рекурсивной форме осуществляется

Положение о том, что оптимальное решение подзадач меньшего размера может быть использовано для решения исходной задачи, является принципом

Подзадачи, которые используются для решения некоторого количества задач большего размера, носят название

Из приведенных ниже записей выделите задачи с перекрывающимися подзадачами:

Сохранение в памяти подзадач для их использования носит название

К типам динамического программирования следует отнести

Из приведенных ниже записей выделите типы динамического программирования:

Граф взаимосвязей переменных несериального динамического программирования представляет собой

Несериальное динамическое программирование рассматривает множество ограничений и целевую функцию

Одним из основных свойств задач, решаемых с помощью динамического программирования, является

К методам решения задачи нахождения наибольшей общей подпоследовательности следует отнести

Время работы полного перебора при решении задачи задачи нахождения наибольшей общей подпоследовательности будет равно

Время работы алгоритма нахождения наибольшей общей подпоследовательности методами динамического программирования будет

В задаче поиска наибольшей увеличивающейся подпоследовательности такая подпоследовательность

Решение задачи поиска наибольшей увеличивающейся подпоследовательности занимает в худшем случае времени

Если строка является перестановкой, решение задачи поиска наибольшей увеличивающейся подпоследовательности занимает времени

К операциям редактирования строки следует отнести

Мера разницы двух последовательностей символов (строк) относительно минимального количества операций вставки, удаления и замены, необходимых для перевода одной строки в другую, носит название

Расстояние Левенштейна применяется

Дистанция Левенштейна, как минимум, равна

Если строки равны, дистанция Левенштейна равна

Если обе строки имеют одинаковую длину, то расстояние Хэмминга является

Суммы биномиальных коэффициентов на диагоналях треугольника Паскаля являются

К задачам комбинаторной оптимизации следует отнести

Для нахождения кратчайших расстояний между всеми вершинами взвешенного ориентированного графа используется