Аннотация:
Рассматривается реализация булевых функций схемами из ненадежных
функциональных элементов в полном конечном базисе, содержащем особенную функцию.
Предполагается, что все элементы схемы независимо друг от друга с вероятностью
$\varepsilon \in (0,1/2)$ подвержены неисправностям типа 0 на выходах. Показано, что
почти любую булеву функцию можно реализовать асимптотически оптимальной по
надежности схемой, функционирующей с ненадежностью, асимптотически равной
$\varepsilon$ при $\varepsilon \to 0$.
|
