Том 19, номер 1, 2012 г., Стр. 33-40

УДК 519.718
Грабовская С. М. 
О надёжности неветвящихся программ в базисе, содержащем обобщённую конъюнкцию

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

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

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

Статья поступила 16 ноября 2010 г.
Исправленный вариант — 14 октября 2011 г.

Литература

[1] Алехина М. А., Васин А. В. О надёжности схем в базисах, содержащих функции не более чем трёх переменных // Уч. записки Казанского гос. ун-та. Сер. «Физ.-мат. науки». — Казань: Изд-во Казанск. ун-та, 2009. — Т. 151, вып. 2. — С. 25–35.

[2] Васин А. В. Асимптотически оптимальные по надёжности схемы в полных базисах из трёхвходовых элементов // Дисс. ... канд. физ.-мат. наук. — Пенза: Пензенский гос. ун-т, 2010. — 100 с.

[3] Васин А. В. Об асимптотически оптимальных схемах в базисе {$x_1 \And x_2, \overline{x}_1$} // Дискрет. анализ и исслед. операций. — 2009. — Т. 16, № 6. — С. 12–22.

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