Языки и исчисления

Упражнение 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) не превосходит math

при

и больших

(2) не превосходит math

при

и больших

(3) равна math

при

и больших

Номер 3

Сложность большинства булевой -местной функций при наибольшем размере  их схем:

Ответ:

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

при

и больших

(2) не меньше math

при

и больших

(3) равна math

при

и больших

Упражнение 4:

Номер 1

Количество всех -местных булевых функций равно:

Ответ:

(1)

(2)

(3)

, где

Номер 2

Количество всех различных -местных схем размера  оценивается:

Ответ:

(1)

(2)

(3)

Номер 3

При некотором  сложность большинства булевых -местных функций:

Ответ:

(1) не больше math

(2) не меньше math

(3) не меньше

C{\raise0.7ex\hbox{${2^n }$} \!\mathord{\left/
 {\vphantom {{2^n } n}}\right.\kern-\nulldelimiterspace}
\!\lower0.7ex\hbox{$n$}}

Упражнение 5:

Номер 1

Если B - полный базис, то существует :

Ответ:

(1)

(2)

(3)

Номер 2

Для сложения двух -разрядных двоичных чисел:

Ответ:

(1) не существует схемы размера math

(2) существует схема размера math

(3) существует схема размера math

Номер 3

Для сложения двух -разрядных двоичных чисел:

Ответ:

(1) не существует схемы размера math

и глубины

(2) существует схема размера math

и глубины

(3) существует схема размера math

и глубины

Упражнение 6:

Номер 1

Для умножения двух -разрядных двоичных чисел существует схема:

Ответ:

(1) размера math

и глубины

(2) размера math

и глубины

(3) размера math

и глубины

Номер 2

Для умножения двух -разрядных двоичных чисел существует схема:

Ответ:

(1) размера math

и глубины

(2) размера math

и глубины

(3) размера math

и глубины

Номер 3

Вычитание двух -разрядных двоичных чисел по модулю  выполнима схема:

Ответ:

(1) размера math

и глубины

(2) размера math

и глубины

(3) размера math

и глубины

Упражнение 7:

Номер 1

Для вычисления функции голосования существует схема:

Ответ:

(1) размера math

и глубины

(2) размера math

и глубины

(3) размера math

O и глубины math

Номер 2

Для вычисления функции голосования существует схема:

Ответ:

(1) размера math

и глубины

,

(2) размера

O\left( {{\raise0.5ex\hbox{$\scriptstyle n$}
\kern-0.1em/\kern-0.15em
\lower0.25ex\hbox{$\scriptstyle 2$}}} \right)

и глубины

O\left( {{\raise0.5ex\hbox{$\scriptstyle n$}
\kern-0.1em/\kern-0.15em
\lower0.25ex\hbox{$\scriptstyle 2$}}} \right)

(3) размера math

и глубины

Номер 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) симметричным, рефлексивным, нетранзитивным

Языки и исчисления - тест 2