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

Алгоритмы и модели вычислений - тест 7

Упражнение 1:
Номер 1
К NP-полным задачам следует отнести

Ответ:

 (1) задачу конкретизации параметров 

 (2) задачу выполнимости 

 (3) задачу разбиения 


Номер 2
Из приведенных ниже записей выделите NP-полные задачи:

Ответ:

 (1) задача 3-выполнимости 

 (2) задача 3-тождественности 

 (3) задача 3-сочетания 


Номер 3
Какие из приведенных ниже записей соответствуют NP-полным задачам?

Ответ:

 (1) Гамильтонов цикл 

 (2) вершинное покрытие 

 (3) клика 


Упражнение 2:
Номер 1
Экземпляром задачи выполнимости является

Ответ:

 (1) массив идентификаторов 

 (2) булева формула 

 (3) список констант 


Номер 2
К элементам экземпляра задачи выполнимости следует отнести

Ответ:

 (1) имена переменных 

 (2) скобки 

 (3) операции 


Номер 3
Какие операции применяются в формулах в задаче выполнимости?

Ответ:

 (1) исключающее "или" 

 (2) "не" 

 (3) "или" 


Упражнение 3:
Номер 1
Является ли задача выполнимости в нормальной конъюнктивной форме NP-полной?

Ответ:

 (1) да, является 

 (2) нет, не является 

 (3) является только для комплексных аргументов 


Номер 2
Задача выполнимости булевых формул в k-конъюнктивной нормальной форме является NP-полной при значении k

Ответ:

 (1) не меньше 3 

 (2) больше 4 

 (3) меньше 3 


Номер 3
Задача выполнимости булевых формул в 2-конъюнктивной нормальной форме имеет

Ответ:

 (1) логарифмическое решение 

 (2) экспоненциальное решение 

 (3) полиномиальное решение 


Упражнение 4:
Номер 1
Множество вершин S графа такое, что у каждого ребра графа хотя бы один из концов входит в S, носит название

Ответ:

 (1) коронарное покрытие 

 (2) вершинное покрытие 

 (3) аддитивное покрытие 


Номер 2
Число входящих в вершинное покрытие вершин является его

Ответ:

 (1) степенью 

 (2) объемом 

 (3) размером 


Номер 3
Каков размер вершинного покрытия с 10 вершинами?

Ответ:

 (1) 10 

 (2) log10 

 (3) 210-1 


Упражнение 5:
Номер 1
В чем суть задачи о вершинном покрытии?

Ответ:

 (1) в нахождении наибольшего вершинного покрытия 

 (2) в нахождении минимального вершинного покрытия 

 (3) в определении степени вхождения вершин в вершинном покрытии 


Номер 2
Множество вершин является вершинным покрытием тогда и только тогда, когда его дополнение является

Ответ:

 (1) терминальным графом 

 (2) независимым набором 

 (3) кликой 


Номер 3
Граф с n вершинами имеет вершинное покрытие размера k тогда и только тогда, когда данный граф имеет независимый набор размера

Ответ:

 (1) nlogk 

 (2) n-k 

 (3) 2n-k2 


Упражнение 6:
Номер 1
Путь, содержащий каждую вершину графа ровно один раз, носит название

Ответ:

 (1) Эйлеров цикл 

 (2) Гамильтонов цикл 

 (3) Марковский цикл 


Номер 2
Простая цепь, проходящая через все вершины графа, называется

Ответ:

 (1) когнитивной 

 (2) гамильтоновой 

 (3) темперной 


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

Ответ:

 (1) гамильтоновым циклом 

 (2) гамильтоновым разрезом 

 (3) гамильтоновым перебором 


Упражнение 7:
Номер 1
Пусть p - число вершин в данном графе. Если степень каждой вершины не меньше, чем p/2, то граф является

Ответ:

 (1) гамильтоновым 

 (2) параллельным 

 (3) остовным 


Номер 2
Если в графе степени любых двух несмежных вершин не меньше общего числа вершин в графе, то такой граф считается

Ответ:

 (1) рекурсивным 

 (2) гамильтоновым 

 (3) вариативным 


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

Ответ:

 (1) гамильтонов граф 

 (2) остовный граф 

 (3) планарный граф 


Упражнение 8:
Номер 1
Класс дополнений языков из NP носит название

Ответ:

 (1) co-NP 

 (2) re-NP 

 (3) a-NP 


Номер 2
Класс сложности co-NP определяется

Ответ:

 (1) для одного языка 

 (2) для двух языков 

 (3) для множества языков 


Номер 3
Если NP не равно co-NP, то любая задача, которая лежит и в классе NP и в классе co-NP

Ответ:

 (1) является NP-полной 

 (2) не может быть NP-полной 

 (3) является NP-тривиальной 


Упражнение 9:
Номер 1
Если задача лежит одновременно в классе NP и в классе co-NP, то она лежит

Ответ:

 (1) в классе N 

 (2) в классе P 

 (3) в классе NCP 


Номер 2
На пересечении классов NP и co-NP лежит

Ответ:

 (1) класс P 

 (2) класс NC 

 (3) класс RNP 


Номер 3
К подклассам эквивалентности класса NP следует отнести

Ответ:

 (1) NPC 

 (2) SP 

 (3) PP 


Упражнение 10:
Номер 1
Пересекаются ли классы P и NPC?

Ответ:

 (1) да, пересекаются 

 (2) нет, не пересекаются 

 (3) только в классе co-NP 


Номер 2
Сколько общих элементов имеют между собой классы co-NPC и NP?

Ответ:

 (1)

 (2) множество 

 (3) ни одного 


Номер 3
В каком классе лежит задача линейного программирования?

Ответ:

 (1) co-NPE 

 (2) RNP 

 (3) P 


Упражнение 11:
Номер 1
Максимальный полный подграф графа называется

Ответ:

 (1) остовом 

 (2) проходом 

 (3) кликой 


Номер 2
Подмножество вершин графа, такое, что между каждой парой вершин этого подмножества существует ребро и, кроме того, это подмножество не принадлежит никакому большому подмножеству с тем же свойством, носит название

Ответ:

 (1) контейнер 

 (2) клика 

 (3) пробой 


Номер 3
В неориентированном графе подмножество вершин, каждые две из которых соединены ребром графа, называется

Ответ:

 (1) дуплексом 

 (2) симплексом 

 (3) кликой 


Упражнение 12:
Номер 1
В оптимизационной задаче о клике необходимо найти в графе

Ответ:

 (1) клику максимального размера 

 (2) клику минимального размера 

 (3) клику нулевого размера 


Номер 2
Размер клики определяется

Ответ:

 (1) степенью полуисходов в графе 

 (2) количеством вершин в ней 

 (3) числом проходов по вершинному покрытию 


Номер 3
Необходимым и достаточным условием для существования клики размера k является наличие независимого множества в дополнении графа, размера не менее

Ответ:

 (1) k-1 

 (2) k 

 (3) 2k 




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