Математика/4. Прикладная математика

Д. ф.-м.н., проф. Алехина М.А., аспирант Грабовская С.М.

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

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

Рассмотрим реализацию булевых функций неветвящимися программами с оператором условной остановки в произвольном полном конечном базисе. Неветвящаяся программа с оператором условной остановки [1] – это последовательность вычислительных команд и команд остановки. Команда условной остановки, которая дает возможность досрочного прекращения работы программы при поступлении на вход стоп-оператора единицы.

Считаем, что все функциональные операторы программы подвержены инверсным неисправностям на выходах операторов и переходят в неисправные состояния независимо друг от друга с вероятностью eÎ(0; ½), а оператор условной остановки подвержен двум типам неисправностей: первого и второго рода. Инверсные неисправности на выходах вычислительных операторов характеризуются тем, что в исправном состоянии вычислительный оператор реализует приписанную ему булеву функцию j, а в неисправном – функцию . Неисправность стоп-оператора первого рода характеризуется тем, что при поступлении единицы на вход стоп-оператора он с вероятностью d (dÎ(0; ½)) не срабатывает, и, следовательно, работа программы продолжается. Неисправность второго рода такова, что при поступлении нуля на вход стоп-оператора он с вероятностью h (hÎ(0; ½))  срабатывает,  и, следовательно, работа программы прекращается. Обозначим  m=max{ε, d, h}.

Ненадежностью Nm(Pr) программы Pr назовем максимальную вероятность ошибки на выходе программы Pr при всевозможных входных наборах.

ТЕОРЕМА 1. Допустим, что в полном конечном базисе B любую булеву функцию f можно реализовать неветвящейся программой Rf с ненадежностью Nm(Rf) ≤ N. Пусть g(x1, x2, x3) –  некоторая функция вида xxÚxxÚxx (σiÎ{0, 1}, iÎ{1,2,3}), Prg – любая программа, реализующая функцию g(x1, x2, x3) в базисе В, а Nm(Prg) – ненадежность программы Prg. Тогда любую булеву функцию f в базисе В можно  реализовать программой  Prf,  ненадежность  которой  при  всех  εÎ(0;1/960]  удовлетворяет неравенству

Nm(Prf)≤max{v1, v0}+3N× Nm(Prg)+3N2,                                                  (1)

где v1 и v0 – вероятности ошибок  программы Prg на наборах (1, 2, 3) и
(σ1, σ2, σ3) соответственно.

Доказательство. Пусть В –  произвольный  полный  конечный базис,  g(x1, x2, x3) = xxÚxxÚxx (σiÎ{0, 1}, iÎ{1,2,3}), Prg – любая программа, реализующая функцию g(x1, x2, x3) в базисе В, а Nm(Prg) – ненадежность программы Prg. По условию любую булеву функцию f можно реализовать неветвящейся программой Rf  с ненадежностью Nm(Rf) ≤ N. Следовательно, функцию  также можно реализовать неветвящейся программой Rf' с ненадежностью Nm(Rf') ≤ N. Реализуем функции  (iÎ{1,2,3}, σi – показатель степени переменной xi функции g) соответственно программами Ri, причем Nm(Ri) ≤ N. Используя по одному экземпляру программ R1, R2 и R3 и программу Prg(x1, x2, x3), построим для функции  f  неветвящуюся программу Prf:

y1= [R1]

y2= [R2]

y3= [R3]

Prg(y1, y2, y3)

Пусть набор а такой, что f(a)=0. На наборе а оценим вероятность ошибки P(Prf, a) программы Prf, т.е. вероятность появления единицы на выходе Prf:

P(Prf, a)≤(1-P1)(1-P2)(1-P3)v1+

+[P1(1-P2)(1-P3)+(1-P1)P2(1-P3)+(1-P1)(1-P2)P3] Nm(Prg)+

+[P1P2(1-P3)+(1-P1)P2P3+P1(1-P2)P3]+P1P2P3≤ v1+3N× Nm(Prg)+3N2,

где Pi – вероятность появления ошибки на выходе программы Ri на наборе а.

Аналогично получается оценка для вероятности ошибки P(Prf, a) программы Prf  в случае, когда набор а – единичный для функции  f,  т.е.  f(a)=1:

P(Prf, a)≤(1-P1)(1-P2)(1-P3)v0+

+[P1(1-P2)(1-P3)+(1-P1)P2(1-P3)+(1-P1)(1-P2)P3] Nm(Prg)+

+[P1P2(1-P3)+(1-P1)P2P3+P1(1-P2)P3]+P1P2P3≤ v0+3N× Nm(Prg)+3N2,

где Pi – вероятность появления ошибки на выходе программы Ri на наборе а.

Поскольку ненадежность программы Nm(Prf) равна максимальной вероятности ошибки, получаем утверждение теоремы. 

Ранее [2] были доказаны лемма 1 и теорема 2.

ЛЕММА 1. [2] В произвольном полном конечном базисе функцию
g(x1, x2, x3)=xxÚxxÚxx можно реализовать такой неветвящейся программой Prg, что справедливы неравенства max{v1, v0}≤ max{ε, h}+m2 и Nm(Prg)≤4m, где v1 и v0 – вероятности ошибок  программы Prg на наборах
(1, 2, 3) и (σ1, σ2, σ3) соответственно, а m=max{ε, d, h}.

ТЕОРЕМА 2. [2] В полном конечном базисе любую булеву функцию f можно реализовать такой программой Prf, что при всех εÎ(0; 1/960] справедливо  неравенство    Nm(Prf) ≤ max{ε, h}+147m 2.

Результат теоремы 2 можно улучшить. Покажем, как это можно сделать в случае m=ε.

ТЕОРЕМА 3. В полном конечном базисе любую булеву функцию f можно реализовать такой программой Prf, что при всех εÎ(0; 1/960] и m=ε справедливо  неравенство    Nε(Prf) ≤ ε+17ε2.

Доказательство. Пусть B – полный конечный базис и m=ε. По лемме 1 некоторую функцию вида g(x1, x2, x3)=xxÚxxÚxx можно реализовать программой Prg, ненадежность которой Nε(Prg)≤4ε  и max{v1, v0}≤ ε+ε2.

Пусть f – любая булева функция. По теореме 2 в базисе B функцию f можно реализовать неветвящейся программой Pr, ненадежность которой при всех εÎ(0; 1/960] удовлетворяет неравенству Nε(Pr)≤ε+147ε2≤1,15ε. Воспользуемся формулой (1), полагая N=1,15ε. Тогда функцию f можно реализовать неветвящейся программой Pr, которая функционирует с ненадежностью Nε(Pr)≤ ε+ ε2+ 3∙1,15ε(1,15ε+4ε)≤ ε+18,77 ε2 ≤1,02ε.

Еще раз воспользуемся формулой (1), полагая N=1,02ε. Тогда функцию f можно реализовать неветвящейся программой Pr, ненадежность которой Nε(Pr)≤ε+ε2+3∙1,02ε(1,02ε+4ε)≤ε+16,37ε2≤ε+17ε2. 

Таким образом, в произвольном полном конечном базисе любую булеву функцию f можно реализовать неветвящейся программой, ненадежность которой не превосходит ε+17ε2  при всех εÎ(0; 1/960] и m=ε.

ЗАМЕЧАНИЕ 1. Из доказательства теоремы 3 видно, что в результате применения двух итераций удалось понизить ненадежность программы с e+147e2 до e+17e2. Возникает вопрос, насколько уменьшится ненадежность программы в результате нескольких следующих итераций?

Чтобы на него ответить, рассмотрим каждое слагаемое в правой части неравенства (1) и заметим, что на каждом шаге итерации: 1) вместо max{v1, v0} подставляем e+e2 ; 2) вместо Nm(Prg) подставляем 4e ; 3) вместо N подставляем величину больше, чем e. Поэтому в правой части неравенства (1) получается выражение больше, чем ε+ε2+3ε∙5ε=e+16e2. Следовательно, на всех следующих итерациях будем получать верхнюю оценку сверху вида e+ke2 , где k > 16, т.е. существенно улучшить результат теоремы 3 описанным методом не удастся.

Исследование выполнено при финансовой поддержке РФФИ, номер проекта 11-01-00212а.

Литература:

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

2.     Грабовская С. М. О надежности неветвящихся программ с ненадежным  оператором условной остановки в произвольном полном конечном базисе // Известия высших учебных заведений. Поволжский регион. Физико-математические науки. – Пенза: ИИЦ ПГУ, 2011 г. – № 3. – С. 52–60.