автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.18, диссертация на тему:Быстрые алгоритмы вычисления надежности случайных сетей

004615067

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

Лосев Александр Сергеевич

Быстрые алгоритмы вычисления надежности случайных сетей

Специальность: 05.13.18 - Математическое моделирование, числсиные методы и комплексы программ

Автореферат

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

' у;:.: д. 3/5

^КИ ДОКУМЕНТОВ

Владивосток 2010

- 2 ДЕК 2010

004615067

Работа выполнена в лаборатории вероятностных методов и системного анализа Института прикладной математики ДВО РАН

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

профессор Цициашвили Гурами Шалвович

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

профессор Нурминский Евгений Алексеевич

доктор технических наук, доцент Головко Николай Иванович

Ведущая организация: Вычислительный центр ДВО РАН, г. Хабаровск

Защита состоится 10 декабря 2010 года в часов на заседании диссертационного совета Д 005.007.01 в Институте автоматики и процессов управления ДВО РАН по адресу: 690041, г. Владивосток, ул. Радио, 5.

С диссертацией можно ознакомиться в библиотеке Института автоматики и процессов управления ДВО РАН.

Автореферат разослан ноября 2010 года

Ученый секретарь

диссертационного совета Д 005.007.01, к.т.н. " А-В. Лебедев

Общая характеристика работы

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

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

Первые попытки определить вероятность работоспособности прямыми методами (Ушаков И.А., Barlow R., Proschan F., Рябипин И.А.) привели к большим объемам вычислений, сложность которых растет геометрически с ростом числа ребер. Поэтому изучение было сведено к рассмотрению специальных моделей случайных сетей и методов их исследования, для которых объемы вычислений можно было бы существенно сократить.

В частности, Ушаковым И.А., Barlow R.E.. Proschan F. были построены линейные по сложности алгоритмы вычисления надежности случайных сетей, состоящих из некоторого набора ребер, параллельно и последовательно соединенных. В работах Содоженцева Е.Д. для вычисления характеристик надежности использовалась логическая функция, построенная с помощью операций конъюнкции, дизъюнкции и отрицания.

Асимптотический подход к решению вопроса надежности стохастических сетей был реализован в работах Буртина и Питтеля. Они получили формулы для вероятности работоспособности сети с ребрами, имеющими одинаковую и малую вероятность отказа. В рамках этой же модели Герцбах И., Родионов A.C. прямое вычисление надежности спели к определению целочисленных коэффициентов некоторого многочлена.

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

з

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

Однако в последнее время появляются новые задачи, которые требуют развития методов моделирования случайных сетей. К их числу, например, относятся сети интернетовского типа (Ball М.О., Colbourn C.J.), которые строятся па базе древовидных соединений. Замена образующей сети радиального вида в древовидном соединении на радиально-кольцевую незначительно отражается па связи между вершинами, но существенно усложняет поиск характеристик надежности в отдельно взятой подсистеме. Добавление кольцевых ребер приводит к тому, что наличие связи между центром и вершипой на кольце, которая раньше характеризовалась надежностью одного ребра, теперь определяется через всевозможные соединения, что значительно усложняет вычисление надежности всей сети.

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

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

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

1. Построение асимптотических соотношений для надежности случайных сетей с оценкой точности.

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

3. Аналитическое и численное исследование надежности различных классов композиций случайных сетей.

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

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

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

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

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

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

Апробация результатов. Результаты диссертационной работы докладывались на двух Дальневосточных конференциях студентов и аспирантов по математическому моделированию (2007 г., 2009 г.), на четырех Дальневосточных математических школах-семинарах имени Е.В. Золотова (2007-2010 гг.), на семинарах ИПМ ДВО РАН (2010 г.), ВЦ ДВО РАН (2010 г.), ИАПУ ДВО РАН (2010 г.), на XXXVIII-XXXIX Российской школе (2008-2009 гг.), на 9-й международной конференции "Reliability and Statistics in Transportation and Communication" (2009 г.). публикации. По материалам диссертационной работы опубликовано 18 работ, в том числе 3 статьи в журналах из списка ВАК. Структура и объем работы. Диссертация состоит из введения, четырех глав, заключения и списка литературы из 107 наименований. Основное содержание изложено на 81 странице, включая 20 рисунков.

Содержание работы

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

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

В диссертационной работе в качестве модели случайной сети рассматривается неориентированный граф Г с конечным множеством вершин U, множеством ребер W и множество всех ацикличных путей 11 = {Ri,..., i?n} из начальной вершины и, в конечную v,. Обозначим a(w), w € W, независимые случайные величины, характеризующие работоспособность ребер. Наша задача заключается в вычислении вероятности работоспособности Рг = Р( и П (a(w) = 1) ) , т.е. вероятности существования

\ReKweR J

хотя бы одного работающего пути между вершинами и», v, и вероятности отказа Рг = 1 — Рг-

Интерес представляют два случая, когда вероятность работоспособности ребер графа pw близка к нулю (низконадежные элементы) и когда близка к единице (высокопадежные элементы). Будем полагать, что вероятность работоспособности pw = pw{h) и вероятность отказа Pw = PwW = 1 — Pw(h) есть функции от безразмерного малого параметра Л —» 0, имеющего произвольную природу.

В частности, для моделей времени жизни в условиях, когда время жизни t(w) отдельного ребра w 6 W подчиняется закону Вейбулла Pw(h) = P(t(w) > t) — exp(—t0) или закону Гомпертца, тогда Pw(h) = P(t(w) > t) = exp(—e®^), где ¡3 > 0. Параметр h имеет следующий смысл h = h(t) — 1/t или h(t) = е-', соответственно, в результате чего P(r(w) > t) = - ехр(—

Теорема 1. Если рш = pw(h) —» 0 при h О для w eW, то

ЯбЯшеЯ

где относительная погрешность полученного соотношения не превосходит nmaxpw(h) —> 0, h 0.

Обозначим множество всех разрезов С = {L{A), А £ Л} в графе Г, где А = {А с U, и, 6 A, vt £ A}, L = L(A) = {(и, v): и £ A, v £ А). Определим через L\ = {L\,..., Lm] совокупность минимальных по теоре-тико-мпожествеппому включению элементов из множества С.

Теорема 2. Если рш — pw(h) > 0 при h 0 для w 6 W, то

(2)

LeCi web

где относительная погрешность полученного соотношения не превосходит го тахрщШ -* 0, h —> 0.

■»nCllr

б

Рассмотрение случайных сетей с низкоиадежными и высоконадежными элементами о случаях степенной и экспоненциальной зависимости позволило получить ряд следствий. Обозначим через d(w),g(w) длину и пропускную способность ребра w соответственно.

Следствие 1.

1) Если pm{h) ~ hi{-w\ h 0, где d{w) >0, w 6 W, то

Я- ~ N(7Z)hDt:R\ Л 0, (3)

где N(TZ) - число путей длины D{TV} = min £ d(w).

ДеЯ-юе д

2) Если pw(h) ~ h—t 0 где g(w) > 0, weW, то

PT~N{£)hGU:\h->Q, (4)

где N(C) - число разрезов с пропускной способностью G(C) = min g(w).

LeC wei.

3) Если pw(h) ~ exp(-h-d(w]), h0 где d(w) > 0, w € W, то

- In Pc ~ Af(n)h~5{n\ h-> 0, (5)

где N(Tl) - минимальное количество ребер длины D(1Z) = min D(R) в путях минимальной псевдодлины D(R) = maxd(tu).

wdR

4) рш(Л) ~ ехр(-/Г«(ю)), /г ->■ 0, где з(ги) > 0, tu G VT, mo

-lnPr ~W(£)h-6(£), h->0, (6)

где M(C) - минимальное количество ребер с пропускной способностью G(C) = minG(L) в разрезах с минимальной псевдопропускной способностью G(L) = тахр(ги).

шб!>

Результат п.З следствия 1 удалось усилить в предположении, что для различных ребер w\w" значения d(w'),d(w") различны. Для этого пронумеруем ребра пути Rj: > «¿(и;*,) > ... > dfiu^.), где m* -число ребер в пути Ri. Обозначим Dl = (d(w\),..., d(w'rn)) и введем па множестве векторов {£)', 1 < i < п} отношение линейного порядка, т.е. Dv У £>?, если при k < mm(mP, m9) первые fc - 1 компонент у этих векторов совпадают, а fc-ая компонента у вектора Dp больше, чем у вектора D4. Без ограничения общности положим D1 У D2 У ...У Dn. Теорема 3. Если pw(h) - exp{-h~dM), h 0, где d{w) > 0, w £ W, то

Fr ~ exp

В условиях п. 3-4 следствия 1 была решена задача оптимального резервирования, которая свелась к определению узких мест графа. Под узкими местами понимается множество ребер графа, изменение надежности которых качественно изменяет надежность всего соединения. Обозначим

йд = {го € Я : <1{ги) = 5{Ъ)}, Ть = {ш е Ь : д(ю) = б(£)}.

Определение. Совокупности Б', Т минимальных по включению множеств из 5 = {ги б Б л, Я £ Л] иТ = {и) е Т^, Ь е £}, соответственно, называются узкими местами в графе Г.

Вместе с тем была поставлена и решена обратная задача. Были получены условия асимптотической инвариантности для всех соотношений следствия 1, т.е. условия, при которых надежность всей сети асимптотически не зависит от надежности того или иного ребра. Для этого определим граф путем исключения из графа Г ребра и> = (и,и'), а граф Гц путем склеивания в графе Г° вершин и, и'.

Утверждение 1. В условиях п.1 следствия 1 асимптотический параметр В (71.) соотношения (3) вычисляется по формуле

В(П) = тшин + П(П1), О«)], В{П1) < £«), где множества 72.® > для графов Г^, Г® понимаются в том же смысле, что и И для графа Г.

Следствие 2. (Условие инвариантности). Параметр £>(72.) не зависят от константы ¿(ю) тогда и только тогда, когда £?(72^) = .0(72®,).

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

Утверждения п. 3-4 следствия 1 были применены к моделям времени жизни.

Утверждение 2. Если Р(т(ю) > ~ ехр(-^(ю'), I -* оо, где ¿(ш) > О, щ£Йг, то

- 1п Р(т(Г) > ~ * -»• оо. (7)

Утверждение 3. ЕслиР(т(ю) > *) ~ ехр(-егад), I оо, где <1(ю) > О, го 6 Иг, то

- 1п Р(т(Г) > Ь) ~ Я{П) ехр(* 5{П)), 4 -> оо. (8)

Замечание 1. Сравнительный анализ построенных относительных погрешностей для соотношений (7), (8), показал, что асимптотическая сходимость для логарифма распределения Гомпертца значительно быстрее сходимости для логарифма распределения Вейбулла, что подтвердили результаты вычислительных экспериментов.

Во второй главе рассмотрен ряд моделей случайных сетей, которые по мнению Х.И. Черпе, H.A. Ушакова, И.А. Рябинина имеют практическую значимость. Речь идет о мостиковой схеме, о схеме трансформатора, о схеме двух "звезд", включенных на треугольник, о структурно-сложной схеме и радиально-кольцевой схеме общего вида. Отличительной особенностью этих схем, помимо того, что каждая реализована во многих технических устройствах, является то, что использование прямых методов вычисления для определения их надежности требует неоправданно большого количества операций в зависимости от количества элементов, содержащихся в соединении.

Для всех перечисленных соединений и их модификаций построены алгоритмы нахождения параметров асимптотических соотношений следствия 1. В качестве примера остановимся на мостиковой схеме (рис. 1).

Обозначим модель данного соединения через граф Г с множеством вершин U = {, Ч2,щ} и множеством ребер IV = {wy — (u0, «1), W2 — (щ,П2), Wz = (iti,u3), Wi = («2,u3), w5 = (tii,u2)}, вершина «о - начальная, а щ - конечная, ребро щ называется мостиком.

UJ

Рис. 1. Мостиковая схема Г.

Для определения вероятности работоспособности данного соединения, например, в условиях п. 1 следствия 1 получено

= ттЩи'ь) + Я«)],

О(П0щ) = тт(№,) + №2) + ¿Ы)), (9)

0(Пи = тт(сг(гу1),сг(ш2)) + ттп(<1(и)з), (1{гю4)).

Для рассматриваемой схемы было сформулировано условие инвариантности. Константа Б (Л) не зависит от ¿(и^), т.е. 0(К®ъ) = выполняется тогда и только тогда, когда выполняется одно из условий:

1) > ¿{и)з), (1{и>г) > ¿(11)1), 2) ¿(юз) > <*М, ¿(101) > (¿(ад2).

Полученные в этой части работы результаты позволяют построить быстрые и минимальные по числу арифметических операций алгоритмы

э

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

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

Рассмотрим параллельное соединение графов || Г2, полученное склеиванием начальных и конечных вершин графов Г^Гг, и последовательное соединение 1\ —> Г2, полученное склеиванием конечной вершины графа 1\ с начальной вершиной графа Гг. Остановимся на одном из результатов, полученных в следствии 1. Предположим, что параметры (¿(гу) для всех ребер в рассматриваемых соединениях различны.

Утверждение 4. Если - 1пР(а(П) = 1) ~ И,'0^, г = 1,2, при Ь. О,

то

- 1пРГ1-,г2 ~ Л-б<*г1-Ч

где.

5(ЯГ1-г,) = шах(5(^1), б(7г2)), б{Пгт) = тт(5(Я1),5(Яа)),

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

\ Ц, ЩЪ) > б(П2), ЮГ1-Г» \ п/2, го < 3(п2),

, / 5(Яг) < 6{П2),

П||Г* \ Ц, 5(4,) > 0(П2).

Здесь множества 7ч, Т^г^ь, ?2г1||г2> г — 1,2, для графов Г;, Г1 —► Г2, Г1 || Г2 понимаются в том же смысле, что и 71 для графа Г, а ребра и)[, и>'2, ю^цгз являются узкими местами в соответствующих

графах.

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

Помимо параллельно-последовательных соединений большой интерес в последнее время вызывают сети интернетовского типа. Речь идет о

ю

сетях, построенных приклеиванием радиально-кольцевой сети к единственной вершине построенной ранее сети (рис. 2).

'к

2 3

Рис. 2. Сеть интернетовского типа.

Пусть ТУ - совокупность двухполюсников Г'л ...,Г{ радиально-кольцевого вида с непересекающимися множествами ребер. Определим рекурсивно класс сетей V, ТУ с Т>, следующим образом. Пусть сети Г* £ £>, Г' £ ТУ имеют конечные множества вершин 1Т, V и непересекающиеся множества ребер IV, V/', Тогда сеть Г* и Г' (рис. 2), полученная склеиванием сетей Г*, Г' в единственной вершине г, также принадлежит классу V.

Вероятность работоспособности Рг между вершинами сети Г = Г*иГ' определяется следующим соотношением

Здесь РГ вероятность работоспособности сети Г* между вершинами и, г, а Рг' вероятность работоспособности сети Г' между вершинами г. и'.

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

(10)

Нт

2 п(Рг)

= 1

(И)

¡<гносг(Г)(/(г) -1)

п

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

Таким образом при ¿(Г) -» оо для вычисления вероятности работоспособности Рг в пересчете на одну пару вершин требуется одна операция.

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

Р01 = 0.0471595 Р02 = 0.0469944 ри = 0.0173955

роз = 0.0287418 Ро4 = 0.0499121 Р56 = 0.00818179

р05 = 0.0135117 Рое = 0.00822811 р45 = 0.0004677

р12 = 0.0490761 рзз = 0.0340865 Рз4 = 0.0442866

Целыо эксперимента было установление точности и быстродействия построенного алгоритма вычисления вероятности работоспособности по сравнению с методом Монте-Карло (число реализаций по методу Моите-Карло составило 10е).

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

0 0.001920 0.010164 0.001425 0.000054 0.006827 0.008561

0.001920 0 0.003351 0.024627 0.004263 0.020932 0.001718

0.010164 0.003351 0 0.002467 0.003994 0.014226 0.010637

0.001425 0.024627 0.002467 0 0.004049 0.020647 0.010964

0.000054 0.004263 0.003994 0.004049 0 0.017331 0.003379

0.006827 0-020932 0.014226 0.020647 0.017331 0 0.011170

0.008561 0.001718 0.010637 0.010964 0.003379 0.011170 0

Здесь а{^ - относительная погрешность вычисления вероятности работоспособности между вершинами г, 3. Как видно из приведенных результатов относительная погрешность не превысила 2.5%. В свою очередь, время счета па одном и том же оборудовании составило 14 часов для метода Монте-Карло и менее минуты для асимптотических соотношений.

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

Аналогичный вычислительный эксперимент был проведен для сетей с высоконадежными элементами в условиях теоремы 2. Время счета было сокращено в несколько тысяч раз, а погрешность не превысила 2 - 3%.

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

Приведем последний в качестве примера. Рассмотрим древовидное соединение Г, множество вершин U которого можно представить в виде непересекающихся подмножеств Uq,У],..., Um, причем множество I/o содержит единственную вершину щ, называемую далее начальной.

Все ребра графа Г представимы в виде (щ.и/), 1 < г < j < тп, щ G Uit Uj € Uj, и любая его вершина достижима из начальной вершины щ. Константы D(u),G(u),D(u), для начальной вершины щ и конечной вершины и, будем понимать в том же смысле, что и D(7Z), G(£), D(TL). Алгоритм определения D(u),G(u),D(u).

Зададим c(w) > О, we W, положим D(u) = G(u) = D(u) = с(щ,«), ru — (uo,u), и e U\.

Шаг 1. Определим множества S(u) = {v : (v, tiJe^nE Uk-i, u € Uk}, 1 <k<m.

Шаг 2. Вычислим D(u), G(u), D(u) для и £ Uk, 1 < к < m, по формулам:

D(u) = min max(c(D,u),Z?(i;)), G(u) = max miu(c(v, u), G(v)), (12) reS(u) veS(u)

D(u) = min (c(v, и) + D(v)). (13)

veS(u)

В свою очередь, критические ребра для параметра D(u) определим из соотношения

{rv, если D(u) — max(D(v),c(v,u)) > c(v,u), (u,u), если D(u) = max(D(v),c(v,u)) > D(v),

а критические ребра параметра G(u) из соотношения

_ f rv, если G(u) = min(G(v),c(v,u)) < c(v:u), " I (v, u), если G(u) = min(G(?;), c(u,u)) < G(v).

(14)

Замечание 2. Если при фиксированной вершине и б U искать с помощью алгоритма только D(u), G(u), D(u), то попутно находятся значения D{v), G(v), D(v) для всех вершин v, из которых вершина и достижима.

Из формул (12), (13) следует, что для вычисления каждого из значений D(u), G(u), D{u), и е U, требуется 2N(S(u)) - 1 арифметических операций, причем это число нельзя уменьшить, т.е. алгоритм является оптимальным.

Основные результаты работы

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

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

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

4. Разработаны аналоги известных алгоритмов Дейкстра и Флойда для поиска узких мест и вычисления параметров асимптотических соотношений. Построек новый оптимальный алгоритм поиска минимальной и псевдоминималыюй длины пути, псевдоминималыюй пропускной способности разреза для класса древовидных соединений.

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

Публикации по теме диссертации

1. Лосев, A.C. Поиск слабого звена в графе со случайными ребрами / A.C. Лосев // Тезисы докладов. Дальневосточная конференция студентов, аспирантов и молодых ученых по математическому моделированию. Владивосток: Дальнаука. - 2007. - С. 47-48.

2. Лосев, A.C. Поиск узких мест в графе со случайными ребрами / A.C. Лосев /7 Тезисы докладов. XXXII Дальневосточная математическая школа-семинар имени академика Е.В. Золотова. Владивосток: Изд-во Дальнаука. - 2007. - С. 26-27.

3. Цициашвили, Г.Ш. Узкие места в логической системе с ненадежными элементами / Г.Ш. Цициашвили, A.C. Лосев // Обозрение прикладной и промышленной математики. - 2007. - Т. 14. - Вып. 5. - С. 950-951.

4. Tsitsiashvili, G.Sh. Fast algorithms of asymptotic analysis of networks with unreliabe edges / G.Sh. Tsitsiashvili, A.S. Loscv // Reliability and Risk Analysis: Theory к Application. - 2008. - Vol.1. - № 1. - P. 58-63.

5. Лосев, А.С. Асимптотический анализ надежности стохастических сетей / А.С. Лосев // Информатика и системы управления. - 2008. - №4(18). -С. 101-105.

6. Лосев, А.С. Пропускная способность в рекурсивно определимых двухполюсниках (на примере мостиковой схемы) / А.С. Лосев // Тезисы докладов. XXXIII Дальневосточная математическая школа-семинар имени академика Е.В. Золотова. - Владивосток: Изд-во Дальнаука. - 2008. -С. 7!Ь80.

7. Лосев, А. С. Асимптотический анализ мостиковых структур с ненадежными ааементами / А.С. Лосев // Наука и технологиии. Труды XXXVIII Российской школы. - М.:РАН. - 2008. - Т.2. - С. 85-92.

8. Цициашвили, Г.Ш. Применение алгоритма Флойда к асимптотическому анализу сетей с ненадежными ребрами / Г.Ш. Цициашвили, А.С. Лосев // Автоматика и телемеханика. - 2008. - Вып. 7. - С. 181-184.

9. Tsitsiashvili, G.Sh. An asymptotic analysis of a reliability of internet type networks / G.Sh. Tsitsiashvili, A.S. Losev // Reliability and Risk Analysis: Theory к Application. - 2009. - Vol. 2. - № 3. - P. 25-29.

10. Tsitsiashvili, G.Sh. An accuracy of asymptotic formulas in calculations of a random network reliability / G.Sh. Tsitsiashvili, A.S. Losev // Reliability and Risk Analysis: Theory к Application. - 2009. - Vol. 2. - № 3. - P. 58-63.

11. Tsitsiashvili, G.Sh. Asymptotic Analysis of Disconnection Probabilities in Random Networks with High Reliable Arcs / G.Sh. Tsitsiashvili, A.S. Losev // Proceedings of the 9th International Conference "Reliability and Statistics in Transportation and Communication", Riga, Latvia. - 2009. - P. 97-101.

12. Лосев, А.С. Погрешность асимптотических формул в моделях времени жизни / А.С. Лосев // Тезисы докладов XXXIV Дальневосточная математическая школа-семинар имени академика Е.В. Золотова "Фундаментальные проблемы математики и информационных наук". -Хабаровск: Изд-во ТОГУ. - 2009. - С. 100.

13. Лосев, А.С. Численные исследования асимптотических формул для надежности монотонных структур / А.С. Лосев // Наука и технологии. Краткие сообщения XXIX Российской шкапы, посвященной 85-летию со дня рождения академика В.П. Макеева. - Екатеринбург: УрО РАН. -2009. - С. 207-209.

14. Лосев, А.С. Асимптотические формулы надежности сети / А.С. Лосев // Наука и технологии. Итоги диссертационных исследований. Избранные труды Российской школы. - М.-.РАН. - 2009. - Т. 1. - С. 351-359.

15. Лосев, А.С. Асимптотические формулы надежности сетей интернетовского типа / А.С. Лосев /7 Дальневосточная конференция студентов,

аспирантов и молодых ученых по теоретической и прикладной математике: материалы конференции. - Владивосток: Изд-во Дальпевост. ун-та. - 2009. - С. 59.

16. Tsitsiashvih, G. Sh. Calculation of connectivity probability in recursively defined random networks / G.Sh. Tsitsiashvili, A.S. Losev // Reliability: Theory and Applications. - 2010. - Vol. 1(16). - .V> 1. - P. 40-46.

17. Лосев, А. С. Вычисление вероятности связности рекурсивно определимых случайных сетей / А.С. Лосев, Г.Ш. Цициашвили // Дальневосточный математический журнал. - 2010. - Т. 1. - № 1. - С. 60-66.

18. Лосев, А.С. Вычисление вероятности работоспособности случайных сетей / А.С. Лосев // Сборник докладов. XXXV Дальневосточная математическая школа-семинар имени академика Е.В. Золотова. -Владивосток: ИАПУ ДВО РАН. - 2010. - С. 298-301.

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

В работах, выполненных в соавторстве [3,4,8-11,16,17] автор внес следующий вклад: участие в построении и выборе рассматриваемых моделей, построение и тестирование вычислительных алгоритмов, проведение практического обоснования и прикладной интерпретации полученных результатов.

Лосев Александр Сергеевич

Быстрые алгоритмы вычисления надежности случайных сетей

Автореферат

диссертации иа соискание ученой степени кандидата физико-математических наук по специальности 05.13.18 - Математическое моделирование, численные методы и комплексы программ

Подписпо в печать 14.10.10. Формат 60x90/16. Бумага офсетная. Печ. л. 1.75 Тираж 100 экз. Заказ 127. Издательство УГПИ. 692508, г. Уссурийск, ул. Некрасова, 25.

Отпечатано типографией Уссурийского государственного педагогического института 692508, г. Уссурийск, ул. Некрасова, 25.

Введение

1 Асимптотический анализ надежности случайных сетей

1.1 Основные обозначения.

1.2 Соотношения для вероятности работы и отказа сети.

1.2.1 Низконадежные соединения.

1.2.2 Высоконадежные соединения.

1.2.3 Оценка относительной погрешности.

1.3 Соотношения для логарифма надежности сети.

1.3.1 Узкие места.

1.3.2 Оценка относительной погрешности.

1.4 Инвариантность асимптотических параметров.

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

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

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

Один из интенсивно развивающихся подходов для изучения моделей сложных систем в теории надежности и безопасности является логико-вероятностный. Он нашел отражение во многих работах по теории надежности (см., например, [15], [21], [33], [34], [46], [55]) и является основным методом расчета надежности в технической области (см., например, [10], [25], [46], [56], [67], [68]). Сочетание булевой алгебры и элементов теории вероятности позволяют точно вычислить надежность системы путем составления таблицы истинности и, как результат функции работоспособности в виде совокупности дизъюнктивно нормальных форм. Однако, размерность таблицы истинности (2П строк, где п - число элементов сети) напрямую зависит от числа элементов сети. Удваиваясь каждый раз при добавлении нового элемента сети, она увеличивает количество необходимых операций и усложняет тем самым функцию работоспособности. Конечно, логико-вероятностный подход позволяет, с одной стороны, точно вычислить надежность сложного соединения и проанализировать влияние отдельного элемента на надежность всего соединения, но с другой стороны, очевидна громоздкость и "неповоротливость" данного метода. Любое изменение числа элементов приводит не просто к увеличению числа операций, а ещё и к изменению самой функции работоспособности всей сети, тем самым, возвращая исследователя на первоначальный этап изучения структуры и составления дизъюнктивно нормальной формы. Ещё одним из недостатков данного метода является тот факт, что степенная зависимость количества операций от числа элементов (2П) заставляет накладывать ограничения на надежность элементов сети, предполагая, что они равны, тем самым хоть как-то уменьшая время счета. Данное ограничение очень сильно сужает возможности применения логико-вероятностного метода, делая его мало востребованным на практике.

Помимо логико-вероятностного подхода метод прямого перебора, аналитически-статистический метод, метод поглощения степеней и метод моделирования накопления отказов элементов до отказа системы ([2], [18], [52], [71], [72], [76]) тоже требуют либо сложнейших аналитических выводов, либо большого числа арифметических операций, а зачастую и того, и другого. Данный факт обусловлен тем, что вычисления надежности перечисленными методами сводится к ЫР-полиой задаче, это делает их громоздкими и плохо приспособленными к применению на практике. Естественным образом возникает необходимость в разработке новых, минимальных по числу арифметических операций методов изучения надежности.

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

Рассмотрение надежности конкретных соединений осложняется тем, что с течением времени надежность как отдельных элементов, так и всего соединения изменяется и не является величиной постоянной. В этом случае возникает вопрос о построении распределения времени жизни соединения, который наравне с вопросом надежности, не решен до конца, и требует дальнейшего изучения. Разработано много подходов и методов к построению распределений времени жизни систем, от построения линейных моделей сетей на основе распределений Вейбулла [77] и до рассмотрения многомерных стареющих функций, которые определяются в терминах кривых уровня соответствующей функции выживания [96], [97]. Однако, большинство предлагаемых методов в силу своей громоздкости или большого числа допущений (предположений) просто не применимы для рассмотрении конкретных соединений.

Особый интерес в последнее время вызывает распределение Гомпертца (см., например, [17], [37]), которое нашло свое применении в геронтологии и современных проблемах и методах исследования продолжительности жизни, в частности, в методах статистики экстремальных значений. Идея данного метода проста и очевидна [37]: разрушение (отказ) сети может наступить в результате поражения самых разных её подсистем. Поэтому есть основания для поиска предельных распределений наименьших значений времен жизни огромного числа элементов. В результате построенные модели приводят к распределению Гомпертца, с одной существенной поправкой: исходное состояние организма не считается идеальным (лишенным дефектов), а, наоборот, характеризуется огромным числом дефектов. Этой небольшой поправки достаточно, чтобы из простейших схем разрушения систем вместо распределения Вейбулла получить распределение Гомпертца. Именно за счет близости к реальным системам и чувствительности к внешним воздействиям при описании их времени жизни распределение Гомперта вызывает такой интерес и является неотъемлемым инструментом для решения задач теории надежности сложных систем.

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

В ходе технического развития возникают все новые и новые аспекты проблемы обеспечения надежности, которые требуют разработок принципиально новых методов расчёта надежности. Так, авторы работ [63], [64], [70] предлагают новый обобщенный логико-вероятностный метод, уделяя большое внимание автоматизации всех этапов изучения надежности: от постановки задачи до расчетного этапа. Однако, предлагаемый метод требует ручного вмешательства при описании логической функции системы, которое заключается в декомпозиции соединения (разложение сети на простейшие параллельные и последовательные соединения) или эквивалентного преобразования соединения "треугольник" в соединение "звезда" и обратно [24], что делает идею полной автоматизации недостижимой.

В диссертационной работе рассматривается класс сетей специального вида, изучаемых в свое время различными авторами ([2], [3], [14],[51],[83]), среди которых особое место занимают информационные сети интернетовского типа. Отличительной особенностью таких систем является то, что они не сводятся к параллельно-последовательным соединениям, поэтому требуется большое количество арифметических операций для точного вычисления их надежности. Использование асимптотического подхода позволил обойти эти недостатки и получить прозрачные формулы, которые могут быть использованы при составлении программных комплексов по вычислению надежности рассмотренных сетей.

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

Надежность рекурсивно определимых сетей изучалась в работах [4, 29]. В них параллельно-последовательные соединения строились из независимо работающих двухполюсников, соединением их в определенных вершинах. В работе [69] в рамках логико-вероятностного подхода [83] введен класс дизъюнктивных нормальных форм логических функций от независимых случайных аргументов, принимающих значения 0,1, который может быть рассмотрен как рекурсивно определимый класс. Для вычисления надежности системы, характеризуемой логическим выражением А (т.е. вероятности события (А = 1)) требуется число арифметических операций, равное числу пар скобок в представлении А. Для рекурсивно определимых сетей, состоящих из ребер с одинаковой надежностью и описывающих различные физические системы, разработаны методы вычисления надежности, основанные на нахождении всех корней многочлена высокой степени и имеющие полиномиальную сложность [95], [98]. При этом метод Монте-Карло используемый при вычислении коэффициентов многочлена приводил к целочисленной погрешности.

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

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

В частности, при рассмотрении известного рекурсивно определимого класса сетей интернетовского типа [43], образующими которых являются ради-алыю-кольцевые соединения, было доказано, что при числе вершин /(Г) —оо для вычисления надежности в пересчете на одну пару вершин требуется одна операция. Однако, при вычислении надежности соединений образующих данного класса, традиционными методами, количество операций растет с геометрической скоростью. Это вызвало интерес авторов и послужило основанием для проведения вычислительного эксперимента с использованием полученных асимптотических формул для вычисления надежности соединений образующих данной сети. В результате вычислительного эксперимента особое внимание уделялось следующим вопросам: время счета и точность результата. Решение данных вопросов позволило сделать вывод о качестве разработанного метода.

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

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

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

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

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

Заключение

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

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

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

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

Построены классы рекурсивно определимых сетей, склеиванием сетей в вершинах, заменой ребер одной сети подобной ей сетью. Для этих классов разработаны минимальные по числу арифметических операций и достаточно прозрачные алгоритмы вычисления ' надежности, длины (псевдодлины) кратчайшего пути, минимальной пропускной и псевдопропускной способности разреза. Для класса параллельно-последовательных соединений построены реккурентные алгоритмы определения узких мест, качественно влияющих на надежность всего соединения. Для класса рекурсивно определимых сетей интернетовского типа, с радиально-кольцевыми соединениями в качестве образующих, проведен вычислительный эксперимент по вычислению вероятность связи между любыми двумя вершинами. Предложенный алгоритм позволил сократить время счета в 1000 раз по сравнению с методом Монте-Карло, а полученная оценка относительной погрешности не превосходит 2.5%.

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

Основными результатами работы являются следующие положения:

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

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

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

4. Разработаны аналоги известных алгоритмов Дейкстра и Флойда для поиска узких мест и вычисления параметров асимптотических соотношений. Построен новый оптимальный алгоритм поиска минимальной и псевдоминимальной длины пути, псевдоминимальной пропускной способности разреза для класса древовидных соединений.

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

1. Davis, K.L. Reliability: management, methods and mayhematics / K.L. Davis, L. Myron - Prentice-Hall, 1.c. Englewood Cliffs, New Jersey, 1962.

2. Берэю, К. Теория графов и её применения / К. Берж // Под редакцией И.А. Вайнштейна. М.: Изд-во ин. лит-ры, 1962. - 320 с.

3. Черне, Х.И. Индуктивные связи и трансформации в электрических фильтрах / Х.И. Черне М.: Гос. изд-во литературы по вопросам связи и радио, 1962. - 315 с.

4. Barlow, R.E. Mathematical Theory of Reliability / R.E. Barlow, F. Proschan- London and New York, Wiley, 1965. 256 p.

5. Гнеденко, Б.В. Математические методы в теории надежности / Б.В. Гнеденко, Ю.Б. Беляев М., 1965. - 524 с.

6. Вентцелъ, Е.С. Теория вероятностей / Е.С. Вентцель М.: Наука, 1969.- 576 с.

7. Гнеденко, В.В. Элементарное введение в теорию вероятностей / Б.В. Гнеденко, Л.Я. Хннчнн Главная редакция физико-математической литературы изд-ва "Наука", - 1970. - 168 с.

8. Полесский, В. П. Об одной нижней границе надежности информационных сетей / В.П. Полесский // Проблемы передачи информации. 1971. - Т. 7. - № 2. - С. 88-96.

9. Полесский, В.П. Верхняя граница надежности информационных сетей / В.П. Полесский, М.В. Ломоносов / / Проблемы передачи информации. -1971. Т. 7. - № 4. - С. 78-81.

10. Рябинин, И. А. Основы теории и расчёта надёжности судовых электроэнергетических систем / И.А. Рябинин Изд. 2-е. - JL: Судостроение, 1971. - 456 с.

11. Полесский, В.П. Нижняя оценка надежности сетей / В.П. Полесский, М.В. Ломоносов // Проблемы передачи информации. 1972. - Т. 8. -№ 2. - С. 47-53.

12. Floid, R.W. An adaptive algorithm for spatial greyscale / R.W. Floid, L. Steinberg SID 75 Digest. - 1975. - P. 36-37.

13. Козлов, Б.А. Справочник по расчёту надёжности аппаратуры радиоэлектроники и автоматики / Б.А. Козлов, H.A. Ушаков М.: Советское радио, 1975. - 472 с.

14. Белое, В.В. Теория графов. Учебное пособие для втузов / В.В. Белов, Е.М. Воробьев, В.Е. Шаталов М.: Высшая школа, 1976. - 391 с.

15. Дружинин, Г.В. Надежность автоматизироованных систем / Г.В. Дружинин 3-е изд. перераб. и доп. - М.: "Энергия", 1977. - 536 с.

16. Полушкин, В.А. О понятии "старение информации"/ В.А. Полушкин // НТК. Сер. 2. 1977. - № 4. - С. 10-11.

17. Гаерилов, Л.А. Математическая модель старения животных / Л.А. Гаврилов // Докл. АН СССР. 1978. - С. 64-105.

18. Кристофидес, Н. Теория графов. Алгоритмический подход / Н. Кристофидес М.: Мир. - 1978. - 432 с.

19. Kelly, P.P. Reversibility and Stochastic Networks / F.P. Kelly Johi Wiley & Sons. - 1979. - 233 p.

20. Штойян, Д. Качественные свойства и оценки стохастических моделей / Д. Штойян Москва: Мир, 1979. - 268 с.

21. Рябинин, И.А. Логико-вероятностные методы исследования надёжности структурно-сложных систем / И.А. Рябинин, Г.Н. Черкесов М.: Радио и связь, 1981. - 264 с.

22. Левин, В.И. Бесконечнозначная логика в задачах кибернетики / В.И. Левин М.: Радио и связь, 1982. - 176 с.

23. Коваленко, И.Н. Случайные процессы / И.Н. Коваленко, Н.Ю. Кузнецов, В.М. Шуренков Киев, 1983. - 366 с.

24. Диллон, Б. Инженерные методы обеспечения надёжности систем / Б. Диллон, Ч. Селигх; пер. с англ. М.: Мир, 1984. - 320 с.

25. Дудник, Д.Я. Надежность и живучесть систем связи / Д.Я. Дудник и др. М.:Радио и связь, 1984. - 220 с.

26. Феллер, В. Введение в теорию вероятностей и ее приложения / В. Феллер- М.:Мир, 1984. Т. 1. - 528 с.

27. Феллер, В. Введение в теорию вероятностей и ее приложения / В. Феллер- М.:Мир, 1984. Т. 2. - 752 с.

28. Bail, F. Deterministic and stochastic épidémies with several kinds of susceptibles / F. Bail Adv. Appl. Probab. - 1985. - № 17. - P. 1-22.

29. Надежность технических систем: Справочник / Под редакцией И.А. Ушакова. Москва: Радио и связь, 1985. - 608 с.

30. Розанов, Ю.А. Теория вероятностей, случайные процессы и математическая статистика / Ю.А. Розанов М: Наука, 1985. - 318 с.

31. Боровков, А.А. Теория вероятностей / А.А. Боровков Москва: Наука, 1986. - 431 с.

32. Gertsbakh, I.B. Statistical Reliability Theory / I.B. Gertsbakh, Marcel Dekker, 1988.

33. Можаев, A.С. Общий логико-вероятностный метод анализа надежности сложных систем / А.С. Можаев JL: ВМА, 1988. - 68 с.

34. Райншке, К. Оценка надежности систем с использованием графов / К. Райншке, И.А. Ушаков М.: Радио и связь, 1988. - 224 с.

35. Полесский,, В.П. Оценки вероятности связности случайного графа / В.П. Полесский // Проблемы передачи информации. 1990. - Т. 26.1. С. 90-98.

36. Shier, D.R. Network Reliability and Algebraic Structures / D.R. Shier -• Oxford, 1991. P. 72-83.

37. Гаврилов, H.A. Биология продолжительности жизни / H.A. Гаврилов, H.C. Гаврилова // Отв. ред. В.П. Скулачев. М.: Наука, 1991. - 280 с.

38. Abate, J. The Fourier-series method for inverting transforms of probability distributions / J. Abate, W.Whitt Queueing Systems, 1992. - № 10. -P. 5-81.

39. Полесский, В.П. Нижние оценки вероятности связности в классах случайных графов, порожденных двусвязными графами с заданным базовым спектром / В.П. Полесский // Проблемы передачи информации. -1992. Т. 28. № 2. - С. 86-95.

40. Когге, Ю.К. Основы надежности авиационной техники / Ю.К. Когге, Р.А. Майский // Учебник для студентов авиационных техником. -М.: Машиностроени, 1993. 176 с.

41. Полесский, В.П. Нижние оценки вероятности связности для некоторых классов случайных графов / В.П. Полесский // Проблемы передачи информации. 1993. - Т. 29. - № 2. - С. 85-95.

42. Ишвин, В. В. Статистические задачи оценивания надежности в моделях "нагрузка-прочность" в случаях гамма-распределений и распределений Вейбулла / В.В. Ишвин // Математическое моделилирование систем и процессов. 1994. - №2(2). -С. 43-49.

43. Ball, М. О.Network Reliability. In Network Models / M.O. Ball, C.J. Colbourn, J.S. Provan // Handbook of Operations Research and Management Science. 1995. - Vol. 7. - P. 673-762.

44. Harms D.D. Network reliability: Experiments with a Sym-bolic Algebra Environment / D.D. Harms, M. KraezI, C.J. Colbourn, J.S. Devitt CRC Press. Inc. - 1995.

45. Asmussen, S. Ruin Probability / S.Asmussen // World Scientific, Singapore.- 1997. 388 p.

46. Рябинин, И.А. Надежность, живучесть и безопасность корабельных электроэнергетических систем / И.А. Рябинин, Ю.М. Парфенов -Л.: ВМА. 1997. - 276 с.

47. Dohmen, К. Inclusion-Exclusion and Network Reliability / К. Dohmen // Humboldt-Universitet on Berlin Institut for Informatik. Germany 1998. -P. 1-8.

48. Донцов, В. И. Сущностные модели старения и продолжительности жизни / В.И. Донцов, В.Н. Крутьк // Профилактика старения. Вып 1. - 1998.- С. 50-58.

49. Ковалёв, А.П. О преобразовании "звезда-треугольник"в расчётах надёжности сложных по структуре схем, элементы которых могут находиться в трёх состояниях / А.П. Ковалёв, А.В. Спиваковский // Электричество.- 1998. № 10.

50. Daby, D.J. Epidemic Modelling / D.J. Daby, J. Gani Cambridge University.- 1999. P. 203.

51. Dohmen, K. Improved inclusion-exclusion identities and inequalities based on particular class of abstract tubes / K. Dohmen // Electronic Journal of Probability. 1999. - Vol. 4. - № 5. - P. 1-12.

52. Носов, В.А. Комбинаторика и теория графов / В.А. Носов // Московский гос. институт электроники и математики (Технический университет). -Москва, 1999. 112 с.

53. Соловьев, А.Е. Надежность и безопасность АС / А.Е. Соловьев, В.Ю. Каминский СПб.: Изд-во СПбГТУ, 1999.

54. Алексеев, В.Б. Элементы теории графов, схем и автоматов (учебное пособие для студентов) / В.Б. Алексеев, С.А. Ложкин М.: Издат. отдел ф-та ВМиК МГУ (лицензия ЛР N 040777 от 23.07.1996), 2000. - 58 с.

55. Ковалёв, А. П. Применение логико-вероятностных методов для оценки надёжности структурно-сложных систем / А.П. Ковалёв,

56. A.B. Спиваковский // Электричество. 2000. - №9. - С. 66-70.

57. Рябипин, H.A. Надежность и безопасность структурно-сложных систем. / И.А. Рябинин СПб.: Политехника. - 2000. - 248 с.

58. Кривулец, В.Г. Квазиупаковочные оценки арактеристик надежности сетей / В.Г. Кривулец, В.П. Полесский // Информационные процессы. -2001. Т. 1,- № 2. - С. 126-146.

59. Кривулец, В.Г. Об оценках надежности монотонной структуры /

60. B.Г. Кривулец, В.П. Полесский // Проблемы передачи информации. -2001. Т. 37.- С. 4.

61. Rocchi, P. Entropy in Reliability Theory / P. Rocclii // Entropy. 2002. -V. 4.- P. 142-150.

62. Арапов, A.A. Теория организации и системный анализ / A.A. Арапов -М. Московский государственный университет экономики, статистики и информатики, 2002. 74 с.

63. Краснов, О. В. Безопасность эксплуатации сложных технических систем // О.В. Краснов СПб., ВИСУ им. Можайского, 2002.

64. Матвеевский, В.Р. Надежность технических систем / В.Р. Матвеевский // Учебное пособие: Московский государственный институт электроники и математики. М., 2002. - 113 с.

65. Бурдонов, И.Б. Неизбыточный алгоритмы обхода ориентированных графов. Детерминированный случай / И.Б. Бурдонов, A.C. Косачев, В.В. Кулямин // Программирование. 2003. - N2 5. - С. 59-69.

66. Ветошкин, А.Г. Надежность технических систем и техногенный риск /

67. A.Г. Ветошкин Пенза: Изд-во ПГУАиС, 2003. - 154 с.

68. Мельников, В.А. Развитие методов оценки надежности для структурно-сложных систем, состоящих из элементов со многими состояниями /

69. B.А. Мельников // АиТ. 2003. - № 7.

70. Рябинин, И.А. Логико-вероятностное исчисление как аппарат исследования надлежности и безопасности структурно-сложных систем / И.А. Рябинин // АиТ. 2003. - № 7.

71. Соложенцев, Е.Д. Особенности логико-вероятностной теории риска с группами несовместных событий / Е.Д. Соложенцев // Автоматика и телемеханика. 2003. - № 7. - С. 187-203.

72. Ершов, Г.А. Оценка безопасности атомных энергетических объектов на стадии проектирования / РА. Ершов, Ю.И. Козлов, A.C. Солодовников,

73. A.C. Можаев // Тяжелое машиностроение. 2004. - № 8. - С. 33-39.

74. Киселёв, В.Ю. Теория графов. (Высшая математика. Третий семестр) /

75. B.Ю. Киселёв, Т.Ф. Калугин. Иван. гос. энерг. ун-т. Иваново, 2004.

76. Кормен, Т. Алгоритмы: построение и анализ / Т. Кормен, Ч. Лейзерсон, Р. Ривест Москва: Лаборатория Базовых Знаний, 2004. - 955 с.

77. JIooickuh, С.А. Лекции по основам кибернетики (учебное пособие для студентов) / С.А. Ложкин - М.: Издательский отдел ф-та ВМиК МГУ,2004. 253 с.

78. Rocchi, P. The Notion of Reversibility and Irreversibility at the Base of the Reliability Theory / P. Rocchi // Proc. Int. Symp. Stochastic Models in Reliability, Safety, Security and Logistics. Beer Sheva, 2005. - P. 287-291.

79. Гнеденко, Б.В. Курс теории вероятностей: Учебник / Б.В. Гнеденко -Изд. 8-е. М.: Едиториал УРСС, 2005. - 448 с.

80. Позняков, С.Н. Компьютерная математика: Учеб. псобие / С.Н. Позняков, С.В. Рыбин СПб.: Изд-во СПбГЭТУ "ЛЭТИ",2005. 64 с.

81. Rocchi, P. Calculations of system aging through the stochastic entropy / P. Rocchi // Entropy. 2006. - № 8. - P. 134-142.

82. Ярошенко, А.В. Развитие учения о формальной теории / А.В. Ярошенко // Отчет о научно-исследовательской работе № 36106. Санкт-Петербург, 2006. - 44 с.

83. Tsitsiashvili, G.Sh. Asymptotic Analysis of Logical Systems with Anreliable Elements / G.Sh. Tsitsiashvili // Reliability: Theory and Applications. -2007. Vol. 2. - № 1. - P. 34-37.

84. Tsitsiashvili, G.Sh. Narrow places in logical systems with anreliable elements / G.Sh. Tsitsiashvili // Reliability: Theory and Applications. 2007. - Vol. 2. - № 2. - P. 43-46.

85. Лосев, А.С. Поиск слабого звена в графе со случайными ребрами / А.С. Лосев // Тезисы докладов Дальневосточная конференция студентов, аспирантов и молодых ученых по математическому моделированию. Владивосток: Дальнаука. 2007. - С. 47-48.

86. Лосев, А.С. Поиск узких мест в графе со случайными ребрами / А.С. Лосев // Тезисы докладов. XXXII Дальневосточная математическая школа-семинар имени академика Е.В. Золотова. Владивосток: Изд-во Дальнаука. 2007. - С. 26-27.

87. Рлбинин, И. А. Надежность и безопасность структурно-сложных систем / И.А. Рябинин СПб.: изд-во С.-Петерб. ун-та, 2007. - 276 с.

88. Серебровский, А.Н. Методы оценки вероятности отказов в процессах прогнозирования техногенных чрезвычайных происшествиях /

89. A.Н. Серебровский // Математические машины и системы. 2007. - №2. - С. 111-116.

90. Цициашвили, Г.Ш. Узкие места в логической системе с ненадежными элементами / Г.Ш. Цициашвили, А.С. Лосев // Обозрение прикладной и промышленной математики. 2007. - Т. 14. - Вып. 5. - С. 950-951.

91. Цициашвили, ГШ. Алгебраические методы моделирования стохастических сетей: Монография / Г.Ш. Цициашвили, М.А. Осипова -Владивосток: Дальнаука, 2007. 132 с.

92. Tsitsiashvili, G.Sh. Bottlenecks in general type logical systems with unreliable elements / G.Sh. Tsitsiashvili // Reliability and Risk Analysis: Theory and Application. 2008. - Vol.1. - № 1. - P. 64-68.

93. Tsitsiashvili, G.Sh. Fast algorithms of asymptotic analysis of networks with unreliabe edges / G.Sh. Tsitsiashvili, A.S. Losev // Reliability and Risk Analysis: Theory & Application. 2008. - Vol.1. - № 1. - P. 58-63.

94. Костеев, B.B. Надежность технических систем и управление риском /

95. B.В. Костеев // Учебное пособие. М.:МИФИ, 2008 - 280 с.

96. Лосев, А. С. Асимптотический анализ надежности стохастических сетей / А.С. Лосев // Информатика и системы управления. 2008. - №4(18).1. C. 101-105.

97. Лосев, А. С. Асимптотический анализ мостиковой структуры с ненадежными элементами / А.С. Лосев // Наука и технологиии. Тезисы докладов XXXVIII Российской школы. Миасс: МСНТ. - 2008. - С. 91.

98. Лосев, А.С. Асимптотический анализ мостиковых структур с ненадежными элементами / А.С. Лосев // Наука и технологиии. Труды XXXVIII Российской школы. М.:РАН. - 2008. - Т.2. - С. 85-92.

99. Цициашвили, Г.Ш. Применение алгоритма Флойда к асимптотическому анализу сетей с ненадежными ребрами / Г.Ш. Цициашвили, А.С. Лосев // Автоматика и телемеханика. 2008. - Вып. 7. - С. 181-184.

100. Dimitrov, B. Age, Interpretations. Control and Applications / B. Dimitrov //VI International Conference Extended Abstracts. Mathematical Methods in Reliability Theory. Methods, Applications. MMR 2009. - P. 10.

101. Fabio, L.S. Relations between dependence and ageing for exchangeable survival models / L.S. Fabio // VI International Conference Extended Abstracts. Mathematical Methods in Reliability Theory. Methods, Applications. MMR 2009. - P. 8.

102. Tsitsiashvili, G.Sh. An asymptotic analysis of a reliability of internet type networks / G.Sh. Tsitsiashvili, A.S. Losev // Reliability and Risk Analysis: Theory & Application. 2009. - Vol. 2. - № 3. - P. 25-29.

103. Tsitsiashvili, G.Sh. An accuracy of asymptotic formulas in calculations ofa random network reliability / G.Sh. Tsitsiashvili, A.S. Losev // Reliability and Risk Analysis: Theory & Application. 2009. - Vol. 2. - № 3. - P. 58-63.

104. Лосев, А.С. Асимптотические формулы надежности сети / А.С. Лосев // Наука и технологии. Итоги диссертационных исследований. Избранные труды Российской школы. М.:РАН. - 2009. - Т. 1. -С. 351-359.

105. Tsitsiashvili, G.Sh. Calculation of connectivity probability in recursively defined random networks / G.Sh. Tsitsiashvili, A.S. Losev // Reliability: Theory and Applications. 2010. - Vol. 1(16). - № 1. - P. 40-46.

106. Лосев, A.C. Вычисление вероятности связности рекурсивно определимых случайных сетей / A.C. Лосев, Г.Ш. Цициашвили /./ Дальневосточный математический журнал. 2010. - Т. 1. - N® 1. -С. 60-66.Щ