Нижняя оценка ненадежности неветвящихся программ с оператором условной остановки

булевы функции неветвящиеся программы оператор условной остановки

Оптические свойства квантовой проволоки с одномерной сверхрешеткой из потенциалов нулевого радиуса во внешнем электрическом поле, Метод интегральных уравнений для решения задачи Дирихле в возмущенном трехмерном слое, ...

М. А. Алехина, С. М. Грабовская НИЖНЯЯ ОЦЕНКА НЕНАДЕЖНОСТИ НЕВЕТВЯЩИХСЯ ПРОГРАММ С ОПЕРАТОРОМ УСЛОВНОЙ ОСТАНОВКИ Аннотация. <...> Рассматривается реализация булевых функций неветвящимися программами с оператором условной остановки. <...> Предполагается, что функциональные операторы с вероятностью ((0, 1/ 2)) εε подвержены инверсным неисправностям на выходах, а операторы условной остановки абсолютно надежны. <...> Доказано, что любую функцию f K (класс K найден явно) нельзя реализовать неприводимой неветвящейся программой с ненадежностью меньше ε(1 – ε)m , где m – число функциональных операторов в программе. <...> Из этого и ранее полученного результата о верхней оценке ненадежности неветвящихся программ следует, что почти все функции можно реализовать асимптотически оптимальными по надежности неветвящимися программами, функционирующими с ненадежностью, асимтотически равной ε при ε0. <...> Переменную a назовем выходом вычислительной команды, переменные 1, ..., dbb – входами этой команды. <...> Последовательность Pr = p1…pi…pL, состоящая из вычислительных команд и команд остановки, называется неветвящейся программой с условной остановкой, если при любом j {1, …, L} каждый вход команды pj есть либо независимая переменная, либо выход некоторой вычислительной команды. <...> Неветвящаяся программа работает в дискретные моменты времени t = 0, 1, 2, …, не изменяет значения независимых переменных и изменяет pttrp – все команды остановки из Pr, причем t1 <…< tr, т.е. s p ), а через qj – аргумент команды остаj t j значения внутренних переменных yi (I {1, …, n}) и значение выходной переменной <...> Тогда через sj будем обозначать j-ю команду остановки программы Pr (т.е. новки sj. <...> Всюду далее будем считать, что операторы условной остановки абсолютно надежны (и, значит, срабатывают, если на вход поступает единица), а все вычислительные операторы базиса B независимо друг от друга с вероятностью ε (ε (0, 1/2)) подвержены инверсным неисправностям на выходах. <...> Ненадежностью N(Pr) программы <...>

• Похожие документы из РУАЭСТ
• |
• Похожие документы из Руконт