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


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


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

Обычно предполагается, что случайные величины имеют дискретное распределение, то есть, могут иметь конечное число значений. Хотя вычисление одной свертки или распределения min/max является элементарным, вычисление распределения для серии k таких операций считается #P-полным, даже если каждая исходная переменная имеет только два значения. Что необходимо, чтобы гарантировать эффективное вычисление свертки и min/max распределения, так это то, чтобы случайные переменные принимали последовательные значения {1, 2,…, xq} (или в более общем случае последовательные значения, кратные некоторому общему знаменателю) для всех ребер графа, для некоторого фиксированного q.

Существует два класса распределений с бесконечным числом состояний, которые относятся к наиболее известным и удовлетворяют сформулированным выше требованиям (1-3). Первое является дискретным и может быть описано как смесь геометрических распределений, имеющих форму pdf(probability distribution function)

x=0,1,…

для 0 < p < 1 и при соответствующем выборе значений aij. Существует также класс непрерывных распределений, которые имеют нужные свойства. Эти распределения могут быть описаны как “смесь Эрланговых” распределений (известных также как Coxian-распределения). Они являются аналогом “смеси геометрических” распределений, описанных выше. Они имеют форму cdf (cumulative distribution function):

0 Ј t < Ґ

при соответствующем выборе aij.

Дадим краткое описание методик основных оценок и ограничений для сетей с большим числом состояний. В большинстве случаев оказывается, что одна и та же техника используется для двух или более упомянутых выше проблем. Большинство методик имеют варианты для двоичных версий, которые представлены в разделах 3 и 4. Таким образом, мы организовали обсуждения методики, а не предмета, и следуем, когда возможно, формату для двоичной версии проблемы.Для большей части обсуждения мы концентрируемся на расчете Pr[Фіa] для конкретного системного значения функции Ф и специфической величины a.




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



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