Примеры сетевых топологий


Элементарные свойства систем с большим числом состояний - часть 2


Работоспособность сети PERT: Если обрыв связи соответствует Te=0, а рабочее состояние связи соответствует Te=1 и каждый путь в G имеет идентичную длину n, тогда Rel2(G,s,t,p)=Pr[ФPERT=n].

Отсюда следует, что эти проблемы являются #P-полными для любого класса графа, для которого ассоциированная проблема надежности (s,t)-связности является #P-полной. (сюда входят и проблемы, которые удовлетворяют дополнительным требованиям соответствия PERT). Аналогичные рассуждения показывают, что вычисление E[Ф] является также #P-полным для этих классов графов.

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

· свертка двух независимых случайных переменных Х1 и Х2, т.е. распределение их суммы Х1 + Х2;

· max (min) двух независимых случайных переменных Х1 и Х2, т.е. распределение max(Х1,Х2) или min(Х1,Х2).

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

1. Вычисление данного значения интегральной функции распределения cdf (cumulative distribution function) элемента в фиксированном классе должно допускать расчет за полиномиальное время с нужным числом значащих цифр при заданной точности входного описания распределения.

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




Начало  Назад  Вперед



Книжный магазин