Главная / Алгоритмы и дискретные структуры /
Алгоритмы и модели вычислений / Тест 11
Алгоритмы и модели вычислений - тест 11
Упражнение 1:
Номер 1
Если P не равно NP, то для оптимизационной задачи вершинного покрытия
Ответ:
 (1) существует полиномиальный алгоритм решения 
 (2) не существует приближенного алгоритма решения 
 (3) соответствие классов NPH и NPC определяется с помощью сведения по Тьюрингу 
Номер 2
Оптимизационная задача о вершинном покрытии является
Ответ:
 (1) NP-трудной 
 (2) NP-легкой 
 (3) NP-неопределенной 
Номер 3
В задаче о вершинном покрытии необходимо найти
Ответ:
 (1) минимальное вершинное покрытие 
 (2) максимальное вершинное покрытие 
 (3) нулевое вершинное покрытие 
Упражнение 2:
Номер 1
Цикл в сети, который проходит ровно один раз через каждый узел, носит название
Ответ:
 (1) гамильтонов цикл 
 (2) эйлеров цикл 
 (3) цикл Лагранжа 
Номер 2
Гамильтонов цикл - это
Ответ:
 (1) минимальный путь в сети от истока к стоку 
 (2) цикл, который проходит ровно один раз через каждый узел 
 (3) обратное вершинное покрытие 
Номер 3
Какое количество раз гамильтонов цикл проходит через каждую вершину сети, если количество узлов равно n?
Ответ:
 (1) n-1
 
 (2) n
 
 (3) 1
 
Упражнение 3:
Номер 1
Связный граф, в котором n
вершин и n-1
ребро, носит название
Ответ:
 (1) дерево 
 (2) остов 
 (3) клика 
Номер 2
Какое количество ребер в дереве с n
вершинами?
Ответ:
 (1) n
 
 (2) n-1
 
 (3) 2n-1
 
Номер 3
Пусть граф имеет 100 вершин. Каким должно быть количество ребер, чтобы граф был деревом?
Ответ:
 (1) 100 
 (2) 101 
 (3) 99 
Упражнение 4:
Номер 1
Ациклический подграф данного графа, в который входят все вершины данного графа, носит название
Ответ:
 (1) комплексное дерево 
 (2) вершинное покрытие 
 (3) остовное дерево 
Номер 2
Остовное дерево - это
Ответ:
 (1) совокупность вершин с максимальными пропускными способностями 
 (2) ациклический подграф данного графа, в который входят все вершины данного графа 
 (3) клика, имеющая наименьшую мощность 
Номер 3
Каково количество компонент связности в остовном дереве графа, если в графе их n
?
Ответ:
 (1) n-1
 
 (2) n
 
 (3) n+1
 
Упражнение 5:
Номер 1
Сумма длин ребер остовного дерева носит название
Ответ:
 (1) длина дерева 
 (2) мощность дерева 
 (3) рекурсия дерева 
Номер 2
Остовное дерево называется минимальным, если
Ответ:
 (1) имеет минимальную длину 
 (2) имеет минимальное количество вершин 
 (3) имеет минимальное количество ребер 
Номер 3
Метод ветвей и границ используется
Ответ:
 (1) только для точного поиска решений 
 (2) только для приближенного поиска решений 
 (3) как для точного, так и для приближенного поиска решений 
Упражнение 6:
Номер 1
Общим алгоритмическим методом для нахождения оптимальных решений различных задач оптимизации является
Ответ:
 (1) метод строк и столбцов 
 (2) метод ветвей и границ 
 (3) метод конечноразностных полиномов 
Номер 2
Метод ветвей и границ является
Ответ:
 (1) конкатенационным 
 (2) рекурсивным 
 (3) комбинаторным 
Номер 3
Метод ветвей и границ основан
Ответ:
 (1) на поиске минимума и максимума функции на множестве допустимых значений 
 (2) на определении связных ребер разных классов соответствия 
 (3) на составлении матрицы инцидентности по принципу неполного вхождения ребер 
Упражнение 7:
Номер 1
Какие из приведенных ниже процедур используются в методе ветвей и границ?
Ответ:
 (1) процедура ветвления 
 (2) процедура формирования рекурсивных циклов 
 (3) процедура векторизации 
Номер 2
Из приведенных ниже записей выделите этапы метода ветвей и границ:
Ответ:
 (1) нахождение оценок 
 (2) скаляризация 
 (3) ветвление 
Номер 3
Разбиение области допустимых решений на подобласти меньших размеров в методе ветвей и границ представляет собой
Ответ:
 (1) процедуру детерминации 
 (2) процедуру полиномизации 
 (3) процедуру ветвления 
Упражнение 8:
Номер 1
Подобласти, образовавшиеся в результате процедуры ветвления в методе ветвей и границ, образуют дерево, называемое
Ответ:
 (1) деревом связей 
 (2) деревом выборки 
 (3) деревом поиска 
Номер 2
Если при решении задачи минимизации методом ветвей и границ нижняя граница для подобласти A
дерева поиска больше, чем верхняя граница какой-либо ранее просмотренной подобласти B
, то
Ответ:
 (1) подобласть A
может быть исключена из дальнейшего рассмотрения 
 (2) подобласть B
не рассматривается для потенциального решения 
 (3) метод ветвей и границ не может быть реализован 
Номер 3
Если нижняя граница для узла дерева совпадает с верхней границей, то это значение является
Ответ:
 (1) минимумом функции 
 (2) максимумом функции 
 (3) нулем функции 
Упражнение 9:
Номер 1
Работы при многопроцессорном расписании выполняются
Ответ:
 (1) без прерываний 
 (2) без переключений 
 (3) с рекурсиями 
Номер 2
При многопроцессорном расписании в фиксированный момент времени один процессор может выполнять
Ответ:
 (1) только одну работу 
 (2) две и более работ 
 (3) множество работ 
Номер 3
В фиксированный момент времени при многопроцессорном расписании одна работа выполняется
Ответ:
 (1) только одним процессором 
 (2) двумя или более процессорами 
 (3) множеством процессоров 
Упражнение 10:
Номер 1
Максимальная длительность работы на процессоре представляет собой
Ответ:
 (1) модуль сложности процессорного расписания 
 (2) длину процессорного расписания 
 (3) коэффициент быстродействия 
Номер 2
Аналог задачи многопроцессорного расписания в виде задачи распознавания свойств является
Ответ:
 (1) NP-полной задачей 
 (2) NP-однозначной задачей 
 (3) NP-вариативной задаче 
Номер 3
Задача многопроцессорного расписания является
Ответ:
 (1) NP-зависимой 
 (2) NP-трудной 
 (3) NP-легкой 
Упражнение 11:
Номер 1
Множество всех возможных назначений работ на процессоры в дереве поиска представляется в виде
Ответ:
 (1) узлов 
 (2) корня 
 (3) листьев 
Номер 2
При решении задачи многопроцессорного расписания для m процессоров с помощью метода ветвей и границ количество вершин первого уровня дерева поиска может достигать
Ответ:
 (1) m
 
 (2) m-1
 
 (3) m+1
 
Номер 3
При решении задачи многопроцессорного расписания для m процессоров с помощью метода ветвей и границ количество вершин любого уровня дерева поиска не превышает числа
Ответ:
 (1) 2m
 
 (2) 2m-1
 
 (3) m
 
Упражнение 12:
Номер 1
Если при раскрытии всех скобок и приведения подобных слагаемых в полиноме все слагаемые будут взаимоуничтожены, такой полином является
Ответ:
 (1) рандомизированным 
 (2) тождественно равным нулю 
 (3) детерминированным 
Номер 2
Какими из приведенных ниже свойств обладает вероятность?
Ответ:
 (1) вероятность события больше или равна нулю 
 (2) вероятность в пустом множестве равна 1 
 (3) вероятность объединения событий равна сумме их вероятностей 
Номер 3
Какая величина соответствует частоте появления события?
Ответ:
 (1) вероятность 
 (2) параметричность 
 (3) рекурсивность