Том 21, номер 1, 2014 г., Стр. 30–43

УДК 519.718
С. М. Грабовская
О верхней оценке ненадёжности неветвящихся программ при однотипных константных неисправностях на выходах вычислительных операторов

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

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

Грабовская Светлана Михайловна ¹
1. Пензенский гос. университет,
ул. Красная, 40, 440026 Пенза, Россия
е-mail: swetazin@mail.ru

Статья поступила 11 февраля 2013 г.
Исправленный вариант — 15 мая 2013 г.

Литература

[1] Алехина М. А. О надёжности схем при однотипных константных неисправностях на выходах элементов // Мат. X Междунар. семинара «Дискретная математика и её приложения» (Москва, МГУ, 1–6 февраля 2010 г.). - М.: Изд-во мех.-мат. фак-та МГУ, 2010. - C. 83–85.

[2] Алехина М. А. Синтез асимптотически оптимальных по надёжности схем. - Пенза: ИИЦ ПГУ, 2006. - 156 с.

[3] Грабовская С. М. Асимптотически оптимальные по надёжности неветвящиеся программы с оператором условной остановки: Дис. . . . канд. физ.-мат. наук: 01.01.09. - Пенза, 2012. - 89 с.

[4] Редькин Н. П. О полных проверяющих тестах // Мат. вопросы кибернетики. - 1989. - Вып. 2. - С. 198–222.

[5] Чашкин А. В. О среднем времени вычисления значений булевых функций // Дискрет. анализ и исслед. операций. Сер. 1. - 1997. - Т. 4, № 1. - С. 60–78.

[6] Яблонский С. В. Асимптотически наилучший метод синтеза надёжных схем из ненадёжных элементов // Banach Center. - 1982. - N 7. - P. 11–19.