Si = {0.0, о, 0.0) ffia = (0,1,0.1,0) ff23 = (1.0.1,1,0)

Дг = (1.0,0.0,0) 5,3= (0,1,0,0.1) Я24 = (1.1.0.0.1)

5з=(0.1,0.0,0) «14= (0.0.1.1,0) S25 = (1.1.0,1,0)

«4= (0.0,1.0.0) ffi5=(0.0.1.0,1) *ze = (1.1.1.0,0)

«5=(0.0. о, 1.0) ff,e={0.0.0,1.1) ff27 = (0.1,1,1,1)

ff6= (0,0,0.0.1) s„ = (0.0.1,1.1) fte=(1.0,1.1.1)

S7 = (1.1-.0.0,0) Sie = (0.1.0.1,1) S29 = (1,1.0,1,1)

«8= (1.0.1.0,0) ff,9 = (0.1.1.0,1) Ло = (1.1.1.0.1)

«9= (1.0.0.1.0) ff20 = (0.1,1.1.0) 53, = (1.1.1.1.0)

ff,o= (1.0,0,0.1) • Дг, = (1,0,0,1,1) S8a=(1,1.1,1,1)

ff„ = (0.1.1.0.0) 5гг= (1.0.1.0,1)

Пусть S={si, Sz, Ss, . . .} - пространство элементарных событий эксперимента. Предположим на время, что S содержит конечное или бесконечное счетное число элементов. Событие - это любое подмножество пространства элементарных событий. Обычно событие словесно выражается в терминах эксперимента, а затем переводится на язык подмножества S. Рассмотрим, например, следующее событие: заняты по крайней мере четыре процессора. В терминах S это событие состоит из всех исходов, которые представляют состояния системы, когда используются четыре или пять процессоров, т. е.

Б={(0, 1, 1. 1. 1), (1, О, 1, 1, 1), (1, 1, О, 1, 1), (1, 1, 1, О, 1), (1, 1, 1, 1, 0), (1, 1, 1, 1, 1)}= -

-{27. 28, Sgg, S30, S31, S32}.

Единичный акт эксперимента называется испытанием. Пусть Е - событие, определенное в пространстве S. Если исход испытания эксперимента принадлежит Е, то мы говорим, что событие Е произошло. При каждом испытании может иметь место только один исход s в S. Однако тем самым произойдет каждое событие, включающее s.

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

El = событие, состоящее в том, что заняты по крайней мере четыре процессора,

и Ei = событие, состоящее в том, что заняты самое большее четыре процессора,

то£з = £1П£2= событие, состоящее в том, что заняты в точности четыре процессора = - {(О, 1, I, 1, 1), (1, О, 1, 1, 1), (1, 1, О, 1, 1), (1, 1, 1, О, 1), (1, 1, 1. 1, 0)}=

При чтении П читается как и, и как или н дополнение как не.

Если £1 и £2 - любые два непересекающихся события (т. е. £1 п Л £2=0), то они называются несовместными. Если Ei и £2,- несоа-

местные события, то невозможно, чтобы при одном и том же испытании произошли оба события. В рассматриваемом примере, если

£] - процессор 1 занят и £2 = процессор 1 свободен,

то El П £2=0- Проверьте это, явно перечислив все элементы Ег и £2-Теперь мы готовы начать обсуждение вероятности. Сначала попытаемся сформулировать стандартное интуитивное понятие вероятности с помощью нашего нового словаря. Нас интересует вероятность того, что данное событие случится в результате эксперимента S. Эксперимент S повторяется раз, причем N - большое число. Каждое испытание дает исход из S. Этот исход либо в £, и в этом случае событие Е произошло, либо нет. Предположим, что событие Е произошло п раз в Л испытаниях. В этом случае мы склонны определить вероятность события Е как

Данное число можно интерпретировать как относительную частоту появления события Е при вьшолнении эксперимента S, в этом cjmj,-ность частотной интерпретации вероятности.

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

Пусть S - пространство элементарных событий эксперимента S. Пусть Р - связанная с S жра вероятности, которая ставит в соответствие некоторым событиям EsiS действительное число Р{Е), называемое вероятностью события Е. Эти вероятности должны удовлетворять трем основным правилам (называемым аксиомами):

I Р (£)>0 для любого EsS;

И P(S)=1;

HI Р {Ei\j Е2)=Р {Ei)+P (Е), если Et и Е несовместны, т. е. если Ein Е 2=0.

Как только этим «некоторым» событиям приписываются вероятности, согласующиеся с перечисленными тремя аксиомами, становится возможным (в принципе) вычислять вероятность любого другого события, определенного на S, пользуясь приписанными вероятностями и тремя аксиомами.

По-видимому, самый трудный аспект в построении вероятностных моделей - это установление вероятностей событий. Общая теория не

говорит нам, как для данной конкретной задачи решить, какие выбрать события и какие им приписать числа. Этот выбор целиком оставляется человеку, анализирующему задачу. Обычно вероятности устанавливаются на базе эксперимента и частотной интерпретации. Другой широко распространенной схемой является схема равновероятного распределения, которая описана в следующем разделе. Очень важно понять, что этот выбор при моделировании может сильно повлиять (и влияет!) на полезность самой модели. Теория нейтральна; она будет давать предсказания независимо от выбора конкретных значений. Но, если выбор значений сделан недостаточно точно, предсказания станут неверными и не будут отражать поведение моделируемой задачи кз «реального мира».

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

P(S)=P(si)+P(s2)+. . .+P{sn)+P{ss2)=l

Так как каждое состояние равновероятно, то

P(Sx) = P(S2) = . . .=P(S3.) = l/32.

Итак, основные значения вероятностей установлены.

Теперь мы можем решить нашу мультипроцессорную задачу. Какова вероятность того, что мы сможем загрузить нашу программу, когда она готова к выполнению? Интересующее нас событие - это

Е = свободны три или более процессоров.

В терминах элементов множества S

E={su Sa, . . . , Sij, SiJ.

Следовательно,

P(£) = P(SiUs2U ... USf„) =

= P{Si) + P{S,)+...+P{Si,)

-1,1. j-i± = lE = l 3232 • 32 32 2 "

Таким образом, нам, по-видимому, удастся загрузить программу в половине попыток, учитывая, что мы пользуемся моделью с равными

1) Напомним, что Si.n5i8=(0, О, 1, 1, 1)П(0, 1, О, 1, 1)=0, а не (О, О, О, 1, 1). Это не характеристические векторы (см. приложение Б); не забывайте их интерпретацию.

) Заметьте, что S=Si U % U • • . U %i U «за •