Поведение схем из функциональных элементов при наличии источников неисправностей тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

, 1 "К^оскойскни государешеипий университет им. М. В. Ломоносова

(факультет пы'шслктслытй математики и кибернетики

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

Дэн Бэнсин

УДК 519.7

ПОВЕДЕНИЕ СХЕМ ИЗ ФУНКЦИОНАЛЬНЫХ ЭЛЕМЕНТОВ ПРИ НАЛИЧИИ ИСТОЧНИКОВ НЕИСПРАВНОСТЕЙ

01. 01. 09 — математическая кибернетика

Автореферат

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

МОСКВА - 1997

Работа выполнена на кафедре математической кибернетики факультета вычислительной математики и кибернетики Москонскот государственного университета им. М. В. Ломоносова.

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

член-корреспондент РАН, профессор С. В. Яблонский

Официальные оппоненты: доктор фюико-матемагических наук,

профессор Н. П. Редькии кандидат физико -математических наук, старший научный сотрудник X. А. Мадатнн

Ведущая организация: Институт системного программирования РАН

Заплта диссертации состоится " 2. " июля 1997 г. В "15-00" часов на заседании диссертационного совета IC.053.05.84 при Московском государственном университете им. М. В. Ломоносова но адресу: 119899, ГСП, Москва, Воробьевы горы, Научно-исследовательский вычислительный центр Московского государственного университета им. М. В. Ломоносова, аудитория "_1_".

С диссертацией можно ознакомиться в библиотеке НИВЦ МГУ.

Автореферат разослан " 6 " июня 1997 г.

Ученый секретарь диссертационного совета . кандидат физико-математических науХ^--в в Суворов

л

01НЦЛЯ ХАРАКТЕРИСТИКА РАБОТЫ Акту,'ми,иосп, теми

Изучение «опросов поведения ущиш.>!::-.нпих систем при наиичии источников нсиспранностей является лажной задачей теории надежности схем — одного из основных разделов математической кибернетики. Решению этой задачи для схем из функциональных элементе» и посвящена настоял-дя работа. Неослабевающий интерес к схемам из функциональных элементов. которые исследуются уже довольно продолжительное нремя, вызван в первую очередь тем, что схемы из функциональных элементов продолжают оставаться удобной математической моделью, служащей для описания многих реалыIих современных управляющих сиспчг Современные технологии, позволяющие производил!, схемы с большим числом элементов, делают более актуальной задачу изучения вопросов ненадежности таких схем.

Петь работы

Напомним, 'г го известно дна основных способа или типа вероятностного описания поведения схем из функциональных элементов при наличии источников неисправностей. Первый способ вероятностного описания иредпола1ас1, что каждому элементу базиса Б, над которым строятся схемы, сопоставляется список его неисправных состояшг: и вероятности перехода в эти состояния. Второй способ вероятностного описания предполагает, что каждому элементу Б базисл Б сопоставляется набор из вероятностей неправильной работы И на различных наборах значений его входных переменных. Оба эти способа являются полными к том смысле, что по описанию поведения элсмешов Б может быть найдено

с и о гв ез стъу ю ще с описали с для любой схемы из функциональна с элементов над Б.

Из работ С. В. Яблонского было известно, что вероятностное описание первою пша позволяет однозначно воопановигь связанное с ним вероятносшое описание второго типа, а обратный переход является, вообще говоря, неоднозначным. Имеете с тем комбинаторные и алгебраические особенности обратного перехода были исследованы слабо. Из работ Дж. фон. Нейматга было известно, что для специалт.тшх источников неисправностей, называемых неймановскими, существует положительная нижняя граница ненадежности схем, построенных из элементов базиса Б, которая вычисляется по вероятностному описанию элеменшв Б. Вмесге с тем класс тех источников неисправностей, для которых такая граница сущестнуег, не был исследован достаточно полно. Це.тью настоящей работы является изучение особенностей перехода от вероятностного описания второго пша к соответствующему вероятностному списанию первого типа для схем из функциональных элементов при наличии источников неисправностей, исследование тех источников неисправностей, для которых существует положительная нижняя граница ненадежности схем, а также исследование источников неисправностей с малым числом надежных наборов.

Научная иовизна

Научная новизна диссертации состоит в следующем:

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

(2) Получено обобщение теоремы Дж. Фон. Неймана о

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

Теоретическая и практическая ценность

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

Методика исследования

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

Апробация работы

Результат настоящей работа докладывались на кафедре математической кибернетики факультета ВМиК МГУ, доклад по результатам диссертации включен в программу очередной международной конференции " Дискретные -модели в теории управляющих систем"

(Подмосковье, июнь 1997).

Структура и объем работы

Работа состоит из введения и двух глав, разбитых на 6 параграфов, а также списка литературы, включающего 13 наименований. Общий объем работы — 61 страница. Изложение материала иллюстрируется 35 рисунками и 11 таблицами.

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

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

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

Материал главы разбит на два параграфа.

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

Пусть £ — схема из функциональных элементов с входными переменными х11 = <хь . . , хЕ), О — система, состоящая из ш ра «личных булевских функций от переменных х", которые схема 2 реализует в различных неисправных состояниях:, порожденных источником неисправностей, Р — вектор длины ш, компоненты которого задают

вероятности этих состояний, и пусть функция ч = ч(х") характеризует вероятность неправильном работа схемы X на различных наборлх значений переменных х". Вектор 1' называется невырожденным, если

т

1\ >0 (1-12.....т) и

Основное утверждение §1 — теорема 1.1. В ней доказывается, чти в случае с^ 0 существует невырожденный вектор Р, соответствующий заданной функции q ира некоторой системе в.

В §2 Исследуются некоторые комбинаторно-алгебраические особенности решения системы линейных уравнений вида:

МхР=<3 (1)

где М — матрица длины н высоты я из 0 и 1, состоящая из различных строк таблицы значений булевских функций системы О, а действитетыгый столбец высоты в получается в результате соответствующей "свертки" столбца значений функ^ш q(xIl). Множество тех векторов для которых уравнение (1) имеет решение при некотором "вероятностном" векторе Р япчяется выпуклым мншограгашком Н евклидова Б-мерного пространства, причем вершинами этого многогранника служат столбцы М.

В этом параграфе приводятся некоторые утверждения, среди которых выделим лемму 2.1 и теорему 2.1.

Лемма 2.1 выявляет все типы решений уравнегагя (1) при различных способах выбора вектора

— если находится вне Н, то решений нет;

— если <3 находится на границе Н, то имеется вырожденное решение;

— если <3 находится внутри Н, то имеется невырожденное решение. В теореме 2.1 доказывается, что для каждого вектора С2 можно

путем конечного перебора перечислить все типы матриц М, допускающих

невырожденный вектор Р.

Во второй главе изучаются источники неисправностей с существенными наборами (ИНСН) и источники с малым числ )м падежных входных наборов. Материал глявы разби т на два параграфа.

В §3 даезся определение ИНСН, которые удовлетворяют условно:

для любого входного набора [3 е £П1 каждого элемента Р, базиса Б существуют функциональные повреждения и такие, что

Л;1"/1 ((3) = 0, ($) = 1., приводятся примеры, а также устанавливаются некоторые свойства ИНСН и оценивается их доля в классе всех источников неисправностей.

Основное утверждение этого параграфа — теорема 3.1, которая является обобщением теоремы Неймана и доказывает существование положите .'Гьной нижней границы для ненадежности схем из функциональных элементов над базисом с ИНСН при любом из двух рассматриваемых способов описания.

В §4 исследуются легочники неисправностей с малым числом надежных входных наборов. Вводится понятие константно-надежных источников неисправностей (КНИН), которые харптд еризуются тем, что любой элемент базиса на всех своих надежных наборах реализует одно и то же значение-. Главное утверждение §4 — теорема 4.2, в которой доказывается, что любая схема из функциональных элементов над базисом с КНИН, реализующая в исправном состоянии функцию, отличную от константы, удовлетворяет теореме Неймана п ослабленной формулировке, согласно которой ненадежность схемы Е но крайней мере на одном входном наборе должна быть не меньше, чем положительная консгапта б, зависящая только от базиса Б.

ч

Лшор иыражао ¡лубокую благодарность научному руководителю член-корреспонденту 1'ЛН, профессору С. В. Яблонскому ta поетянную помощь и ценные сонеты при ио;п отопке данной диссертационной работы. процессе исследования «шор постоянно нольчоналгя сонетами н консультациями доцента С. А. Ложкина. Аитор также ни ража ет ему спою п.чаголармооъ.