СИНТЕЗ НАДЕЖНЫХ НЕВЕТВЯЩИХСЯ ПРОГРАММ
С УСЛОВНОЙ ОСТАНОВКОЙ В ПОЛНОМ КОНЕЧНОМ
БАЗИСЕ, СОДЕРЖАЩЕМ x1 & x2
Аннотация. <...> Рассматривается реализация булевых функций неветвящимися
программами с условной остановкой в полном конечном базисе B , содержащем конъюнкцию x1 & x2 . <...> Предполагается, что функциональные операторы
с вероятностью подвержены инверсным неисправностям на выходах. <...> Решается задача синтеза надежных неветвящихся программ в двух случаях: 1) оператор условной остановки абсолютно надежен; 2) оператор условной остановки ненадежен. <...> The problem of synthesis of nobranching programs with conditional stopoperator is considered in full finite basis, contained x1 & x2 . <...> This problem is solved for two
cases: 1) conditional stop-operator is absolutely reliable; 2) conditional stopoperator is unreliable. <...> Рассматривается реализация булевых функций неветвящимися программами с условной остановкой [1] в базисе B , содержащем конъюнкцию
x1 & x2 . <...> Программы с условной остановкой характеризуются наличием
управляющей команды – команды условной остановки, дающей возможность
досрочного прекращения работы при выполнении определенного условия. <...> Переменные из множества Y назовем внутренними, переменные из множества Z – выходными переменными. <...> Переменную a
назовем выходом вычислительной команды, переменные b1 , ..., bd – входами
этой команды. <...> Командой остановки p назовем выражение
p : Stop a . <...> Переменную a назовем входом команды остановки p. <...> Последовательность Pr p1 pi pl , состоящая из вычислительных
команд и команд остановки, называется неветвящейся программой с условной
остановкой, если при любом j 1, 2, , L каждый вход команды p j есть
43
Известия высших учебных заведений. <...> Поволжский регион
либо независимая переменная, либо выход некоторой вычислительной команды pi , где i j . <...> Неветвящаяся программа работает в дискретные моменты времени
t = 0, 1, 2, …, не изменяет значения независимых переменных и изменяет значения внутренних и выходных переменных. <...> Значением команды pt программы Pr на наборе независимых переменных x ( x1 , , xn ) назовем <...>