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

<<- Назад к вопросам

Если - минимальная глубина схемы, вычисляющая функцию , то:

(Отметьте один правильный вариант ответа.)

Варианты ответа

$fsize(f) = C_1^{depth(f)}$ , $depth(f) = C_2 \log _2 fsize(f)$

$fsize(f) > C_1^{depth(f)}$ , $depth(f) > C_2 \log _2 fsize(f)$

$fsize(f) \le C_1^{depth(f)}$ , $depth(f) \le C_2 \log _2 fsize(f)$ (Верный ответ)

Похожие вопросы

Контрпример к секвенции $A \mapsto B$ будет контрпримером к формуле ( $\wedge A$ - конъюнкция, $\vee A$ - дизъюнкция формул из А)

Перейти

Верно утверждение для любой булевой функции

от

аргументов:

Перейти

Глубина формулы $\forall x:A$ :

Перейти

Глубина формулы $\neg A$ равна:

Перейти

Глубина формулы $A \vee B$ равна:

Перейти

Глубина формулы $\exists x:A$ :

Перейти

Сложность большинства булевой

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

их схем:

Перейти

Вычитание двух

-разрядных двоичных чисел по модулю 2^n

2^n

выполнима схема:

Перейти

Сложность любой булевой

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

их схем:

Перейти

Количество всех различных

-местных схем размера

оценивается:

Перейти