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

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

Асимптотически оптимальные по надежности неветвящиеся программы с оператором условной остановки тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

Грабовская, Светлана Михайловна АВТОР

кандидата физико-математических наук УЧЕНАЯ СТЕПЕНЬ

Пенза МЕСТО ЗАЩИТЫ

2012 ГОД ЗАЩИТЫ

01.01.09 КОД ВАК РФ

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

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

На правах рукописи

005043102

Грабовская Светлана Михайловна

АСИМПТОТИЧЕСКИ ОПТИМАЛЬНЫЕ ПО НАДЕЖНОСТИ НЕВЕТВЯЩИЕСЯ ПРОГРАММЫ С ОПЕРАТОРОМ УСЛОВНОЙ ОСТАНОВКИ

Специальность 01.01.09 — дискретная математика и математическая кибернетика

Автореферат диссертации на соискание ученой степени кандидата физико-математических наук

1 7 МАЯ 2012

Казань 2012

005043102

Работа выполнена в ФГБОУ ВПО «Пензенский государственный университет» на кафедре «Дискретная математика».

доктор физико-математических наук, профессор ФГБОУ ВПО «Пензенский государственный университет» Алехина Марина Анатольевна

доктор физико-математических наук, профессор ФГБОУ ВПО «Московский государственный университет имени М. В. Ломоносова» Вороненко Андрей Анатольевич;

кандидат физико-математических наук, доцент ФГАОУ ВПО «Казанский (Приволжский) федеральный университет» Нурмеев Наиль Нуреевич

ФГБОУ ВПО «Восточно-Сибирская государственная академия образования»

Защита состоится « // » мая 2012 г. в мин на заседании диссер-

тационного совета Д 212.081.24 при ФГАОУ ВПО «Казанский (Приволжский) федеральный университет» по адресу: 420008, г. Казань, ул. Кремлевская, д. 35, конференц-зал научной библиотеки им. Н. И. Лобачевского.

С диссертацией можно ознакомиться в научной библиотеке ФГАОУ ВПО «Казанский (Приволжский) федеральный университет».

Автореферат разослан « 26 » апреля 2012 г.

Научный руководитель:

Официальные оппоненты:

Ведущая организация:

Ученый секретарь диссертационного совета

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ Актуальность темы. Настоящая работа относится к одному из важнейших разделов математической кибернетики - теории синтеза, надежности и сложности управляющих систем. Актуальность исследований в этой области обусловлена важностью многочисленных приложений, возникающих в различных разделах науки и техники.

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

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

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

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

2 Чашкин А. В. О среднем времени вычисления булевых операторов // Дискретный анализ и исследование операций. Серия 1. - 1998. - Т. 5, № 1. - Январь-март. - С. 88-103.

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

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

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

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

Для повышения надежности схем Дж. фон Нейман использовал схему, реализующую функцию голосования (медиану) т(х 1,х2,х3) = х\%2 Узд V Х2Х3, и многократное дублирование исходных схем, что естественно приводило к увеличению сложности схем (примерно в 3* раз, где к - число итераций). Поэтому именно сложности уделялось главное внимание в дальнейших иссле-

3 Von Neuman J. Probabilistic logics and the synthesis of reliable organisms from unreliable components // Automata studies / edited by C. Shannon, Mc. Carthy J. - Princeton University Press, 1956. (Русский перевод: Автоматы. - M. : ИЛ, 1956. - С. 68-139.)

дованиях, среди которых отметим результаты С. И. Орткжова4, Д. Улига5, С. В. Яблонского6. Чтобы сформулировать эти результаты, введем необходимые понятия и определения.

Полное (в Рг) множество В = {в1, ..., ет} (то € /V) называется полным конечным базисом в

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

Каждому элементу базиса Е1 приписано положительное число —

вес данного элемента. Сложность ¿(5) схемы «5, реализующей булеву функцию /(х) (х = (аг1, ..., хп)), определяется как сумма весов всех входящих в нее элементов. Предполагается, что все элементы схемы независимо друг от друга с вероятностью е переходят в неисправные состояния. Пусть а) - вероятность появления значения /(а) на выходе схемы 5 при входном наборе а = (а^ ..., а„). Ненадежностью Я£(5) схемы 5 называется ^(5) = тахРщ(5, а), где максимум берется по всем возможным входным наборам а схемы 5. Надежность схемы 5 равна 1 — N¿(3). Вводится функция

Шеннонз ЬР:е(п) = тахтт£(5), характеризующая сложность схем, реали/ ^

зующих функции от п переменных в базисе В, где минимум берется по всем схемам 5 из ненадежных элементов, реализующим функцию / с ненадежностью ЛГе(5) < р, а максимум - по всем булевым функциям / от п переменных.

Пусть Л^(/) = тГЛ^й), где инфимум берется по всем схемам 5 из ненадежных элементов, реализующим функцию /. Схема 5 из ненадежных элементов, реализующая функцию /, называется асимптотически оптималь-

4 Ортюков С. И. Об избыточности реализации булевых функций схемами из ненадежных элементов // Труды семинара по дискретной математике и ее приложениям (г. Москва, 27-29 января 1987 г.). -М. : Изд-во Моск. ун-та, 1989. - С. 166-168.

5 Uhlig D. Reliable networks from unreliable gates with almost minimal comlexity // Fundamentals of Computation Theory. Intern, conf. FCT'87 (Kazan, June 1987). - Pioc. Berlin : Springer-Verl., 1987. -P. 462-469. (Lecture Notes in Comput. Sci.; V. 278).

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

7 Редькин Н. П. Надежность и диагностика схем. - М. : Изд-во МГУ, 1992. - 192 г..

8 Лупанов О. Б. Асимптотические оценки сложности управляющих систем. - М.: Изд-во МГУ, 1984.

ной (асимптотически наилучшей) по надежности, если N¡-(5) ~ Л^/) при е 0. т. е. Нт тгШ = 1.

Е-+0

Приведенным весом называется число р = тт(у(Е^/(п(Е{) — 1)), где минимум берется по всем элементам Е{ базиса, для которых п(Е{) > 1, п(Ег) - число существенных переменных функции реализуемой элементом Е{, а у(Е{) - вес функционального элемента Е^ { — I, ..., т.

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

С. И. Ортюков [4] для инверсных неисправностей на выходах элементов получил следующий результат: пусть 0 < £ < £о. Р > гДе ^д ~ ми"

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

Д. Улиг [5] для инверсных неисправностей на выходах элементов с вероятностью ошибки е доказал, что для любых сколь угодно малых чисел т и к (г, к > 0) существует такое число е' (е' е (0,1/2)), что при любом е (е € (0,е']) и любом р, удовлетворяющем условию р > (1 + К)еЬд (точнее р > д(£)Ьд), справедливо соотношение ЬРА{п) < (1 + т)р2"/п.

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

С. В. Яблонский [б] рассматривал задачу синтеза надежных схем в базисе В = {Х1&Х2,Х1 V х2,х\1д(х1,х2,хз)}. Он предполагал, что элемент, реализующий функцию голосования д{х\, Хъ, Хз) = а№ У Х\Хз V Х2Х3, абсолютно надежный, а конъюнктор, дизъюнктор и инвертор - ненадежные, подвержены произвольным неисправностям, ненадежность каждого из них не больше е. С. В. Яблонский доказал, что для любого р > 0 существует алгоритм, кото-

9 Лупанов О. Б. Об (у*ном метете синтеза схем // Ичв. вузов. Радиофизика. - 1958. - Т.1, № 1. -С. 120-140.

рый ДЛЯ любого П ДЛЯ каждой булевой функции f(xX, X2i ■ ■ ■, хп) строит такую схему S, реализующую /, что NC(S) < р. L(S) < 2п~1/п.

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

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

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

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

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

K(S) < 5е + cie2, (1)

причем £\ = 1/3600; С! = 10584.

10 Алехина М. А. Синтез асимптотически оптимальных по надежности схем из ненадежных элементов : моногр. - Пенза : ИИЦ ПГУ, 2006. - 156 с.

11 Чугунова В. В. Синтез асимптотически оптимальных по надежности схем при инверсных неис-

правностях на входах элементов : дис. ... канд. физ.-мат. наук. - Пенза, 2007.

13 Васин A.B. Асимптотически оптимальные по надежности схемы в полных базисах из трехвходовых элементов : дис. ... канд. физ. мат. паук. Пенза, 2010.

13 Аксенов С. И. О надежности схем над произвольной полной системой функций при инверсных неисправностях на выходах элементов // Известия высших учебных заведений. Поволжский регион. Серия «Естественные науки». - 2005. - № 6 (21) - С. 42-55.

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

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

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

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

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

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

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

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

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

14 Алехина М. А., Васин А. В. О надежности схем в базисах, содержащих функции не более чем трех переменных // Ученые записки казанского государственного университета. Серия «Физико-математические науки». - 2009. - Т. 151, кн. 2. - С. 25-36.

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

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

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

2П-1

~ ~~п-тт ПРИ п -> оо; а если полный базис В С Вг, то для любой

пук — 1)

булевой функции /, зависящей от п переменных, среднее время вычисления

п-1 2"

и для почти всех функций от п переменных Т(/) > — при

3 п

п —> оо.

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

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

тором условной остановки в произвольном полном конечном базисе. Уделено внимание среднему времени вычисления таких программ.

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

Научная новизна. Основные результаты диссертации являются новыми. Укажем наиболее важные из них. В каждом из двух случаев (абсолютно надежных стоп-операторов и ненадежных стоп-операторов):

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

2. Для всех булевых функций получены верхние оценки ненадежности неветвящихся программ.

3. Найдены нижние оценки ненадежности неветвящихся программ.

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

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

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

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

Апробация работы. Основные результаты диссертации докладывались на международных и российских конференциях и семинарах, среди которых: XVI Международная конференция «Проблемы теоретической кибернетики» (Нижний Новгород, 2011); VIII молодежная научная школа по дискретной математике и ее приложениям (Москва, 2011); Международная научно-техническая конференция «Проблемы автоматизации и управления в технических системах» (Пенза, 2011); Всероссийская научно-практическая конференция «Математика и математическое моделирование» (Саранск, 2011); семинар «Надежность управляющих систем» под руководством профессора Н. П. Редькина (Москва, МГУ им. М. В. Ломоносова, 2011); спецсеминар «Дискретная математика и математическая кибернетика» кафедры математической кибернетики (Москва, МГУ им. М.В. Ломоносова, 2011); научный семинар кафедры теоретической кибернетики (Казань, Казанский (Приволжский) федеральный университет, 2011).

Публикации. Результаты диссертации опубликованы в 11 работах автора, список которых приведен в конце автореферата; среди них б опубликованы в журналах, рекомендованных ВАК для публикации результатов диссертаций. Три работы из 11 написаны в соавторстве с научным руководителем М. А. Алехиной (опубликованные результаты являются собственными, М. А. Алехиной принадлежат постановка задачи и идея доказательства).

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

ОСНОВНОЕ СОДЕРЖАНИЕ РАБОТЫ

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

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

Программа Рг/ вычисляет га-местную булеву функцию /(х) (х = (xi, ..., £„)), если при отсутствии неисправностей в программе Рг/ для любого х е {0, 1}" верно равенство РгДх) = /(х). Предполагается, что все вычислительные операторы независимо друг от друга с вероятностью е (е € (О, 1/2)) подвержены инверсным неисправностям на выходах. Во второй главе будем считать, что операторы условной остановки абсолютно надежны. В третьей главе будем считать, что операторы условной остановки ненадежны, подвержены двум типам неисправностей: первого и второго рода. Определим эти неисправности.

Неисправность первого рода характеризуется тем, что при поступлении единицы на вход стоп-оператора он с вероятностью S (S € (О, 1/2)) не срабатывает, и, следовательно, работа программы продолжается. Неисправность второго рода такова, что при поступлении нуля на вход стоп-оператора он с вероятностью 7] {т} £ (0, 1/2)) срабатывает, и, следовательно, работа программы прекращается. Пусть р = шах{£, <5, rj}.

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

Обозначим А^(/) = inf ЛГДРг), где инфимум берется по всем программам Рг, реализующим булеву функцию /. Программа Рг, реализующая функцию /, называется асимптотически оптимальной по надежности, если Nti{Pr) ~ ВД) при /х -> 0, т.е. lim ^ = 1.

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

ме все операторы условной остановки абсолютно надежны (т.е. 5 = 0, 77 = 0); 2) если ¡1 = е; 3) если неветвящаяся программа не содержит операторов условной остановки.

Обозначим через ЗиЬв^Н) множество всех функций, зависящих от п переменных XI, Х2, ..., хп (п > 3) и полученных из функции Л всевозможными подстановками переменных (т.е. заменой и/или отождествлением переменных).

Обозначим А0(п) = {а^, ..., хп}, Аг(п) = ЗиЬй^/Дх!, ..., Х2Г+1)). где ¡Г(Х1, ..., Х2Г+1) = Х1Х2 V Х1Х314 V Х1Х3Х5Х6 V ... V Х1Х3...Х2г-ЗХ2г-1Х2г V Х1Х3...Х2Т-3Х2Г-1х2г+1 (г > 1, ^ € {гсх, ..., хп} при всех г е Г^).

оо

Обозначим А{п) = |^|Аг(п).

г=0

Пусть К(п) - множество всех неконстантных булевых функций, зависящих от переменных х\, Х2, ..., хп (п > 3), не принадлежащих множеству

ОО

А(п). Обозначим К= и^(п).

п=3

Замечание. Мощность множества А{п) удовлетворяет неравенству |Л(п)| < га2""1.

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

Первая глава диссертации содержит необходимые определения, обозначения и ряд вспомогательных утверждений.

Особенной функцией15 называется функция вида х\х2 ®х2х3 Ф Х1Х3 ® /31Х1 ф /32х2 ф /З3Ж3 ф & (А е {0, 1}, i € {0, 1, 2, 3}).

Пусть В - полный конечный базис, тогда в этом базисе содержится нелинейная функция Д. Из функции Д (Н. П. Редькин [15]) подстановкой переменных можно получить либо некоторую нелинейную функцию двух переменных, либо некоторую особенную функцию. Таким образом, можно считать, что рассматриваемый базис В содержит либо нелинейную функцию двух переменных, либо особенную функцию.

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

В этой главе предложен также метод повышения надежности исходных программ с помощью программы, реализующей некоторую функцию вида х\>х°2г V х\1хаг3 V х?ха33 (<т{ € {0,1}, г € {1, 2, 3}), и с его помощью доказана теорема 1.2: пусть В - полный конечный базис; пусть существует такое N. что любую булеву функцию / можно реализовать неветвящейся программой Я/ с ненадежностью < ЛГ; пусть д(хх, х2, ж3) - функция вида х?х? 4x^x2 чхрх? {а 6 {0,1}, г 6 {1, 2, 3}), Ртд - программа, реализующая функцию д(х 1, х2, х3), а Ргд) - ненадежность программы Ргэ. Тогда любую булеву функцию / в этом базисе можно реализовать такой программой Рг/, что справедливы неравенства

]уРг^) < тах{г;1, и0} + 3^ • Л'ДРг,) + ЗЛГ2,

где I)1 и V0 - вероятности ошибок программы Рг5 на наборах о-2, ст3) и (<71, <72, Сз) соответственно.

Эти неравенства в дальнейшем используются для получения верхних оценок ненадежности программ.

Во второй главе исследуется ненадежность неветвящихся программ с абсолютно надежным оператором условной остановки. В разделе 2.1 разработаны методы синтеза надежных программ и получены верхние оценки ненадежности построенных программ. В разделе 2.1.1 предполагается, что полные конечные базисы содержат нелинейную функцию двух переменных, причем в разделе 2.1.1.1 рассматриваются полные конечные базисы, содержащие обобщенную дизъюнкцию, а в разделе 2.1.1.2 - полные конечные базисы, содержащие обобщенную конъюнкцию. В разделе 2.1.2 исследуются полные конечные базисы, содержащие особенную функцию. В каждом из этих случаев конструктивно доказано (теоремы 2.1-2.5), что любую булеву функцию можно реализовать неветвящейся программой, ненадежность которой при всех е 6 (0, 1/960] не больше е + 4е2.

Таким образом, справедлива теорема 2.6: в произвольном полном конечном базисе любую булеву функцию можно реализовать неветвящейся программой, ненадежность которой при всех £ е (0, 1/960] не больше е + 4е2.

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

Доказана теорема 2.7: в произвольном полном конечном базисе для любой булевой функции / € К и любой неветвящейся программы Рг/ с абсолютно надежными операторами условной остановки, реализующей /, верно неравенство Л^Рг/) > е(1 — е)т (т - число вычислительных операторов в программе Рг}).

Таким образом, из теоремы 2.6 следует, что все булевы функции можно реализовать программами, функционирующими с ненадежностью асимптотически не больше, чем е при е —> 0. Из теоремы 2.7 получаем, что функции из класса К нельзя реализовать программами с ненадежностью асимптотически меньше, чем £ (е —> 0). Следовательно, построенные при доказательстве теоремы 2.6 программы являются асимптотически оптимальными по надежности для функций из класса К, т.е. почти все булевы функции можно реализовать асимптотически оптимальными по надежности программами, функционирующими с ненадежностью, асимптотически равной е при г —>• 0.

В разделе 2.3 исследуется среднее время работы асимптотически оптимальных по надежности неветвящихся программ с абсолютно надежным оператором условной остановки. Доказано (теорема 2.8), что в произвольном полном конечном базисе для почти всех функций среднее время работы асимптотически оптимальных по надежности неветвящихся программ асимптотически не больше чем в 9(1 + г) раз превышает среднее время работы минимальных неветвящихся программ, построенных из абсолютно надежных операторов (т - любое сколь угодно малое положительное число).

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

В разделе 3.1 разработаны методы синтеза надежных программ и получены верхние оценки ненадежности построенных программ.

В разделе 3.1.1 рассматриваются полные конечные базисы, содержащие нелинейную функцию двух переменных, и конструктивно доказано (теорема 3.1), что в полном конечном базисе, содержащем нелинейную функцию

двух переменных, любую булеву функцию / можно реализовать программой Pr¡ с ненадежностью N^Prj) < е + 131^2 при всех е е (0, 1/960] (напомним, что (i = тах{е, 6, rj}). В случае ц = е результат теоремы 3.1 можно улучшить (следствие 3.1): в полном конечном базисе, содержащем нелинейную функцию двух переменных, любую булеву функцию / можно реализовать такой программой Pr¡, что при всех е 6 (0, 1/960] и ц = е верно неравенство Ne(Prf) <£ + 1б£2.

В разделе 3.1.2 рассматриваются полные конечные базисы, содержащие особенную функцию, и конструктивно доказано (теорема 3.2), что в полном конечном базисе, содержащем особенную функцию, любую булеву функцию / можно реализовать программой Pr¡ с ненадежностью N^Prf) < max{e, r¡} + 147/i2 при всех е <= (0, 1/960]. В случае ц = е результат теоремы 3.2 можно улучшить (следствие 3.2): в полном конечном базисе, содержащем особенную функцию, любую булеву функцию / можно реализовать такой программой Рг/, что при всех е 6 (0, 1/960] и ц = £ верно неравенство Ns{Prf) < £ +17£2.

Учитывая результаты следствий 3.1 и 3.2, получаем (теорема 3.3), что в произвольном полном конечном базисе любую булеву функцию можно реализовать такой неветвящейся программой, что при всех е е (0,1/960] и д = е ее ненадежность не больше е + 17е2.

В разделе 3.2 получена нижняя оценка ненадежности неветвящихся программ с ненадежными операторами условной остановки. Доказана теорема 3.4: в произвольном полном конечном базисе для любой булевой функции / е К и любой программы Рг/ с ненадежными операторами условной остановки, реализующей /, верно неравенство ЛГДРг/) > е(1 - ц)т+г, где т - число функциональных операторов; г - число стоп-операторов программы Рг/.

Таким образом, из теоремы 3.3 следует, что все булевы функции можно реализовать программами, которые в случае ц = £ функционируют с ненадежностью асимптотически не больше, чем е при £ 0. Из теоремы 3.4 получаем, что функции из класса К нельзя реализовать программами, функционирующими с ненадежностью асимптотически меньше, чем е (е -» 0) в случае ц — £. Следовательно, программы из теоремы 3.3 являются асимптотически оптимальными по надежности для функций из класса К, т.е. почти

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

В разделе 3.3 исследуется среднее время работы асимптотически оптимальных по надежности неветвящихся программ с ненадежным оператором условной остановки. Доказано (теорема 3.5), что в произвольном полном конечном базисе для почти всех булевых функций среднее время работы таких неветвящихся программ асимптотически не больше чем в 9(1 + т) раз превышает среднее время работы минимальных неветвящихся программ, построенных из абсолютно надежных операторов (т - любое сколь угодно малое положительное число).

В заключении диссертации содержатся выводы и рекомендации по использованию научных результатов.

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

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

N¿Prf) < є + 4er2, и для любой булевой функции / Є К

ВД) > є - сіє2

при всех є Є (0,1/960], где С\ - некоторая положительная константа.

Теорема 2. Для произвольного полного конечного базиса В, любого действительного числа т > 0 существует константа Єї Є (0, 1/2), такая, что при любом ті > 3 всякую булеву функцию / Є К{п) можно реализовать программой Pr¡ с абсолютно надежными операторами условной остановки, для которой при всех є Є (0,£і]

Nt(Prf) - Ne(f) < c2e2, T{Pr¡) < 3(1 + т)р2п/п

при n oo, где сі - некоторая положительная константа.

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

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

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

И/1=£

ЛГЕ(Рг/) <£ + 17е2, и для любой булевой функции / е К

где сз - некоторая положительная константа.

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

ЛГе(Рг/) - ВД) < С4Е2, Г(Рг/) < 3(1 + т)р2п/п

при п со (с4 - некоторая положительная константа).

Из теорем 3 и 4 следует, что в произвольном полном конечном базисе любую булеву функцию / е К можно реализовать асимптотически оптимальной по надежности неветвящейся программой Рг/ с ненадежным оператором условной остановки, ненадежность которой ЛГе(Рг/) ~ £, если р = е и е 0. Среднее время работы таких программ для почти всех функций асимптотически не больше чем в 9(1 +г) раз превышает среднее время работы минимэль-

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

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

ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ

Работы [1-6] опубликованы в журналах, рекомендованных ВАК для публикации результатов диссертаций.

1. Грабовская, С. М. Синтез надежных неветвящихся программ с условной остановкой в полном конечном базисе, содержащем Х\&,Х2 / С. М. Грабовская // Известия высших учебных заведений. Поволжский регион. Физико-математические науки. - 2010. - № 3 (15). - С. 43-54.

2. Грабовская, С. М. О надежности неветвящихся программ в базисе, содержащем функцию вида х"1 \/х^ / С. М. Грабовская // Известия высших учебных заведений. Поволжский регион. Физико-математические науки. - 2010. - № 4 (16). - С. 26-38.

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

4. Грабовская, С. М. О надежности неветвящихся программ в базисе, содержащем функцию вида х^кх^ / С. М. Грабовская // Дискретный анализ и исследование операций. - 2012. - Т. 19, № 1 - С. 33-40.

5. Алехина, М. А. Нижняя оценка ненадежности неветвящихся программ с оператором условной остановки / М. А. Алехина, С. М. Грабовская II Известия высших учебных заведений. Поволжский регион. Физико-математические науки. - 2012. - N2 1 (21). - С. 44-56.

6. Алехина, М. А. О надежности неветвящихся программ в произвольном полном конечном базисе / М. А. Алехина, С. М. Грабовская // Известия высших учебных заведений. Математика. - 2012. - № 2. - С. 13-22.

7. Грабовская, С. М. О верхней оценке ненадежности неветвящихся программ в некоторых базисах / С. М. Грабовская // Проблемы автоматизации и управления в технических системах : тр. Междунар. науч.-техн. конф. (г. Пенза. 19-22 апреля 2011 г.). - Пенза : Изд-во ПГУ, 2011. -Т. 1. - С. 116-120.

8. Алехина, М. А. О методах повышения надежности схем и неветвящихся программ / М. А. Алехина, С. М. Грабовская // Проблемы теоретической кибернетики : материалы XVI Междунар. конф. (г. Нижний Новгород, 20-25 июня 2011 г.). - Нижний Новгород : Изд-во Нижегородск. гос. ун-та, 2011. - С. 30-33.

9. Грабовская, С. М. О надежности неветвящихся программ в базисах, содержащих нелинейную функцию двух переменных / С. М. Грабовская // Проблемы теоретической кибернетики : материалы XVI Междунар. конф. (г. Нижний Новгород, 20-25 июня 2011 г.). - Нижний Новгород : Изд-во Нижегородск. гос. ун-та, 2011. - С. 122-125.

10. Грабовская, С. М. О среднем времени работы неветвящихся программ в произвольном полном конечном базисе / С. М, Грабовская // Математика и математическое моделирование : тр. Всерос. науч.-практич. конф. (г. Саранск, 13-14 октября 2011 г.). - Саранск : Изд-во Мордовск. гос. пед. ин-та им. М. Е. Евсевьева, 2011. - С. 25-29.

И. Грабовская, С. М. О верхней оценке ненадежности неветвящихся программ с ненадежным оператором условной остановки / С. М. Грабовская /I Материалы восьмой молодежной школы по дискретной математике и ее приложениям (г. Москва, 24-28 октября 2011 г.). - М. : Изд-во мех.-мат. ф-та МГУ им. М. В. Ломоносова, 2011. - Ч. 1. - С. 18-23.

Научное издание

Грабовская Светлана Михайловна

АСИМПТОТИЧЕСКИ ОПТИМАЛЬНЫЕ ПО НАДЕЖНОСТИ НЕВЕТВЯЩИЕСЯ ПРОГРАММЫ С ОПЕРАТОРОМ УСЛОВНОЙ ОСТАНОВКИ

Специальность 01.01.09 — дискретная математика и математическая кибернетика

Редактор Ю. В. Коломиец Компьютерная верстка С. М. Грабовской

Подписано в печать 19.04.2012 Формат 60 х 84 1/16 Усл. печ. л. 1,40.

_Заказ N' 349 Тираж 100._

Издательство ПГУ Пенза, Красная, 40 Тел./факс: (8412) 56-47-33; e-mail: ¡ic@pnzgu.ru

Текст научной работы диссертации и автореферата по математике, кандидата физико-математических наук, Грабовская, Светлана Михайловна, Пенза

61 12-1/1119

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

Грабовская Светлана Михайловна

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

01.01.09 — дискретная математика и математическая

Диссертация на соискание ученой степени кандидата физико-математических наук

Научный руководитель: доктор физико-математических наук, профессор Алехина М.А.

Пенза 2012

На правах рукописи

кибернетика

Оглавление

Введение ' 3

Глава 1. Основные понятия и вспомогательные утверждения 17 Глава 2. Неветвящиеся программы с абсолютно надежным

оператором условной остановки 25

2.1 Верхняя оценка ненадежности неветвящихся программ ... 25

2.1.1 Базисы, содержащие нелинейную функцию двух переменных................................................25

2.1.2 Базисы, содержащие особенную функцию..............35

2.2 Нижняя оценка ненадежности неветвящихся программ ... 42

2.3 Среднее время работы неветвящихся программ................57

Глава 3. Неветвящиеся программы с ненадежным оператором

условной остановки 60

3.1 Верхняя оценка ненадежности неветвящихся программ ... 60

3.1.1 Базисы, содержащие нелинейную функцию двух переменных................................................60

3.1.2 Базисы, содержащие особенную функцию..............67

3.2 Нижняя оценка ненадежности неветвящихся программ ... 74

3.3 Среднее время работы неветвящихся программ................77

Заключение 80

Литература 86

Введение

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

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

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

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

Впервые задачу синтеза надежных схем из ненадежных функциональных элементов рассматривал Дж. фон Нейман [3]. Он предполагал, что элементы схемы подвержены инверсным неисправностям на выходах, когда функциональный элемент с приписанной ему булевой функцией </? в неисправном состоянии, в которое переходит независимо от других элементов схемы с вероятностью £ (е € (0,1/2)), реализует функцию (р. С помощью итерационного метода Дж. фон Нейман установил, что произвольную булеву функцию можно реализовать схемой, вероятность ошибки на выходе которой при любом входном наборе значений переменных не превосходит се при любом в € (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 базиса, для которых 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,1/2)), что при любом г (е Е (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, а = 10584.

Позднее М. А. Алехиной и А. В. Васину [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), содержащего функцию, существенно зависящую от к переменных, приведенный вес р = Следовательно, при к > 3 среднее время работы (сложность) минимальных схем для почти всех функций в два раза больше, чем среднее время работы неветвящихся программ с оператором условной остановки. Если к — 2, то для почти всех функций отношение среднего времени работы (сложности) минимальных схем к среднему времени работы неветвящихся программ с оператором условной остановки не больше 3.

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

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

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

В частности, в обозначениях Л^ДРг) и Nß(f ) вместо символа ¡1 будем использовать символ если 1) в неветвящейся программе все операторы условной остановки абсолютно надежны (т.е. ö = 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. В любом полном конечном базисе для любой булевой функции f существует такая неветвящаяся программа Рг/ с абсолютно надежным�