Главная / Алгоритмы и дискретные структуры /
Языки и исчисления / Тест 2
Языки и исчисления - тест 2
Упражнение 1:
Номер 1
Схема "И - НЕ" имеет:
Ответ:
 (1) 2 входа и 2 выхода 
 (2) 1 вход и 2 выхода 
 (3) 2 входа и 1 выход 
Номер 2
Схема "ИЛИ - НЕ" имеет:
Ответ:
 (1) 2 входа и 2 выхода 
 (2) 1 вход и 2 выхода 
 (3) 2 входа и 1 выход 
Номер 3
Схема "ИСКЛЮЧАЮЩЕЕ - ИЛИ" имеет:
Ответ:
 (1) 2 входа и 2 выхода 
 (2) 1 вход и 2 выхода 
 (3) 2 входа и 1 выход 
Упражнение 2:
Номер 1
Сложность булевой функции относительно базисных функций - это:
Ответ:
 (1) максимальный размер схемы из B-элементов 
 (2) минимальный размер схемы из B-элементов 
 (3) мощность множества B 
Номер 2
Полным набором B булевых функций называется набор, для которого:
Ответ:
 (1) схемы B-элементов всегда максимальны 
 (2) некоторая булева функция задаваемая задаваема схемой из B-элементов 
 (3) любая булева функция задаваемая задаваема схемой из B-элементов 
Номер 3
Размером схемы называется число:
Ответ:
 (1) входов 
 (2) проводников 
 (3) циклов 
Упражнение 3:
Номер 1
Если A
и B
- полные наборы булевых функций, то для любой функции:
Ответ:
 
(1)  
 
(2)  
 
(3)  
Номер 2
Сложность любой булевой -местной функций при наибольшем размере их схем:
Ответ:
 
(1) не превосходит
при
и больших
 
 
(2) не превосходит
при
и больших
 
 
(3) равна
при
и больших
 
Номер 3
Сложность большинства булевой -местной функций при наибольшем размере их схем:
Ответ:
 
(1) не меньше
при
и больших
 
 
(2) не меньше
при
и больших
 
 
(3) равна
при
и больших
 
Упражнение 4:
Номер 1
Количество всех -местных булевых функций равно:
Ответ:
 
(1)  
 
(2)  
 
(3) , где
 
Номер 2
Количество всех различных -местных схем размера оценивается:
Ответ:
 
(1)  
 
(2)  
 
(3)  
Номер 3
При некотором сложность большинства булевых -местных функций:
Ответ:
 
(1) не больше
 
 
(2) не меньше
 
 (3) не меньше  
Упражнение 5:
Номер 1
Если B - полный базис, то существует :
Ответ:
 
(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) размера
O и глубины
 
Номер 2
Для вычисления функции голосования существует схема:
Ответ:
 
(1) размера
и глубины
,
 
 (2) размера и глубины  
 
(3) размера
и глубины
 
Номер 3
Если - минимальная глубина схемы, вычисляющая функцию , то:
Ответ:
 
(1) ,
 
 
(2) ,
 
 
(3) ,
 
Упражнение 8:
Номер 1
Отношение x mod y=0
(x, y
- натуральные) является:
Ответ:
 (1) симметричным, рефлексивным, транзитивным  
 (2) несимметричным, рефлексивным, нетранзитивным 
 (3) симметричным, рефлексивным, нетранзитивным 
Номер 2
Отношение x>y
(x, y
- натуральные) является:
Ответ:
 (1) симметричным, рефлексивным, транзитивным  
 (2) несимметричным, нерефлексивным, транзитивным 
 (3) симметричным, рефлексивным, нетранзитивным 
Номер 3
Отношение x + 5=y
(x, y
- натуральные) является:
Ответ:
 (1) симметричным, рефлексивным, транзитивным  
 (2) несимметричным, нерефлексивным, нетранзитивным 
 (3) симметричным, рефлексивным, нетранзитивным