Синтез асимптотически оптимальных по надежности неветвящихся программ в базисе {x[1]vx[2], x[1]&x[2], x{-}[1], stop} (90,00 руб.)

, С. М. Зиновьева СИНТЕЗ АСИМПТОТИЧЕСКИ ОПТИМАЛЬНЫХ ПО НАДЕЖНОСТИ НЕВЕТВЯЩИХСЯ ПРОГРАММ В БАЗИСЕ {x1x2, x1x2, x1 , stop}1 Аннотация. <...> Рассматривается задача синтеза асимптотически оптимальных по надежности неветвящихся программ с условной остановкой, реализующих булевы функции, при инверсных неисправностях на выходах операторов в базисе {x1x2, x1x2, 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 {x1x2, x1x2, 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 <...>