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

• Автор: Грабовская, Светлана Михайловна
• Шифр специальности: 01.01.09
• Научная степень: Кандидатская
• Год защиты: 2012
• Место защиты: Пенза
• Количество страниц: 89 с.

Оглавление
Введение '
Глава 1. Основные понятия и вспомогательные утверждения 17 Глава 2. Неветвящиеся программы с абсолютно надежным оператором условной остановки
2.1 Верхняя оценка ненадежности неветвящихся программ
2.1.1 Базисы, содержащие нелинейную функцию двух переменных
2.1.2 Базисы, содержащие особенную функцию
2.2 Нижняя оценка ненадежности неветвящихся программ
2.3 Среднее время работы неветвящихся программ
Глава 3. Неветвящиеся программы с ненадежным оператором
условной остановки
3.1 Верхняя оценка ненадежности неветвящихся программ
3.1.1 Базисы, содержащие нелинейную функцию двух переменных
3.1.2 Базисы, содержащие особенную функцию
3.2 Нижняя оценка ненадежности неветвящихся программ
3.3 Среднее время работы неветвящихся программ
Заключение
Литература

Введение
Одной из важнейших задач математической кибернетики является задача синтеза надежных программ (схем) из ненадежных операторов (элементов).
Неветвящиеся программы (с оператором условной остановки или без него), реализующие булевы функции, относятся к числу основных модельных объектов математической теории синтеза, сложности и надежности управляющих систем. Неветвящиеся программы с оператором условной остановки [1,2] отличаются от неветвящихся программ наличием управляющей команды - команды условной остановки, дающей возможность досрочного прекращения работы программы при выполнении определенного условия, а именно, при поступлении единицы па вход оператора условной остановки (который еще называют стоп-оператором).
Разработка специальных методов синтеза как для схем из ненадежных функциональных элементов, так и для неветвящихся программ с оператором условной остановки связана главным образом с выбранной математической моделью неисправностей. Одна из основных моделей определяется инверсными неисправностями на выходах функциональных элементов схемы и вычислительных операторов неветвящейся программы. В диссертации решается задача построения асимптотически оптимальных (асимптотически наилучших) по надежности неветвящихся программ с оператором условной остановки в предположении, что все вычислительные операторы подвержены инверсным неисправностям на выходах, а операторы условной остановки могут быть как абсолютно надежны (2- я глава), так и ненадежны, подвержены двум типам неисправностей (3-я глава). Задача решается во всех полных конечных базисах. Уделяется внимание среднему времени работы асимптотически оптимальных по надежности неветвящихся программ с оператором условной остановки.
Известно, что схемы из функциональных элементов (ФЭ) являются моделями электронных схем, а неветвящиеся программы (как с условной остановкой, так и без нее) моделируют работу вычислительных устройств.
Однако, несмотря на эти различия, результаты о надежности и сложности, полученные для схем из функциональных элементов переносятся на неветвящиеся программы без стоп-операторов и наоборот.
До появления работ автора задача построения надежных (а также и асимптотически оптимальных по надежности) неветвящихся программ с оператором условной остановки не рассматривалась, поэтому приведем известные и связанные с тематикой диссертации результаты о надежности и сложности схем из ненадежных функциональных элементов и о среднем времени вычисления неветвящихся программ с оператором условной остановки (в предположении, что все операторы программ абсолютно надежны)
Впервые задачу синтеза надежных схем из ненадежных функциональных элементов рассматривал Дж. фон Нейман [3]. Он предполагал, что элементы схемы подвержены инверсным неисправностям на выходах, когда функциональный элемент с приписанной ему булевой функцией (/? в неисправном состоянии, в которое переходит независимо от других элементов схемы с вероятностью £ (е € (0,1/2)), реализует функцию (р. С помощью итерационного метода Дж. фон Нейман установил, что произвольную булеву функцию можно реализовать схемой, вероятность ошибки на выходе которой при любом входном наборе значений переменных не превосходит се при любом е £ (0,1/6] (с - некоторая положительная константа)
Для повышения надежности схем Дж. фон Нейман использовал схему, реализующую функцию голосования (медиану) т{х, Х2, Хз) = Х1Х2 V ХХз /Х2Хз, и многократное дублирование исходных схем, что, естественно, приводило к увеличению сложности схем (примерно в 3' раз, где к - число итераций). Поэтому именно сложности уделялось главное внимание в дальнейших исследованиях, среди которых отметим результаты С. И. Ор-тюкова [4], Д. Улига [5], С. В. Яблонского [6]. Чтобы сформулировать эти результаты, введем необходимые понятия и определения.
Полное (в Рг) конечное множество В ~ {е]

Теперь возьмем в качестве программы Щ программу Pr j и построим новую программу, которую обозначим через Prf. Оценим ненадежность программы Prf, используя неравенство (12):
Ne(Prf) тах{е-Ь1,06е2 + 2(1.06е)2, £-2 + 4(1. 0б£-)£ + 4(1. Обе)2} е + 4е1
при всех е Е (0, 1/960].
Программа Prf - искомая.
Теорема 2.4 доказана.
Таким образом, во всех полных конечных базисах, содержащих нелинейную функцию двух переменных, любую булеву функцию / можно реализовать неветвящейся программой Prf, ненадежность которой при всех £ Е (0, 1/960] удовлетворяет неравенству Ne(Prf) е + 4е2.
2.1.2. Базисы, содержащие особенную функцию
Пусть теперь полный конечный базис В содержит особенную функцию ip(x 1, Х2, Хз) = ХХ2 © Х2Х3 0 Х1Х3 0 ßiXi 0 ß2X2 0 РзХз 0 ßo, где ßo, ßi, ßi) ß3 € {0, 1}. Справедлива теорема 2.5.
Теорема 2.5. В полном конечном базисе В, содержащем функцию вида ip(x 1, Х2, Хз) = Х1Х2 0 Х2Хз 0 ХХз 0 ßiXi 0 ß2x2 0 РзХз 0 ßo
(ßo, ßi, ß2, ß3 G {0, 1}), любую булеву функцию f можно реализовать такой неветвящейся программой Prf, что при всех е Е (0, 1/960] справедливо неравенство Ne(Prf) е + 4в2.
Доказательству теоремы 2.5 предпошлем леммы 2.4 - 2.7.
Лемма 2.4. Если полный конечный базис содержит функцию х2, Хз) = XiX2 0 Х2Х3 0 хххз 0 х 0 х2 0 хз 0 1, то в этом базисе функцию д(хь х2, х3) = ХХ2 V х2х3 V хХз можно реализовать неветвящейся программой Ргд, ненадежность которой Ne(Prg) е.
Доказательство. Пусть В - полный конечный базис, ipi(x, х2, x3) Е В. Построим в этом базисе неветвящуюся программу Prg (см. приложение, с. 84), реализующую функцию g{x, х2. х3) = хх2 V х2х3 V тщ'з-