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


Введение к сложности анализа надежности - часть 2


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

Многие практические приложения требуют использования моделей с разной надежностью компонентов. В таких моделях все вероятности являются рациональными числами. Мы формулируем проблему анализа рациональной надежности следующим образом. В качестве входной информации используется представление и для каждого компонента i пара целых чисел ai, bi. На выходе получается пара целых чисел a и b таких, что a/b = Rel(SBS,{ai/bi}).

Мы начинаем с установления того, что, если конкретный анализ функциональной надежности является NP-сложными, тогда соответствующий анализ рациональной надежности является NP-сложными.

Утверждение 2.2. Для любой задачи анализа рациональной надежности r-Rel и соответствующей ей задачи анализа функциональной надежности, f-Rel за полиномиальное время может быть сведена к r-Rel.

Доказательство: В f-Rel входит представление функции SBS. На выходе необходимо получить набор коэффициентов {Fi} полинома надежности. Чтобы преобразовать f-Rel в r-Rel выберем m+1 рациональное значение вероятности 0 < p0 < p1 < ... < pm < 1. Для j= 0,1,…,m обозначим решения соответствующей задачи анализа рациональной надежности как rj = Rel(SBS,pj), где все компоненты надежности установлены равными pj. Теперь мы можем записать систему уравнений:

для j = 0,1,…,m.

Решив m+1 задачу анализа рациональной надежности, найдем pj и rj. Получим систему из m+1 линейного уравнения с m+1 неизвестными Fi.


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



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