М. А. Алехина, С. М. Грабовская
НИЖНЯЯ ОЦЕНКА НЕНАДЕЖНОСТИ НЕВЕТВЯЩИХСЯ
ПРОГРАММ С ОПЕРАТОРОМ УСЛОВНОЙ ОСТАНОВКИ
Аннотация. <...> Рассматривается реализация булевых функций неветвящимися
программами с оператором условной остановки. <...> Предполагается, что функциональные операторы с вероятностью ε (ε ∈ (0, 1/ 2)) подвержены инверсным
неисправностям на выходах, а операторы условной остановки абсолютно
надежны. <...> Доказано, что любую функцию f ∈ K (класс K найден явно) нельзя
реализовать неприводимой неветвящейся программой с ненадежностью
меньше ε(1 – ε)m , где m – число функциональных операторов в программе. <...> Из
этого и ранее полученного результата о верхней оценке ненадежности неветвящихся программ следует, что почти все функции можно реализовать асимптотически оптимальными по надежности неветвящимися программами, функционирующими с ненадежностью, асимтотически равной ε при ε→0. <...> The article considers a problem of synthesis of nobranching programs with
conditional stop-operator. <...> Any boolean function f ∈ K (class K is found explicitly) is
proved to be impossible to realize by irreducible nobranching program with unreliability of less than ε(1 – ε)m, where m – the number of functional operators in the
program. <...> These and the previous results on the upper bound for the unreliability of
the nobranching programs prove that almost all functions can be realized by asymptotically optimal reliable nobranching programs that operate with unreliability asymptotically equal to ε at ε → 0. <...> Неветвящиеся программы
с оператором условной остановки характеризуются наличием управляющей
команды, дающей возможность досрочного прекращения работы программы
при выполнении определенного условия [1]. <...> Переменную a
назовем выходом вычислительной команды, переменные b1 , ..., bd – входами
этой команды. <...> Переменную a назовем входом команды остановки p. <...> Последовательность Pr = p1…pi…pL, состоящая из вычислительных команд и команд остановки, называется неветвящейся программой с условной
остановкой, если при любом j ∈ {1, …, L} каждый вход команды pj есть либо
независимая переменная, либо выход некоторой вычислительной команды <...>