игра брюс 2048
Главная / Алгоритмы и дискретные структуры / Алгоритмы и модели вычислений / Тест 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) рекурсивность 




Главная / Алгоритмы и дискретные структуры / Алгоритмы и модели вычислений / Тест 11