А.М. Андреев, Г.П. Можаров
8
щее время ее принято называть надежностью системы множеств,
комбинаторной надежностью или даже полиномом надежности [3],
так как это есть полином от надежностей ее элементов. В случае оди-
наковой надежности элементов мы имеем полином от одной пере-
менной [5, 10].
Надежность системы множеств полностью определяется надеж-
ностью системы (подсистемы) ее минимальных по включению мно-
жеств. Такие множества не вложимы друг в друга. Как известно, си-
стему множеств со свойством невложимости друг в друга называют
клаттером [3]. Поэтому надежность системы множеств называют
перколяционной вероятностью случайного клаттера [10–12].
Пусть программное обеспечение
должно реализовать множе-
ство операций
, причем
1
, ...,
M
P P
– семейство подмно-
жеств множества
(необязательно непересекающихся и различ-
ных). Назовем каждое
i
P
из
программным модулем (ПМ). При
выполнении условия Ф. Холла [9, 10] существует система различных
представителей (трансверсаль) семейства
, т. е. такое
,
p
p M
, что при некоторой нумерации
1
, ...,
M
O O
его эле-
ментов
i
i
O P
. Если
O p
и
P
имеют одинаковый индекс, мы
скажем, что
O
есть представитель
:
P O P
.
Известно [6, 9, 10], что множество всех трансверсалей системы
ПМ
порождает на множестве
матроид
M
как совокупность
всех его баз. Определим в
случайное подмножество
,
такое,
что события
независимы и имеют заданные вероятности.
Пусть
,
R q
– вероятность того, что
содержит трансверсаль
(где
q
– заданная вероятность отказа ребра случайного графа). Верх-
няя оценка надежности ПО может быть вычислена из следующего
выражения
1
,
1
,
i
r
C
i
R M q
q
где при каждом
1, ...,
i
M
множество коциклов
1
, ...,
M
C C
порождено базой
p
[3, 5].
Пусть
1
, ...,
M
p P P
– фиксированная трансверсаль,
i
i
P
и
1
, ...,
M
C C
– семейство коциклов
M
, порожденное ба-
зой
p
. Коциклы
k
C
можно охарактеризовать как множество всех
