Введение к работе
Актуальность темы диссертации. Укрупнение масштабов производства t прогресс компьютерных технологий в последние два десятилетия пособствовали развитию математической теории надежности больших .'истем. Потребность в развитом математическом аппарате привела к формированию двух основных направлений исследований:
а) вероятностные методы, основанные на предельных теоремах теории
іероятностей, статистическом моделировании, теории массового
>бслуживания и теории случайных процессов;
б) методы дискретной математики, основанные на булевой алгебре,
;омбинаторном анализе, теории графов и гиперграфов, теории алгоритмов и
:ложности вычислений, теории коммуникационных сетей.
В рамках первого направления в странах бывшего СССР, включая Беларусь, сложились научные школы мирового уровня. Второе направление, і пределах которого возможно создание эффективных сомпыотерноориентированных методов анализа высоконадежных :ложных систем, особенно интенсивно развивается в США, Канаде* и Яндни, что отражено в многочисленных монографиях, учебниках, справочной и обзорной литературе. Исследования, проведенные в гиссертацни, относятся именно к этому направлению и их актуальность эаскрывается ниже.
Проблемы вычисления комбинаторной надежности и надежностного покрытия гиперграфов в эквивалентных формулировках — в терминах монотонных бинарных систем, клатгеров, симплициальных комплексов, эулевых функций — известны в литературе уже более 40 лет. Ключевыми здесь являются алгоритмические задачи точного и приближенного вычисления полиномов надежности гиперграфов, а также задачи синтеза максимально надежных графов с предписанными значениями параметров, характеризующих пропускные способности вершин и ребер. Большинство разработанных в этой области подходов и методов было предназначено для сетевых моделей мультитермннальной надежности, и потому ограничено 2-униформными гиперграфами, т. е. графами и мультиграфами. В связи с этим оставались открытыми задачи оценки полиномов надежностного и связного надежностного покрытия гиперграфов, а также задачи алгоритмической классификации двойственных проблем надежности и синтеза максимально надежных элементов в классах гиперграфов с предписанными степенными параметрами.
В начале 80-х годов была разработана теория доминирования, сыгравшая важную роль в эволюции комбинаторных методов анализа надежности сетевых структур. На ее основе были усовершенствованы многочисленные
методы расчета надежности графов, использующие принципы включенії)
исключения и факторизации/ и выявлены среди них оптимальнь
алгоритмические стратегии. Впоследствии границы этой теории был
значительно раздвинуты благодаря установлению взаимосвязи функци
доминирования клаттеров с матроидными инвариантами симплициальны
комплексов и Полиномами надежности гиперграфов. Однако диапазон это
теории охватывал только традиционные модели сетевой надежности, и
позволяющие учитывать произвольную М0Н0ТОНІГ/Ю логик
функционирования в вершинах графов. .
Особенности двойственных проблем надежности для графоидны гиперграфов определяются свойствами индуцирующих их графов, чт требует разработки специальных методов решения этих проблел Центральными здесь являются проблемы вычисления оллполюсной резидуалыюй надежности различных классов графов. Интенсивное изучени первой было обусловлено тем, что связанные с нею графоидные гиперграф] обладают матроидальными и шеллинговыми свойствами. Это послужил причиной появления эффективных методов для ее приближенного решенш Вторая проблема оставалась малоизученной ввиду немонотонности системі путей индуцированного ею1 графоидного гиперфафа и как следствш неприменимости сложившихся подходов, используемых для расчета и оценк оллполюсной надежности. Незавершенными оставались также исследовани по алгоритмической классификации двойственных проблем надежности узких подклассах графоидных гиперграфов.
Связь работы с крупными научными программами, темаміі Исследования проводились в рамках следующих госбюджетных научны тем:
Республиканская профамма важнейших научно-исследовательских рабо в области естественных, технических и общественных наук п Белорусской ССР на 1986—1990 гг.,'утвержденная постановление? № 39 Президиума АН БССР от 03.04.86, тема Машиностроение 0 "Развитие теории прогнозирования надежности структурно-сложны систем машин и их элементов, разработка методик, программных і аппаратурных средств оценки надежности",. 1986—1990, № roc регистрации 01860016567; і
Исследование дискретных объектов с предписанными1 свойствами, 1996-1997 гг. (план НИР Белгосуниверситета, приказы БГУ № 216-Д от 19.03.9 и№438-Дот 14.05.97), № гос. регистрации 19962634;
Характеризационные и алгоритмические аспекты теории графов и булевы функций, 1997—1999 гг. (распоряжение Министерства образовани Республики Беларусь № 05-9/5 от 13.01.97), № гос. регистрации 19974238;
— Разработка универсальных математических методов анализа надежности сложных систем, 1996—1997 гг., утверждена Министерством образов; кия и науки Республики Беларусь, приказ №. 60 от 16.02.96, № гос. регистрации 1996403.
Цель и задачи исследований. Целью исследования является разработка универсальных комбинаторных моделей и методов анализа надежности "иперграфов с предписанными структурными свойствами. Задачами «следования являются: алгоритмическая классификация двойственных іроблем надежности и синтез максимально надежных элементов в классах -иперграфов с предписанными структурными свойствами; получение )ффективно вычислимых оценок основных полиномов надежности ^иперграфов; создание универсальной модели мультитерминальной тадежностн графов с произвольной монотонной логикой в вершинах и эаспространение на эту модель теории доминирования.
Объект и предмет исследования. Объектом исследования являются :труктурно-с ложные системы и устройства, для которых возникает необходимость разработки комбинаторных методов анализа надежности. Предметом исследования являются математические модели таких систем, алгоритмическая сложность соответствующих задач, точные и приближенные методы их решения.
Методология и истоды проведенного исследования. Использовались методы теории сложности вычислений, теории графов, булевой и пороговой to гики, комбинаторной теории бинарных матриц, теории надежности коммуникационных сетей.
Ряд новых методов разработан автором диссертации, в том числе общий иетод получения нижних оценок коэффициентов полиномов надежности гиперграфов; единый декомпозиционный подход для решения проблем эезидуальной надежности в наследственных (относительно композиции) классах графов.
Разработана новая техника доказательства полиномиальной :водимости перечислительных задач на базе модифицированного метода локальных замен, использующего рекуррентные соотношения для анализа числовых свойств структурных характеристик добавляемых модулей.
Разработана конструктивная методология получения факторизационных георем и алгоритмов синтеза гиперграфов с предписанными значениями иереключателыю совершенных параметров.
Научная новизна и значимость полученных результатов. Получена алгоритмическая классификация проблем вычисления комбинаторной надежности и надежностного покрытия в классах гиперфафов с ограниченными степенными параметрами. Тем самым решена открытая
задача алгоритмической сложности двойственных проблем надежности ду униформных гиперграфов с разреженной реберной структурой.
Разработан метод регуляризации для получения эффективно вычислимь нижних оценок коэффициентов основных полиномов надежност гиперграфов. С этой целью определен аналог регулярных гиперграфов классе всех гиперграфов — реберно-регулярные гиперграфы, и введен операции ;сдвигов на .гиперграфах. Доказано, что эти операции і увеличивают коэффициентов полиномов надежности и за полиномиальш время с их помощью гиперграфы и униформные простые гиперграфы мoж^ преобразовать соответственно в реберно-регулярные и регулярнь гиперграфы. Показано, что структурные свойства реберно-регулярнь гиперграфов позволяют генерировать подклассы канонических гиперграфо полиномы надежностного и связного надежностного покрытия которь эффективно вычислимы; в то же время получена структурная характеризащ путей и сечений регулярных гиперграфов, давшая эффективные алгоритм вычисления их полиномов комбинаторной надежности. На основе эп результатов решены две открытые задачи, изученные ранее в частнь случаях: а) эффективная оценка полиномов надежностного и связної надежностного покрытия униформных гиперграфов; б) структури; характеризация гиперфафов, имеющих наименьшие коэффициент полиномов надежности в классах униформных гиперфафов фиксированными числами вершин и ребер. В серии прямых следствг получены усиления известных результатов о полиномиальной дуализаш регулярных гиперфафов и свойствах регулярных гиперфафо индуцирующих матроидные комплексы.
Разработана единая теоретическая основа для решения задач синте: максимально надежных элементов в классах гиперфафов с предписанные значениями переключательно совершенных параметров. Это достигается помощью конструктивного аппарата, унифицирующего теоремы переключениях и обобщающего их на гиперфафы. На базе этого аппарата качестве прямых следствий решены: задача выявления множес: гипергр чфов, в которых основные виды степенных последовательности становятся переключательно совершенными, и задача эффективно] построения элементов в множествах связных гиперфафов с предписанньи степенными последовательностями.
Построена новая модель мультитерминальной надежности монотонный фаф, представляющий собой графовую суперпозицию прость гиперфафов, что дает возможность моделировать с их помощью сложнь системы с сетевой структурой и произвольной монотонной логик< функционирования в вершинах. Монотонные фафы обобщают в< традиционные модели мультитерминальной надежности — d-тривиальні
графы, которые являются их специальными случаями. На монотонные графы распространена теория доминирования, что позволило достичь максимально возможной конденсации символьных выражений надежности и определить фаничные подклассы монотонных графов, для которых существуют :оответственно псевдополиномиальные и квазиполнномиальные алгоритмы решения проблемы комбинаторной надежности. Параллельно' выявлена клаттерная природа всех ранее известных результатов о доминировании d-гривиальных графов. Получена структурная характеризацня основных подклассов монотонных графов, обладающих пороговой живучестью, завершающая, в частности, эффективное описание ^-тривиальных графов с гаким же свойством.
Завершена алгоритмическая классификация (начатая другими авторами) проблем вычисления полиномов надежности в подклассах графоидных гиперграфов: а) определены фаницы, разделяющие ЯР-полные и полиномиально разрешимые подзадачи проблемы вычисления полинома надежностного покрытия фафоидных гиперфафов, индуцированных деревьями Офаниченной степени и диаметра; б) доказана гипотеза о UP-полноте проблемы вычисления полинома оллполюсной надежности з классе гамильтоновых фафов; в качестве следствий аналогичные результаты установлены в классах фафов, близких к полным и полным двудольным; в) ткрыт вопрос об алгоритмической сложности проблемы вычисления полинома резидуальной надежности для основных расширений пороговых фафов; при этом все результаты о полиномиально разрешимых случаях получены на основе единого декомпозиционного подхода, применимого гакже к любому свойству фафов, которое наследственно относительно эперации композиции или подвергалось бы легко обозримым изменениям, делающим это свойство наследственным.
Все результаты являются новыми. Некоторые из них включены (с :оответствующими ссылками) в несколько монофафий по дискретной математике и теории надежности, в том числе в монофафию Mahadev N., Peled U. "Tlireshold graphs and related topics", Amsterdam — New York, 1995.
Практическая значимость полученных результатов. Ряд моделей и теоретических обобщений, разработанных в диссертапии, возникли из конкретных практических задач в рамках хоздоговорных НИР, выполненных автором в составе фуппы ответственных исполнителей в Институте проблем надежности машин АН БССР по заказу предприятия п/я 5537 Министерства авиационной промышленности СССР.
Рігппботанньїе автором методы и алгоритмы вошли составной частые з заботу "Алгоритмические методы оценки и оптимизации надежности технических систем с сетевой структурой", удостоенной премии Академии наук БССР за лучшую НИР (1990 г.).
Методы и алгоритмы, разработанные в диссертации, могут был использованы в задачах анализа и синтеза сложных систем, при оптимальної^ проектировании высоконадежных систем со структурными ограничениями для решения задач живучести систем.
Основные положения диссертации, выносимые на защиту. На защи-р выносятся:
— классификация в соответствии с алгоритмической сложностьк
двойственных проблем надежности в классах гиперграфов (
ограниченными степенными параметрами;
общий метод получения эффективно вычислимых нижних оценої основных полиномов надежности гиперграфов на базе комбинаторны) свойств регулярных и реберно-регулярных гиперграфов;
единая теоретическая методология для решения задач синтезг максимально надежных гиперграфов в классах гиперграфов ( предписанными значениями переключательно совершенных параметров;
универсальная графовая модель мультитерминальной надежности — монотонный граф; теория доминирования для монотонных графов і определение на ее основе граничных классов монотонных графов, дл? которых существуют псевдополиномиальные и квазиполиномиальныЕ алгоритмы решения проблемы комбинаторной надежности; эффективные характеризации основных подклассов монотонных графов, обладающи> пороговой живучестью;
— вклад в алгоритмическую классификацию проблем вычисления полиномое
надежности графоидных гиперграфов: полиномиальные алгоритмы
решения, доказательства йР-полноты и #Р-трудности этих проблем е
разлігчньїх классах графоидных гиперграфов.
Личный вклад соискателя. Все основные результаты диссертации получены автором самостоятельно. Из всех совместных работ, не считав авторских свидетельств на изобретения, в диссертацию включены толькс результаты, полученные лично автором. Что касается авторских свидетельсті [33, 34], то идеи изобретений в них принадлежат лично автору, а формуль изобретений принадлежат автору и соавторам в равной степени и включены і приложение к диссертации.
Апробация результатов диссертации. Результаты исследований включенных в диссертацию, докладывались на следующих научных форумах 4-я Всесоюзная научно-техническая конференция по повышению качестве функционирования и надежности информационных сетей и их элементов, г Новосибирск, 1981 г.; Республиканская научно-техническая конференция "Путг повышения технического уровня и надежности машин", Минск, 1986 г.; 30-f и 33-й Международные коллоквиумы по технической кибернетике математике и вычислительной технике "Графы и сети — теория г
риложения", г. Ильмєнау, Германия, 1985 г., 1988 г.; Республиканская аучно-техническая конференция "Проблемы качества и надежности изделий лектронной техники, радиоэлектронной аппаратуры и средств управления", 4инск, 1988 г.; Международный симпозиум по надежности в электронике RELECTRONIC91" г. Будапешт, Венгрия, 1991 г.; Всесоюзная научно-ехническая конференция по повышению надежности машин и приборов, г. Куйбышев, 1991 г.; Европейская конференция по индустриальной іатематнке, г. Прага, Чехия, 1994 г.; 4-й Международный конгресс по ндустриальной и прикладной математике "ІСІАМ 99", г. Эдинбург, Нотландия, 1999 г.; семинар Белорусского математического общества, г. 4инск, 1999 г.; семинары по теории графов и гиперграфов механико-іатематического факультета Белгосуниверситета, 1997—1999 гг.
Опублнкованность результатов. Основные результаты диссертации публикованы в работах [1—41], из которых 30 публикаций в журналах [1— 0], 2 публикации в сборниках работ [31, 32], 2 авторских свидетельства на зобретения [33, 34], 5 тезисов докладов и выступлений [35—39], 2 .епонированные рукописи [40, 41]. Общее количество страниц публикованных материалов — 288 журнальных страниц.
Структура и объем диссертации. Диссертация состоігт из общей характеристики работы, 4 глав, заключения, списка использованных істочников и одного приложения. Объем диссертации 230 страниц. Список юпользованных источников содержит 204 наименований.