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

Введение

Предмет исследования.

Цель диссертационной работы.

Методы исследования.11

Обзор литературы.11

Структура и объем диссертации.13

Краткое описание результатов диссертации.13

Теоретическая и практическая ценность работы.15

Аппробация, благодарности.16

1 О теории надежности монотонных систем 18

1.1 Математическая модель надежности монотонных систем . 18

1.1.1 Монотонная система. Минимальные пути и минимальные разрезы . .18

1.1.2 Случайная монотонная система и ее надежность . 21

1.2 Методы вычисления надежности монотонных систем .24

1.2.1 Перебор состояний.24

1.2.2 Перебор минимальных путей или минимальных разрезов 24

1.2.3 Метод непересекающихся произведений.26

1.2.4 Факторизационный метод.29

1.3 Оценки надежности монотонных систем.30

1.3.1 Общие замечания.30

1.3.2 Оценки включения-исключения.32

1.3.3 Упаковочные оценки.32

1.3.4 Развязочные оценки.33

1.4 Выводы.38

2 Построение новых оценок. Разностно-развязочные оценки надежности монотонных систем 39

2.1 Формула надежности в терминах непересекающихся произведений .39

2.2 Разностно-развязочные оценки.42

2.3 Разностно-развязочно-упаковочные оценки.46

2.3.1 Теоретическое сравнение с оценками Оксли - Уэлша для случайной изотропной монотонной системы.46

2.3.2 Достижимость.48

2.4 Эффективно вычислимые квазиупаковочные оценки надежности монотонных систем.51

2.5 Пример. Сравнение оценок на мостиковой структуре .54

2.6 Выводы.60

3 Эффективно вычислимые оценки надежности информационных сетей 62

3.1 Математическая модель надежности информационных сетей . 62

3.2 О связи характеристик надежности неориентированных и ориентированных сетей.63

3.3 Вычислительная сложность проблем анализа характеристик надежности информационных сетей .66

3.4 Квазиупаковочные оценки терминальной надежности информационных сетей.68

3.5 Квазиупаковочные оценки вероятности связности информационных сетей.71

3.6 Квазиупаковочные оценки двухполюсной надежности информационных сетей.73

3.7 Выводы.80

4 Численное исследование оценок надежности монотонных систем 82

4.1 Общие замечания.82

4.2 Структура и описание алгоритмов и программных модулей . . 83

4.3 Результаты тестирования для различных видов монотонных систем.87

4.4 Выводы.102

Заключение 103

Приложение 105

Список литературы 130

Акты о внедрении 139

Список сокращений мс - монотонная система

ТКБ - теорема о клаттерной бифуркации

РРУ - разностно-развязочно-упаковочные (оценки)

РРА - разностно-развязочно-антиблокирующие (оценки)

РР2 - разностно-развязочные (оценки) второго порядка

У - упаковочные (оценки)

РУ - развязочно-упаковочные (оценки)

РА - развязочно-антиблокирующие (оценки)

ОУ - (оценки) Оксли - Уэлша

ЭП - (оценки) Эзари - Прошана

Введение

Б.В.Гнеденко так характеризует в [4] теорию надежности: "Общая научная дисциплина, изучающая методы и приемы, которых следует придерживаться при проектировании, изготовлении и эксплуатации изделий для обеспечения максимальной эффективности в процессе использования, а также разрабатывающая общие методы расчета качеств устройств по известным качествам соответствующих их частей называется теорией надежности".

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

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

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

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

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

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

Готовность используется в контексте систем поддающихся ремонту. В этом случае состояние компоненты чередуется между работоспособным и отказавшим (и подвергающимся ремонту). Готовность (состояние устойчивости) компоненты определяется как предел вероятности того, что компонента работает во время t при t —> оо. Если поведение компоненты подчиняется предположениям чередующегося процесса восстановления (см. [35]), то готовность равна среднему времени отказа, деленному на сумму средних времен отказа и восстановления.

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

В случае произвольных внешних разрушающих воздействий (т.е. не предусмотренных условиями нормальной экскплуатации) вместо надежности (reliability) говорят об уязвимости (vulnerability) или живучести сети [86]. Меры живучести могут совпадать с мерами надежности, но вероятности р(е) определяются специальными моделями взаимодействия.

В [16, Гл.4 Терминология. Общие понятия и эффективность, стр.168], говорится: "Живучесть - способность системы сопрягать свойства, необходимые для выполнения требуемых функций, при наличии воздействий, не предусмотренных условиями нормальной эксплуатации".

В [13] говорится, что "В случае появления произвольных разрушающих воздействий говорят о "уязвимости" или о "живучести" информационных систем . Под "живучестью" информационных систем можно понимать способность информационных систем поддерживать определенный уровень обслуживания при ухудшении показателей работоспособности ее компонент на некоторую величину". В [13] рассматривается также и детерминированная модель надежности/живучести, отсылая к вероятностным моделям к [6]. В [86] в качестве мер уязвимости рассматривается реберная связность сети, или двухполюсная реберная связность (см. также [37]).

Случайная монотонная система - одна из простейших моделей надежности составных технических систем, в частности, сетей передачи информации.

В этой модели предполагается, что работоспособность системы определяется исключительно знанием того, какие компоненты работают (отказали).

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

Термин "монотонная" объясняется тем, что система не перестает быть работоспособной, когда какие-либо отказавшие ее компоненты заменяются на исправные (восстанавливаются), или что то же самое, если монотонная система не исправна, и какие-либо ее компоненты ее отказывают, то она остается неисправной.

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

Особое место среди них занимают оценки надежности монотонной системы общего вида (с произвольным клаттером и произвольной надежностью компонент).

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

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

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

Предмет исследования

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

Цель диссертационной работы

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

- анализ известных оценок надежности монотонных систем общего вида;

- построение новых, эффективно вычислимых, оценок надежности монотонных систем общего вида и сравнение их с существующими оценками этого типа;

- построение новых, эффективно вычислимых, оценок характеристик надежности сетевых систем;

- разработка алгоритмов и программных модулей, для исследования оценок надежности монотонных систем общего вида;

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

Актуальность темы

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

1. Монотонная система общего вида является весьма распространенным объектом. Легко убедиться в том, что не любой клаттер является клат-тером сети. Например, уже клаттер {{1, 2}, {2, 3}, {3,4}} не является клаттером двухполюсных путей или разрезов в сети. Это - простейший пример (к — 2, п = 3) так называемой последовательной системы "к из п", состоящей из п компонент 1, 2,., п и исправной тогда и только тогда, когда исправны все элементы какого либо набора из следующего семейства наборов

1, 2, {2,3, .,& + 1},., {п — & + 1,., п}}.

Эта, и более общие монотонные системы, не являются системой сетевого типа.

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

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

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

Установлено, что точное вычисление каждой характеристики надежности сети - $Р-полная проблема (понятие jjP-полноты и ее связь с NP-полнотой см. например, в [50]. Качественно fjP-полные проблемы есть проблемы подсчета, связанные с iVP-полными задачами, например, это проблема подсчета числа гамильтоновых циклов. Такие задачи по меньшей мере также трудны, как TVP-полные задачи, т.к. знание числа решений проблемы распознавания легко решает вопрос существования).

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

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

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

Обзор литературы

Простая, но очень общая, модель надежности есть случайная монотонная система.

Теория надежности таких систем началась с работы Ф.Мура и К.Шенонна [63] (русский перевод [14]). В ней получены некоторые результаты, касающиеся надежности двухполюсной сети, состоящей из независимых и равнона-дежных компонент - реле (случай, когда все элементы равнонадежны называют изотропным).

В 61-м году В.Бирнбаум, Д.Эзари, С.Саундерс в [38] обобщили результаты Ф.Мура и К.Шенонна на то, что они назвали когерентной системой. Сейчас вместо термина "когерентная" используется термин "монотонная".

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

Анализу надежности сетей с рекурентной структурой посвящены работы В.А.Гадасина и И.А.Ушакова [3,26]. Отражение широкого спектра проблем надежности нашло в справочнике "Надежность технических систем", английское издание которого вышло под названием "Handbook of Reliability Engineering" (под ред. И.А.Ушакова) в 1994 г. [17].

С 79-го года надежность монотонной системы стала изучаться в теории перколяции под названием "вероятность клаттерной перколяции". Ок-сли, Уэлш, МакДиармид получили некоторые результаты, см. [69,70,61,62]. В частности, Оксли и Уэлш получили нижнюю оценку надежности монотонной системы для изотропного случая.

Введенное в 97-м году В.П.Полесским в [21] (и получившее обобщение в [22]) преобразование развязывания клаттеров и его теорема о клаттерной бифуркации позволила получить серию новых ("развязочно-антиблокирующих") оценок и дать общие принципы построения развязочных оценок в дальнейшем.

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

В настоящий момент проблемам структурной надежности посвящено значительное число работ (см. например [23,15,5,27,25]). Среди отечественных, отметим работы Б.В.Гнеденко, А.Д.Соловьева, И.Г.Коваленко, Г.А.Маргули-са, В.П.Полесского, В.Е.Степанова, А.К.Кельманса, М.В.Ломоносова, В.А.Гадасина, И.А.Ушакова, В.А.Богатырева, Б.П.Филина. Среди зарубежных, отметим работы Р.Барлоу, Ф.Прошана, С.Росса, Дж.Оксли, Д.Уэлша, К.МакДи-армида, Ч.Калберна, Р.Вуда, Д.Шира, Б.Болобаша, Д.Каргера, А.Сатинара-яна и др.

Структура и объем диссертации

Диссертация состоит из введения, четырех глав, заключения, изложенных на 141 странице, содержит 16 рисунков, 8 таблиц и списка цитируемой литературы из 98 наименований.

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

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

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

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

4. Разработаны программные модули для основных методов оценивания монотонных систем общего вида; приведены примеры работы алгоритмов и программ.

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

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

Заключение

1. Вероятность и математическая статистика. Большая Русская Энциклопедия. Москва, 1999, стр. 345-346.

2. Богатырёв В.А. К расчёту надёжности сети связи по совокупности путей. Электросвязь, 1981, № 2, стр. 42-44.

3. Гадасин В.А., Ушаков И.А. Надежность сложных информационно-управляющих систем. М.: Сов. Радио, 1975.

4. Гнеденко Б.В., Беляев Ю.К., Соловьев А.Д. Математические методы в теории надежности. М.: Наука, 1965.

5. Давыдов Г.Б., Рогинский В.Н., Толчан А.Я. Сети электросвязи. М.: Связь, 1978.

6. Дудник Б.Я., Орлов В.К., Филин Б.П., Холин А.В., Шурмин А.В. Надёжность и живучесть систем связи, М.: Радио и связь, 1984.

7. Кельманс А.К., Ломоносов М.В., Полесский В.П. О минимальных покрытиях в матроиде. Проблемы передачи информации, 1976, том 29, № 4, стр. 58-66.

8. Кельманс А.К., Полесский В.П. Экстремальные множества и задачи покрытия и упаковки в матроидах. В кн.: Исследования по прикладной теории графов, Новосибирск: Наука, Сиб. отд., 1986, стр. 140-188.

9. Кривулец В.Г. Разностно-развязочные оценки надежности монотонной структуры. XLIV научная конференция МФТИ, посвященная 50-летию создания МФТИ, Сб. трудов, часть I. Москва-Долгопрудный, 2001, стр. 17.

10. Кривулец В.Г., Полесский В.П. Об оценках надежности монотонной структуры. Проблемы передачи информации, 2001, том 37, № 4, стр. 112-129.

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

12. Малашенко Ю.Е., Рогожин B.C., Ферапонтов Е.В. Живучесть сетевых систем. Препринт ВЦ АН СССР, М. 1989.

13. Мур Э.Ф., Шеннон К.Э. Надежные схемы из ненадежных реле. Киб.Сб. 1960. № 1. Изд-во Иностр. Лит-ры. Москва, стр. 109-148.

14. Мизин И.А., Кулешов А.П., Богатырёв В.А. Сети коммутации пакетов. М.: Радио и связь, 1986.

15. Надежность и эффективность в технике. Справочник в десяти томах (под ред. Б.В.Гнеденко). М., Машиностроение, 1987, том 2.

16. Надежность технических систем: справочник. Под ред. И.А. Ушакова. М.: Радио и связь, 1985. (английский перевод: Handbook of Reliability Engineering. New-York: John Wiley Sons. Inc., 1994.)

17. Полесский В.П. Об одном способе построения структурно-надежной сети. В кн.: Дискретные автоматы и сети связи. М.: Наука, 1970, стр. 13-19.

18. Полесский В.П. Оценки вероятности связности случайного графа. Проблемы Передачи Информации, 1990, том 26, Я2 1, стр. 90-98.

19. Полесский В.П. Достижимые границы вероятности полного ранга случайного подматроида. Проблемы передачи информации, 1995, том 31, № 4, стр. 81-99.

20. Полесский В.П. Развязывания клаттеров, корреляционные неравенства и границы комбинаторной надежности. Проблемы передачи информации, 1997, том 33, № 3, стр. 50-70.

21. Полесский В.П. Развязывание носителей семейства клаттеров и его роль в теории надежности. Проблемы передачи информации, 2001, •том 37, № 2. стр. 62-76.

22. Самойленко С.Н., Давыдов А.А., Золатарев В.В., Третьякова Е.И. Вычислительные сети (адаптивность, помехоустойчивость, надежность). М.: Наука, 1981.

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

24. Рогинский В.Н., Богатырёв В.А. К расчёту структурной надёжности связей в сети. Процессы и устройства управления в сетях связи. М.: Наука, 1982.

25. Ушаков И.А., Гадасин В.А. Анализ надежности структурно-сложных систем. М.: Знание, 1979.

26. Филин Б.П. Методы анализа структурной надёжности сетей связи. М.: Радио и связь, 1988.

27. Ball М.О., Provan J.S. Computing k-Terminal Reliability in Time Polynomial in the Number of (s,t)-Quasicuts. Fourth Army Conference on Applied Mathemathics and Computing. Washington: Army Research Office, pp. 901-907.

28. Ball M.O., Van Slyke R.M. Backtracking algorithms for network reliability analysis. Annals of Discrete Mathematics, 1977, vol. 1, pp. 49-64.

29. Ball M.O., Nemhauser G.L. Matroids and reliability analysis. Math. Operations Res. 1979, vol. 4, no. 2, pp. 132-143.

30. Ball M.O. Computing Network Reliability. Operations Research, 1979, vol. 27, no. 4, pp. 823-838.

31. Ball M.O., Provsn J.S. The complexity of counting cuts and of computing the probability that a graph is connected. SIAM J. Computing, 1983, vol. 12, pp. 777-788.

32. Ball M.O., Colbourn C.J., Provan J.S. Network Reliability. In: Handbooks in OR and MS. Chapter 11. New York: Elsevier, 1995,

33. Barlow R.E., Proschan F. Mathematical Theory of Reliability. New York: Wiley, 1965. (русский перевод: Барлоу P., Прошан Ф. Математическая теория надежности. М.: Сов.радио, 1969.)

34. Barlow R.E., Proschan F. Statistical Theory of Reliability and Life Testing, to Begin With. Md: Silver Spring. 1981. (русский перевод: Барлоу P., Прошан Ф. Статистическая теория надежности и испытания на безотказность. М.: Наука, 1984.)

35. Barlow R.E. Mathematical Theory of Reliability: A Historical Perspective. IEEE Transaction on Reliability, 1984, vol. 33, no. 1, pp. 16-20.

36. Beineke L.W. Exploration into graph vulnerability. Technical Report. Dept. of Math. Sciences, Indiana Univ. Purdue Univ. 1990.

37. Birnbaum Z.W., Esary J.D., Saunders S.C. Multicomponent Systems and Structures and Their Reliability. Technometrics, 1961, no. 1, pp. 55-77.

38. Brecht Т.К., Colbourn C.J. Lower Bounds for Two-Terminal Network Reliability. Discr. Appl. Math, 1988, vol. 21, pp. 185-198.

39. Colbourn C.J. The Combinatorics of Network Reliability. Oxford: Oxford Univ. Press, 1987.

40. Colbourn С. J. Edge-Packings of Graphs and Network Reliability. Discrete Mathematics, 1988, vol. 72, pp. 49-61.

41. Colbourn C.J., Nel L.D. Using and Abusing for Network Reliability. Proc. IEEE Telecommunications Conference Globecom90, IEEE Press, 1990, pp. 663-667.

42. Chernyak A.A., Chernyak Zh.A. Note on complexity of Comuting Domination of Binary Systems. Discrete Applied Math, 1997, vol. 73, no. 3, pp. 289-295.

43. Dotson W.P., Gobien J.O. A new analysis technique for probabilistic graphs. IEEE Trans. Circuits and Systems, 1979, vol. CAS-26, no. 10, pp. 855-865.

44. Edmonds J., Fulkerson D.R. Bottleneck extrema. J. Combinatorial Theory, 1970, vol. 8, pp. 299-306.

45. Edmonds J. Submodular Functions, Matroids and Certain Polyhedral. In: Combinatorial Stuctures and Their Applications. New York: Gordon and Breach, 1970, pp. 69-81.

46. Edmonds J. Edge-Disjoint Branching. In: Combinatorial Algorithms. Algo-rithmics Press, 1972, pp. 91-96.

47. Esary J., Proschan F. Coherent Structures of Non-Identical Components. Technometrics, 1963, vol. 5, no. 2, pp. 191-209.

48. Fratta L., Montanari U.G. A Boolean algebra method for computing the terminal reliability in a communication network. IEEE Transactions on Circuit Theory, 1973, vol. CT-20, pp. 203-211.

49. Garey M.R., Johnson D.S. Computers and Intractability: A Guide to the Theory of NP-Completeness. San-Francisco: W.H.Freeman, 1979. (русский перевод: Гэри M., Джонсон Д. Вычислительные машины и трудноре-шаемые задачи. М.: Мир, 1982.)

50. Grimmett G.R. Percolation Theory. Second edition. A Series of Comprehensive Studies in Math. Berlin: Springer, 1999.

51. Hansler E., McAuliffe G.K., Wilkov R.S. Exact calculation of computer network reliability. Networks, 19974, vol. 4, pp. 85-112.

52. Huseby A.B. Domination Theory and Crapo b-Invariant. Networks, 1989, vol. 19, pp. 135-149.

53. Huseby A.B. On reguality, amenability and optimal factoring strategies for reliability computations. Preprint, Univ. of Oslo.

54. Jensen P.A., Bellmore M. An algorithm to determine the reliability of a complex system. IEEE Transactions on Reliability, 1969, vol. R-18, pp. 169-174.

55. Karger D.R. A Randomized Fully Polynomial Time Approximation Scheme for the All Terminal Network Reliability Problem. Proceedings of the 37th Annual Symposium on the Foundations of Computer Science, 1996, pp. 113.

56. Katona G. A theorem of finite sets. In: Theory of graphs. Budapest: Akademia Kiado, 1966, pp. 187-207.

57. Krivoulets V.G., Polesskii V.P. What is the theory of bounds for network reliability ? Information Processes, 2001, vol. 1, no. 2, pp. 199-203.

58. Krivoulets V.G., Polesskii V.P. Monotone structures. The best possible bounds of their reliability. Information Processes, 2001, vol. 1, no. 2, pp. 188-198.

59. Kruskal J.B. The number of simplices in a complex.Mathematical Optimization Techniques, California: University of California Press, 1963, pp. 251— 278.

60. McDiarmid C. Clutter Percolation and Random Graphs. Mathematical Programming Study, 1980, vol. 13, pp. 17-25.

61. McDiarmid C. General Percolation and Random Graphs. Adv. Appl. Prob, 1981, vol. 13, pp. 40-60.

62. Moore E.F., Shannon C.E. Reliable circuits using less reliable relays, J.Franklin Inst., 1956, pp. 262, no. 3, pp. 191-208; no. 4, pp. 281-297.

63. Moskowitz F. The analysis of redundancy networks. IEEE Trans. Com-mun. Electron. 1958, vol. 39, pp. 627-632.

64. Moran S. An Improvement of an Algorithm for Construction of Edge-Disjoint Branching. Technical Report, Haita, 1984.

65. Mine H. Reliability of physical systems. IRE Trans. Circuit Theory, 1959, vol. CT-6, pp. 138-151.

66. Nel L.D., Strayer N.J. Two-Terminal Reliability Bounds Based on Edge-Packing by Cutsets. J. Comb. Math. Comb. Comut., 1993, vol. 13, pp. 3-22.

67. Nelsen A.C., Baths J.R., Beaadles R.L. A computer program for approximation system reliability. IEEE Transactions on Reliability, 1970, vol. R-19, pp. 61-65.

68. Oxley J.G., Welsh D.J.A. On Some Percolation Results of J.M. Hammers-ley. J. Appl. Prob., 1979, vol. 16, pp. 527-540.

69. Oxley J.G., Welsh D.J.A. The Tutte Polynomial and Percolation. Graph Theory and Related Topics, 1979, pp. 329-339.

70. Polesskii V.P., Krivoulets V.G. Efficiently computable bounds on stochastic monotone binary system reliability. Proceedings of 3d conferences on Mathematical Methods in Reliability. Trondheim, Norway, 2002, to appear.

71. Provan J.S., Ball M.O. Computing Networks Reliability in Polynomial Time in the Number of Cuts. Operation Research, 1984, no. 32, pp. 516526.

72. Provan J.S. Polyhedral combinatorics and network reliability. Math. Oper. Res., 1986, vol. 11, no. 3, pp. 36-61.

73. Rai S. A cutset approach to reliability evaluation in communication networks. IEEE Transactions on Reliability, 1982, vol. R-31, pp. 428-431.

74. Ramanathan A., Colbourn C.J. Bounds of All-Terminal Reliability via Arc-Packing. Ars Combinatorica, 1987, vol. 23A, pp. 91-94.

75. Raman V. Finding the Best Edge-Packing for Two-Terminal Reliability is NP-hard. J. Comb. Math. Comb. Comput., 1991, vol. 9, pp. 91-96.

76. Reliability of computer and communication networks. Proc. of the DIMACS Workshop on Reliability at Rutgers University, 1989, AMS Publication.

77. Resende L.I.P. A program for reliability evaluation of underected networks via polygon-to-chain reductions. IEEE Transactions on Reliability, 1986, vol. R-35, pp. 24-29.

78. Resende L.I.P. Implementation of a factoring algorithm for reliability evaluation of undirected networks. Annals of Discrete Mathematics, 1988, vol. 33, pp. 261-273.

79. Ross S.M. Introduction to probability models. New York: Academic Press Inc., 1985.

80. Satyanarayama A., Prabhaker A. New Topological Formula and Rapid Algorithm for Reliability Analysis of Comlex Networks. IEEE Trans, on Reliability, 1978, vol. 27, pp. 82-100.

81. Satyanarayana A., Hagstrom J.N. A new algorithm for the reliability analysis of multi-terminal networks. IEEE Transactions on Reliability, 1982, vol. R-30, pp. 325-334.

82. Satyanarayana A., Hagstrom J.N. Combinatorial properties of directed graphs useful in computing reliability. Networks, 1981, no. 11, pp. 357-366.

83. Satyanarayana A. A unified formula for analysis of some network reliability problems. IEEE Transactions on Reliability, 1982, vol. R-31, pp. 23-32.

84. Satyanarayana A., Chang M.K. Network Reliability and the Factoring Theorem. Networks, 1983, no. 13, pp. 107-20.

85. Shier D.R. Network Reliability and Algebraic Structures. Oxford: Claredon Press, 1991.

86. Материалы диссертации вошли в отчет по первому этапу НИР.

87. Зам. директора ИПИ РАН д.ф.-м.н.1. С.Я. Шоргин

88. Научный руководитель НИР гл. научн. сотр., д.ф.-м.н., проф1. А.В. Печинкин1. АКТ

89. Центрального научно-исследовательского института связи Министерства связи РФ о внедрении научных результатов Кривульца Виктора Григорьевича

90. В данной НИР для оценки устойчивости ВСС РФ были использованы методы анализа устойчивости сетей связи.

91. Начальник лаборатории ЦНИИ ^ Н.А.Аверин

92. С Н С лаборатории ЦНИИС —Л.И.Борисов