RUS  ENG
Полная версия
ЖУРНАЛЫ // Известия высших учебных заведений. Математика // Архив

Изв. вузов. Матем., 2012, номер 2, страницы 13–22 (Mi ivm8429)

Эта публикация цитируется в 14 статьях

О надежности неветвящихся программ в произвольном полном конечном базисе

М. А. Алехина, С. М. Грабовская

Кафедра дискретной математики, Пензенский государственный университет, г. Пенза, Россия

Аннотация: Рассматривается реализация булевых функций неветвящимися программами с условной остановкой в произвольном полном конечном базисе. Предполагается, что операторы условной остановки абсолютно надежны, а все вычислительные операторы базиса независимо друг от друга с вероятностью $\varepsilon$ из интервала (0,1/2) подвержены инверсным неисправностям на выходах. Доказано, что любую булеву функцию можно реализовать программой с ненадежностью $\varepsilon+81\varepsilon^2$ при всех $\varepsilon\in(0,1/960]$.

Ключевые слова: булевы функции, неветвящиеся программы, оператор условной остановки, синтез, надежность.

УДК: 519.718

Поступила: 02.02.2011


 Англоязычная версия: Russian Mathematics (Izvestiya VUZ. Matematika), 2012, 56:2, 10–18

Реферативные базы данных:


© МИАН, 2024