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