, С. М. Зиновьева
СИНТЕЗ АСИМПТОТИЧЕСКИ ОПТИМАЛЬНЫХ
ПО НАДЕЖНОСТИ НЕВЕТВЯЩИХСЯ ПРОГРАММ
В БАЗИСЕ {x1x2, x1x2, x1 , stop}1
Аннотация. <...> Рассматривается задача синтеза асимптотически оптимальных по
надежности неветвящихся программ с условной остановкой, реализующих булевы функции, при инверсных неисправностях на выходах операторов в базисе {x1x2, x1x2, x1 , stop}. <...> Доказано, что в рассматриваемом базисе все булевы
функции f(x1, x2,…, xn) можно реализовать асимптотически оптимальными по
надежности программами с условной остановкой, причем для функций xi
(i {1, 2, …, n}) эти программы являются абсолютно надежными (не содержат
операторов), а для остальных функций эти программы функционируют с ненадежностью, асимптотически равной ε при ε → 0 (ε – вероятность инверсной
неисправности на выходе оператора). <...> We consider the problem of synthesis of optimal on reliability nobranching programs with conditional stop-operator at inverse faults on operator outputs in basis {x1x2, x1x2, x1 , stop}. <...> We proved that in this basis it’s possible to
realize all Boolean functions with asymptotically optimal on reliability programs
with conditional stop-operator, and for functions xi (i {1,2,…,n}) these programs
are absolutely reliable (contain no operators), and for remaining functions these
programs work with unreliability asymptotically equal ε at ε → 0 (ε is a probability
of the inverse fault on the operator output). <...> Предполагается, что все операторы –
конъюнкторы, дизъюнкторы, инверторы и операторы условной остановки –
независимо друг от друга с вероятностью ε (ε (0; 1/2)) подвержены инверсным неисправностям на выходах. <...> Эти неисправности характеризуются тем,
что в исправном состоянии вычислительный оператор реализует приписанную ему булеву функцию φ, а в неисправном – функцию . <...> В неисправном
состоянии оператор условной остановки вместо единицы выдает нуль. <...> Считаем, что программа Pr реализует функцию f(x1, x2, …, xn), если она реализует
ее при отсутствии неисправностей. <...> Ненадежностью N(Pr) программы Pr <...>