Асимптотически оптимальные по надежности неветвящиеся программы с оператором условной остановки

Одной из важнейших задач математической кибернетики является задача синтеза надежных программ (схем) из ненадежных операторов (элементов).

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

Разработка специальных методов синтеза как для схем из ненадежных функциональных элементов, так и для неветвящихся программ с оператором условной остановки связана главным образом с выбранной математической моделью неисправностей. Одна из основных моделей определяется инверсными неисправностями на выходах функциональных элементов схемы и вычислительных операторов неветвящейся программы. В диссертации решается задача построения асимптотически оптимальных (асимптотически наилучших) по надежности неветвящихся программ с оператором условной остановки в предположении, что все вычислительные операторы подвержены инверсным неисправностям на выходах, а операторы условной остановки могут быть как абсолютно надежны (2- я глава), так и ненадежны, подвержены двум типам неисправностей (3-я глава). Задача решается во всех полных конечных базисах. Уделяется внимание среднему времени работы асимптотически оптимальных по надежности неветвящихся программ с оператором условной остановки.

Известно, что схемы из функциональных элементов (ФЭ) являются моделями электронных схем, а неветвящиеся программы (как с условной остановкой, так и без нее) моделируют работу вычислительных устройств.

Однако, несмотря на эти различия, результаты о надежности и сложности, полученные для схем из функциональных элементов переносятся на неветвящиеся программы без стоп-операторов и наоборот.

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

Впервые задачу синтеза надежных схем из ненадежных функциональных элементов рассматривал Дж. фон Нейман [3]. Он предполагал, что элементы схемы подвержены инверсным неисправностям на выходах, когда функциональный элемент с приписанной ему булевой функцией </? в неисправном состоянии, в которое переходит независимо от других элементов схемы с вероятностью? (е € (0,½)), реализует функцию (р. С помощью итерационного метода Дж. фон Нейман установил, что произвольную булеву функцию можно реализовать схемой, вероятность ошибки на выходе которой при любом входном наборе значений переменных не превосходит се при любом в € (0,1/6] (с — некоторая положительная константа) .

Для повышения надежности схем Дж. фон Нейман использовал схему, реализующую функцию голосования (медиану) т (х, х2, хз) = V ххз VХ2Х?, и многократное дублирование исходных схем, что, естественно, приводило к увеличению сложности схем (примерно в раз, где к — число итераций). Поэтому именно сложности уделялось главное внимание в дальнейших исследованиях, среди которых отметим результаты С. И. Ор-тюкова [4], Д. Улига [5], С. В. Яблонского [6]. Чтобы сформулировать эти результаты, введем необходимые понятия и определения.

Полное (в Р2) конечное множество В = {еь ., ет} {т е N) называется полным конечным базисом в Р2.

Рассматривается реализация булевых функций схемами из ненадежных функциональных элементов [7], подверженных инверсным неисправностям на выходах, в полном конечном базисе В = {ei, ., ет}, т е N. (Множество всех функциональных элементов Ei, функции которых е^ принадлежат базису В, будем также называть базисом В [8].).

Каждому элементу базиса Еi приписано положительное число v (Ei) — вес данного элемента. Сложность L (S) схемы S, реализующей булеву функцию /(х) (х = (xi, ., хп)), определяется как сумма весов всех входящих в нее элементов. Предполагается, что все элементы схемы независимо друг от друга с вероятностью е переходят в неисправные состояния. Пусть а) — вероятность появления значения /(а) на выходе схемы.

S при входном наборе, а = (а, ., ап). Ненадежностью Ns (S) схемы S называется Ne (S) = maxPy^y (5, а), где максимум берется по всем возможным входным наборам, а схемы S. Надежность схемы S равна 1 — N?(S). Вводится функция Шеннона LPj?(n) — maxminL (5), характеризующая сложность схем, реализующих функции от п переменных в базисе В, где минимум берется по всем схемам S из ненадежных элементов, реализующим функцию / с ненадежностью Ne (S) ^ р, а максимум — по всем булевым функциям / от п переменных.

Пусть Ne (f) = infNs (S), где инфимум берется по всем схемам S S из ненадежных элементов, реализующим функцию /. Схема S из ненадежных элементов, реализующая функцию /, называется асимптотически оптимальной (асимптотически наилучшей) по надежности, если Ne (S) ~ N?(f) при? —" 0, т. е. lim = 1.

Приведенным весом называется число р = min (v (El)/(n (Ei) — 1)),.

Ei где минимум берется по всем элементам Ei базиса, для которых n (Ei) > 1, n (Ei) — число существенных переменных функции е^, реализуемой элементом Ei, a v (Ei) — вес функционального элемента Ei (i = 1, ., т).

О. Б. Лупанов [9] показал, что для схем, реализующих булевы функции от п переменных и состоящих из абсолютно надежных элементов (т.е. при е = 0 и р = 0), выполняется соотношение L0, о ~ р • 2п/п.

С. И. Ортюков [4] для инверсных неисправностей на выходах элементов получил следующий результат: пусть 0 <? < ?q, р > q (?)Lg, где Lg.

— минимальное число надежных элементов, необходимое для реализации функции голосования д (х 1, х<1, = ХХ2 V ХХз V х2х% в рассматриваемом базисец{е) — некоторая функция, такая, что ц{е) = е + Зе2 + о (г2) при? —>• 0. Тогда существует такая функция р (е) —р при? -" 0, что Ьр,?(п)<�р (?)-2п/п.

Д. Улиг [5] для инверсных неисправностей на выходах элементов с вероятностью ошибки? доказал, что для любых сколь угодно малых чисел г и К (т, Н > 0) существует такое число е' (г' Е (0,½)), что при любом г (е Е (0, г']) и любом р, удовлетворяющем условию р ^ (1 + К) еЬ9 (точнее р ^ ц (е)Ьд), справедливо соотношение Ьр^?(п) < (1 + т) р2п/п.

Таким образом, в результатах С. И. Ортюкова и Д. Улига асимптотика функции Шеннона сохраняется с точностью до множителя, сколь угодно близкого к единице (при этом вероятность сбоя? ограничена константой), т. е. найденные ими методы синтеза позволяют строить асимптотически оптимальные по сложности схемы, функционирующие с некоторым уровнем надежности.

С. В. Яблонский [6] рассматривал задачу синтеза надежных схем в базисе В = {хкх2,х V х% х, д (х, ?3)}. Он предполагал, что элемент, реализующий функцию голосования д (х, Х2<�Хз) — ХХ2 V хХз V х2х$, абсолютно надежный, а конъюнктор, дизъюнктор и инвертор — ненадежные, подвержены произвольным неисправностям, ненадежность каждого из них не больше е. С. В. Яблонский доказал, что для любого р > 0 существует алгоритм, который для любого п для каждой булевой функции /(х1,х2,.—, хп) строит такую схему реализующую /, что Ntг (5) ^ р, т < 2п-'/п.

Полный базис В называется неприводимым полным базисом (в Р2), если никакое его собственное подмножество полным не является.

Обозначим через В^ множество всех булевых функций, зависящих от переменных Х, Х2, ., х^ (к ^ 2).

Задачу синтеза асимптотически оптимальных по надежности схем из ненадежных элементов решали М. А. Алехина [10], В. В. Чугунова [И], А. В. Васин [12].

М. А. Алехина [10] рассматривала константные неисправности только на входах или только на выходах функциональных элементов и доказала, что во всех неприводимых полных базисах В С В2 (исключая три случая) почти все булевы функции можно реализовать асимптотически наилучшими по надежности схемами 5, функционирующими с ненадежностью, асимптотически равной N?(S) ~ се1 при е —> 0, константы с и i зависят от базиса и типа неисправностей, с? {1, 2, 3}, t? {1, 2}. Для почти всех функций сложность таких схем S удовлетворяет соотношению L (S) < кв ¦ 2п/п, причем мультипликативная константа кв зависит только от базиса В, 40 ^ кв ^ 168.

Важный результат о верхней оценке ненадежности схем при инверсных неисправностях на выходах элементов получил С. И. Аксенов [13]. Он доказал, что в произвольном полном конечном базисе любую булеву функцию / можно реализовать такой схемой S, что при всех? ? (0, ?i] верно неравенство.

N?(S) ^ + се2. (1) причем £Х = 1/3600, а = 10 584.

Позднее М. А. Алехиной и А. В. Васину [14] удалось ослабить ограничение на ?, а константу с уменьшить: е = 1/960, с = 182.

А. В. Васин [12] решил задачу синтеза асимптотически оптимальных по надежности схем во всех полных базисах В С Б3 при инверсных неисправностях на выходах элементов. Он доказал, что почти все булевы функции можно реализовать асимптотически оптимальными по надежности схемами из функциональных элементов с ненадежностью, асимптотически равной кв ¦? при? —У 0. Константа кв зависит от базиса В, и кв? {1, 2, 3, 4, 5}. Для почти всех функций сложность таких схем асимптотически не больше чем в три раза превышает сложность минимальных схем, построенных из абсолютно надежных элементов.

В частности, из результатов А. В. Васина [12] следует, что для некоторых базисов, например В = {ХХ2, нельзя понизить мультипликативную константу 5 в оценке ненадежности (1).

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

Сложностью С (Рг) неветвящейся программы Рг назовем число команд этой программы.

Временем работы Т (Рг, а) неветвящейся программы Рг на входном наборе, а назовем число команд программы, выполненных до остановки.

Если на входном наборе, а ни один из операторов условной остановки не сработал (т.е. входы всех стоп-операторов равны нулю), то Т (Рг, а) = С{Рг).

Величину Т (Рг) = (%2Т (Рг, а))/2п, где суммирование производится по всем двоичным наборам, а длины п, назовем средним временем работы программы Рг.

Очевидно, что для любой неветвящейся программы Рг верно неравенство Т (Рг) ^ С{Рг). В частности, если неветвящаяся программа 5 не содержит операторов условной остановки, то ее сложность равна среднему времени ее работы, т. е. С (Б) = Т (5).

Величину Т (/) = ттГ (Рг), где минимум берется по всем неветвя-щимся программам, вычисляющим /, назовем средним временем вычисле-лил (средней сложностью) функции /.

Программу Рг, вычисляющую функцию /, назовем минимальной программой, если для нее справедливо равенство Т (Рг) = Т (/).

А. В. Чашкин [2] доказал: в полном базисе В С В^ (к ^ 3), содержащем функцию, существенно зависящую от к переменных, для почти всех функций /, зависящих от п переменных, среднее время вычисления.

2?г-1 —г,-г при п ооа если полный базис В С В2) то для любой п (к — 1) булевой функции /, зависящей от п переменных, среднее время вычисле.

2 п ния Т (/) < 2п~1/п, и для почти всех функций от п переменных Г (/) > — о’ТЬ при п —> оо.

Сравним среднее время работы неветвящихся программ с оператором условной остановки [2] и схем [9] в случае, когда все операторы программ и все функциональные элементы схем абсолютно надежны. Поскольку все операторы программы имеют вес, равный единице, будем считать, что вес функционального элемента также равен единице. Тогда для полного базиса В С Вк (к ^ 2), содержащего функцию, существенно зависящую от к переменных, приведенный вес р = Следовательно, при к > 3 среднее время работы (сложность) минимальных схем для почти всех функций в два раза больше, чем среднее время работы неветвящихся программ с оператором условной остановки. Если к — 2, то для почти всех функций отношение среднего времени работы (сложности) минимальных схем к среднему времени работы неветвящихся программ с оператором условной остановки не больше 3.

В диссертационной работе исследуются неветвящиеся программы с оператором условной остановки, в которых вычислительные операторы подвержены инверсным неисправностям на выходах, а для стоп-операторов рассмотрены два случая: 1) операторы условной остановки абсолютно надежны- 2) операторы условной остановки ненадежны, подвержены неисправностям первого и второго рода. В каждом из двух случаев решена задача синтеза асимптотически оптимальных по надежности неветвящихся программ с оператором условной остановки в произвольном полном конечном базисе. Уделено внимание среднему времени вычисления таких программ.

Во второй главе будем считать, что все операторы условной остановки абсолютно надежны. А значит, каждый из них срабатывает (и следовательно, прекращает работу программы) при поступлении на его вход единицы. При этом на выходе программы появляется значение выходной переменной г, вычисленное последним до остановки.

В третьей главе будем считать, что операторы условной остановки подвержены двум типам неисправностей (первого и второго рода) и переходят в неисправные состояния независимо друг от друга. Неисправность первого рода характеризуется тем, что при поступлении единицы на вход стоп-оператора он с вероятностью 5 (5 Е (0, ½)) не срабатывает, и, следовательно, работа программы продолжается. Неисправность второго рода такова, что при поступлении нуля на вход стоп-оператора он с вероятностью г] (?7 Е (0, ½)) срабатывает, и, следовательно, работа программы прекращается. Обозначим р = тах{£, 6, г]}.

Ненадежностью N?{Pr) программы Рг назовем максимальную вероятность ошибки на выходе программы Рг при всевозможных входных наборах. Надежность программы Рг равна 1 — N^(Pr). Обозначим N?(f) = inf N?(Pr), где инфимум берется по всем программам Рг, реализующим булеву функцию /. Программа Рг, реализующая функцию /, называется асимптотически оптимальной по надежности, если N^{Pr) ~ Nfl (f) при? 0, т. е. lim р^г = 1.

В частности, в обозначениях Л^ДРг) и N?(f) вместо символа ?1 будем использовать символ если 1) в неветвящейся программе все операторы условной остановки абсолютно надежны (т.е. o = 0, г) = 0) — 2) если? — е- 3) если неветвящаяся программа не содержит операторов условной остановки.

Обозначим через Subst (h) множество всех функций, зависящих от п переменных Х, Х2, ¦¦¦¦, хп (n ^ 3) и полученных из функции h всевозможными подстановками переменных (т.е. заменой и/или отождествлением переменных).

Обозначим Ао (п) = {хь ., хп], Ar (n) = Subst (fr (xi,. х2г+))-, гДе fr (xi,., X2r+l) = ХХ2 v ?1X3X4 V X1X3X5XQ V. V XiX3. X2r-3X2r-lX2r V xiXz. X2r-zX2r-iX2r+i (r > 1,^г e {хь ., xn} при всех г G N).

Обозначим A{n) = |^J, 4fc (n). k=0.

Пусть К. (ri) — множество всех неконстантных булевых функций, зависящих от переменных xi, • • •, хп (п ^ 3), не принадлежащих множеству оо.

Л (п). Обозначим К = |^jK (n). п=3.

Замечание. Мощность множества Л (п) удовлетворяет неравенству.

А (п) ^п2п;

Поэтому —0 при n 00. Следовательно, -рт^ —> 1, а множество К содержит почти все булевы функции.

Основные результаты работы в самом общем виде можно сформулировать в виде теорем 1, 2 (для случая абсолютно надежных стоп-операторов) и теорем 3, 4 (для случая ненадежных стоп-операторов).

Теорема 1. В любом полном конечном базисе для любой булевой функции f существует такая неветвящаяся программа Рг/ с абсолютно надежными операторами условной остановки, реализующая /, для которой.

ЛГДРг/) < е + 4е2. и для любой булевой функции / Е К.

Щ/) > г — с² при всех? Е (0,1/960], где с — некоторая положительная константа.

Теорема 2. Для произвольного полного конечного базиса В, любого действительного числа т > 0 существует константа е Е (0,½), такая, что при любом п ^ 3 всякую булеву функцию /' Е К (п) можно реализовать программой Рг{ с абсолютно надежными операторами условной остановки, для которой при всех е Е (0, ?1] и.

Т (Рг-)<3(1+т)р2п/п при п —У оо, где — некоторая положительная константа.

Из теорем 1 и 2 следует, что в произвольном полном конечном базисе любую булеву функцию / Е К можно реализовать асимптотически оптимальной по надежности неветвящейся программойРг/, ненадежность которой Л^(Рг/) ~ е при е —У 0. Среднее время работы таких программ для почти всех функций асимптотически не больше чем в 9(1 +т) раз превышает среднее время работы минимальных программ, построенных из абсолютно надежных операторов (т — любое сколь угодно малое положительное число).

В теоремах 3 и 4 будем считать, что операторы условной остановки ненадежны, подвержены неисправностям первого и второго рода.

Теорема 3. В любом полном конечном базисе для любой булевой функции f существует такая неветвящаяся программа Ptf с ненадежными операторами условной остановки, реализующая f, для которой при всех? е (0,1/960] и? = e.

N?(Prf)^?+ 17е2, и для любой булевой функции f Е К.

N?(f) ^ е — с3г2, где сз — некоторая положительная константа.

Теорема 4. Для произвольного полного конечного базиса В, любого действительного числа г > 0 существует константа ?2 Е (0,½), такая, что при любом п ^ 3 всякую булеву функцию f Е К (п) можно реализовать программой Prj с ненадежными операторами условной остановки, для которой при всех? Е (0, ?2] и? = ?

N?{Prf) — N?(f) ^ c4?2 и.

T (Prf)<3(l+r)p2n/n при п —> оо (?4 — некоторая положительная константа).

Из теорем 3 и 4 следует, что в произвольном полном конечном базисе любую булеву функцию / Е К можно реализовать асимптотически оптимальной по надежности неветвящейся программой Prj с ненадежным оператором условной остановки, ненадежность которой N?(Prf) ~ е, если р, =? и г —> 0. Среднее время работы таких программ для почти всех функций асимптотически не больше чем в 9(1 + г) раз превышает среднее время работы минимальных программ, построенных из абсолютно надежных операторов (г — любое сколь угодно малое положительное число).

Диссертация состоит из введения, трех глав, заключения, приложения и списка литературы, содержащего 28 наименований. Общий объем работы — 89 страниц.

Заключение

.

В диссертации исследована ненадежность неветвящихся программ с оператором условной остановки в произвольном полном конечном базисе. Предполагалось, что вычислительные операторы программ ненадежны, подвержены инверсным неисправностям на выходах, переходят в неисправные состояния независимо друг от друга с вероятностью е (е? (0,½)). Для операторов условной остановки рассмотрены два случая: 1) стоп-операторы абсолютно надежны, 2) стоп-операторы ненадежны, подвержены неисправностям 1-го рода (с вероятностью 5 (6? (0,½))) и 2-го рода (с вероятностью Г) (т)? (0,½))), переходят в неисправные состояния независимо друг от друга.

В первом случае (2-ая глава) доказано, что в произвольном полном конечном базисе все булевы функции можно реализовать неветвящи-мися программами с абсолютно надежным оператором условной остановки, которые функционируют с надежностью асимптотически (е 0) не больше чем е, и существуют функции /? К, которые нельзя реализовать неветвящимися программами с оператором условной остановки, которые функционируют с надежностью асимптотически (е —" 0) меньше чем г. Класс К содержит почти все булевы функции. Таким образом, получаем следующий результат: в произвольном полном конечном базисе почти все булевы функции можно реализовать асимптотически оптимальными по надежности неветвящимися программами с оператором условной остановки, которые функционируют с ненадежностью, асимптотически равной? при? -> 0.

Этот результат принципиально отличается от аналогичного результата для неветвящихся программ (без стоп-оператора). Проведем сравнение с известными результатами для полных базисов В С (поскольку в других полных конечных базисах задача построения асимптотически оптимальных по надежности неветвящихся программ пока не решена).

Из результатов А. В. Васина [12] следует, что в полном базисе В С В3 при инверсных неисправностях на выходах вычислительных операторов почти все функции можно реализовать асимптотически оптимальными по надежности неветвящимися программами (без стоп-операторов), функционирующими с ненадежностью, асимптотически равной к в •? при? —> 0. Константа кв зависит от базиса В и кв Е {1, 2, 3, 4, 5}. Например, если полный базис В содержит функцию хх2 0×3) то кв = 1- если В — {хх2,х (х2 /хз), 1}, то кв = 2- если В = {ХХ2,Х V Х2, х], то кв = 3- если В = {ХХ2, х\, то кв = 4- если В = {хх2, Х}, то кв — 5.

Тогда как для неветвящихся программ с оператором условной остановки в произвольном полном базисе В константа к в = 1.

Отметим также, что с точки зрения сложности вычислений (но не средней сложности!) результат для асимптотически оптимальных по надежности неветвящихся программ с оператором условной остановки такой же, как для асимптотически оптимальных по надежности неветвящихся программ (без стоп-оператора), а именно сложность названных программ отличается от сложности неветвящихся программ (как с оператором условной остановки, так и без него), построенных из абсолютно надежных операторов, асимптотически не больше чем в три раза.

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

Во втором случае (3-я глава) доказано, что в произвольном полном конечном базисе все булевы функции можно реализовать неветвящимися программами с ненадежным оператором условной остановки, которые функционируют с надежностью, асимптотически (¡-л —V 0, ¡-л = тах{г, 6, г]}) не больше чем тах{б, 77}, и существуют функции / Е К, которые нельзя реализовать неветвящимися программами с оператором условной остановки, которые функционируют с надежностью асимптотически (¡-л —> 0) меньше чем ?. Класс К (тот же, что и во 2-ой главе) содержит почти все булевы функции.

Попытки получить нижнюю оценку вида тах{е, г)} позволили выявить свойства подпрограмм исследуемой программы, при которых ошибки ненадежных стоп-операторов не влияют на результат вычисления. Эти свойства не зависят ни от базиса, ни от функции, которую вычисляет программа, определяются лишь структурой самой программы. А значит, в самом общем случае для произвольной программы, реализующей функцию /? К, невозможно оценить ее ненадежность снизу выражением вида г] • (р (е, 6, 77) или 6 ¦ ф (е, д, г}) 5, ту), ф (е, 77) — некоторые функции, зависящие от е, <5, г]). Этот факт указывает на то, что именно ошибки вычислительных операторов наиболее существенно влияют на оценку ненадежности неветвящихся программ с оператором условной остановки.

Если же /л — е, то верхняя и нижняя оценки ненадежности программ асимптотически {¡-л 0) равны е. В этом случае получаем следующий результат: в произвольном полном конечном базисе почти все булевы функции можно реализовать асимптотически оптимальными по надежности неветвящимися программами с оператором условной, которые функционируют с ненадежностью, асимптотически равной? при е —>• 0.

Среднее время вычисления таких программ для почти всех функций | по порядку равно среднему времени вычисления минимальных неветвящихся программ с оператором условной остановки, построенных из I абсолютно надежных операторов. 5 1 I.

1 [.

I |.

4 |.