Главная  Полное построение алгоритма 

[0] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15] [16] [17] [18] [19] [20] [21] [22] [23] [24] [25] [ 26 ] [27] [28] [29] [30] [31] [32] [33] [34] [35] [36] [37] [38] [39] [40] [41] [42] [43] [44] [45] [46] [47] [48] [49] [50] [51] [52] [53] [54] [55] [56] [57] [58] [59] [60] [61] [62] [63] [64] [65] [66] [67] [68] [69] [70] [71] [72] [73] [74] [75] [76] [77] [78] [79] [80] [81] [82] [83] [84] [85] [86] [87] [88] [89] [90] [91] [92] [93] [94] [95] [96] [97] [98] [99] [100] [101] [102] [103] [104] [105] [106] [107] [108] [109] [110] [111] [112] [113] [114] [115] [116] [117]

вероятностями и частотной интерпретацией конечного результата. Если система работает в более тяжелом режиме и состояниям Sj,, . . . .,., S32 соответствуют большие вероятности, чем состояниям Si, ..., sg, то теория предскажет меньшие шансы на успех.

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

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

2. Присваивание вероятностей. Присвойте вероятности элементам S. Это присваивание должно согласовываться с аксиомами I, П и HI. Пространство S должно состоять из конечного числа несовместных и в совокупности исчерпывающих элементов. Поэтому вероятности должны быть присвоены элементам S таким образом, чтобы сумма всех присвоенных значений равнялась 1. (Почему сумма должна быть равна 1?)

3. Идентификация событий реиления. Переведите искомое решение на язык событий из S.

4. Вычисление искомых вероятностей. Используя правила вычисления (аксиомы I, П и П1 и другие правила из упражнений), подсчитайте искомые вероятности.

Хотя вывод большинства формул для подсчета вероятностей оставляется в качестве упражнений, есть одно настолько важное правило, что мы должны обсудить его очень подробно. Оно известно как формула условной вероятности. Пусть Е и F - два события, определенные в пространстве S, и пусть Р{Е) и Р (F) - вероятности, соответствующие этим событиям. Пусть P{E\F) обозначает вероятность события Е при условии, что произошло событие F. Как правило, Р{Е)фР(Е\Р). Как только мы знаем, что событие F произошло, вычисление вероятности Е зависит уже не от всего пространства S; теперь нам нужно рассматривать только те элементы S, которые обусловливают выполнение события F. Все это учитывается автоматически в формуле

P{E]F)= (имеет смысл, только когда Р{Р)ФО).

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

) Более формально, множество подмножеств А±, ... , А„в S состоит из несовместных и в совокупности исчерпывающих подмножеств, если Ai(]Aj=e для всех

1ф}, и и



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

Е = событие, состоящее в том, что нам удается загрузка, т. е. что

свободны три или более трех процессоров; F = событие, состоящее в том, что процессор 1 занят.

Если событие F произошло, то мы знаем, что система должна находиться в одном из следующих 16 состояний: s, - Sio, Sai - s, Sss - «32. Каждое из этих 16 состояний по-прежнему равновероятно; иначе говоря, у нас нет оснований предпочесть какое-то одно состояние всем остальным. Поэтому вероятность того, что предстоящее испытание будет иметь некоторый конкретный исход из этого множества,

равна 1/16,- т. е. P{Si\F)- для i=2, 7-10, 21-26 и 28-32. В этом

ограниченном пространстве исходы Ss, s„ Sp, Sg и Sio означают появление события Е. Следовательно, по аксиоме III

P{E\F) = P{s,\F) + P{s,\F) + P(s,\F) + P(s,\F) + PiSio\F) = -.

Чтобы воспользоваться формулой условной вероятности, рассматриваем полное пространство S. Тогда

E = {Si, Sj, ..., Si,};

Р~{2у 7~ioy «2i «2C> *2в зг}? ЕПР = {$2, s„ S3, Sg, Sio};

P(£nF) = P(s,) + P(s,) + P(s,) + P(Sg) + P(Si„) (аксиома III) = J;

P{F)=P (S,) + P (S,) +...+P (S,„) + P (S,i) +...+P (Se) -f

+ P(s,8)+...+P(s32) (аксиома П1) = ;

и (Crj p(f) -1616

A что, если появление события F никак не связано с ожидаемым появлением £? Тогда

Р{Е) = Р{Е\Р). Но Р(Е\Р) = -Ш

поэтому PiE)==jWl, или Р(ЕПР)==.Р{Е)Р{Р).

Если события Е hF таковы, что вероятность их совместного появления



равна произведению вероятностей их раздельного появления, то говорят, что эти события независимы. Эта формула легко обобщается на случай трех или более взаимно независимых событий, т. е. если множества Ai, . . . , Л„ таковы, что

P(AinAj)=P(Ai)-P(Aj) для любых ij, то PiAiHA.n. . .nArd=P{Ai)P{A,). . .Р(Л„).

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

X == число свободных процессоров

сообщает нам все, что мы хотим знать в нашем мультипроцессорном эксперименте. Искомая конечная вероятность может быть выражена как Р (ХЗ) и равна вероятности того, что значение X больше или равно 3. Обратите внимание на то, что X в действительности является функцией, область определения которой есть пространство 5, а область значений - множество {О, 1, 2, 3, 4, 5}. Любая такая функция из пространства (и определенной на нем вероятностной меры) задачи на множество действительных чисел называется случайной переменной. Фактически все серьезные вычисления вероятностей выполняются в терминах случайных переменных.

Определение вероятностей на области значений случайной переменной называется распределением. В нашем мультипроцессорном примере, предполагая, что элементы S равновероятны, мы имеем

5 32

10 32

10 32

5 32 J 32 •

Чтобы понять, как вычисляются эти значения, рассмотрим Р(Х=4)=Р (имеются в точности четыре свободных процессора)

= P(s2USsUsUsUs,) =

= Р (S,) + Р (8з) + Р (sJ + Р (S,) + Р (Se) -~32"32"32"32"f32 32 *

P{X--

= 0)

P{X:

= 1)

Р{Х--

= 2)

Р{Х--

= 3)

P(x:

= 4)

P{X-.

= 5)



[0] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15] [16] [17] [18] [19] [20] [21] [22] [23] [24] [25] [ 26 ] [27] [28] [29] [30] [31] [32] [33] [34] [35] [36] [37] [38] [39] [40] [41] [42] [43] [44] [45] [46] [47] [48] [49] [50] [51] [52] [53] [54] [55] [56] [57] [58] [59] [60] [61] [62] [63] [64] [65] [66] [67] [68] [69] [70] [71] [72] [73] [74] [75] [76] [77] [78] [79] [80] [81] [82] [83] [84] [85] [86] [87] [88] [89] [90] [91] [92] [93] [94] [95] [96] [97] [98] [99] [100] [101] [102] [103] [104] [105] [106] [107] [108] [109] [110] [111] [112] [113] [114] [115] [116] [117]

0.0012