Новости    Библиотека    Байки    Ссылки    О сайте


предыдущая главасодержаниеследующая глава

§ 1.7. Сети вероятностных диаграмм

На сетях диаграмм Венна точки в некоторых ячейках операторов не оказывают влияния на соответствующие результирующие диаграммы.

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

Например, на диаграмме Dτ2,1 (рис. 1.36) точку в ячейке 11 можно уничтожить, а в ячейках 4-10,14 можно поставить точки, не изменяя диаграммы [Dτ2,1].

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

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

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

Вероятностной диаграммой п переменных будем называть символ Венна n переменных, в каждой ячейке которого поставлена одна из трех букв: 1, р, 0.

На рис. 1.53 показана вероятностная диаграмма четырех переменных.

Вероятностную диаграмму n переменных будем обозначать через Dρ, иногда указывая справа в круглых скобках число переменных или сами переменные: Dρ (n) или Dρ1,..., аn).

Рис. 1.53
Рис. 1.53

Используя нумерацию ячеек символа Венна n переменных, вероятностную диаграмму можно записывать в линейной форме: Dρ(n)0,..., αn2-1), где αj - одна из букв 1, ρ, 0, j = 0,..., 2n -1. Например, Dρ (4) (0, 0, 0, 0, 0, 0, р, 0, р, 0, 1, 0, р, р, 1, р) - линейная запись вероятностной диаграммы четырех переменных на рис. 1.53.

Каждая из букв р на вероятностной диаграмме может принимать значение 1 или 0 независимо от остальных букв р на этой диаграмме.

Между вероятностными диаграммами и диаграммами Венна n переменных можно установить соответствие.

Единица в t-той ячейке вероятностной диаграммы взаимно однозначно соответствует точке в i-той ячейке диаграммы Венна.

Ноль в j-той ячейке вероятностной диаграммы обозначает, что j-тая ячейка на соответствующей диаграмме Венна пуста, и наоборот.

Буквы р вероятностной диаграммы могут принимать значения 1 или 0, независимо друг от друга, следовательно, каждой вероятностной диаграмме л переменных, в I ячейках которой находятся буквы р, соответствует 21 диаграмм Венна.

Например, вероятностной диаграмме Dρ (3)(p, 0, 1, 1, 0, р, 0, 1) соответствуют четыре диаграммы Венна:


Из вероятностных диаграмм можно строить сети. Построение осуществляется аналогично случаю сетей диаграмм Венна, в том числе аналогично строятся М-регулярные и регулярные сети вероятностных диаграмм, а также сети с обратными связями. Единственное отличие от сетей диаграмм Венна состоит в предположении, что все входные диаграммы, содержащие по крайней мере по одной букве р, имеют одинаковое число переменных (обозначим его через n), а все остальные диаграммы первого ранга имеют число переменных, не превосходящее n.

Например, на рис. 1.54 приведена трехранговая сеть вероятностных диаграмм с двумя выходами, а на рис. 1.55 - сеть вероятностных диаграмм с обратными связями.

Будем предполагать, что все диаграммы первого ранга имеют одинаковое число переменных л.

В противном случае заменяем каждую диаграмму первого ранга Dρ1,i (m), m<n (без букв р) ее результирующей, содержащей n переменных. Построение результирующей диаграммы [Dρ1,i] осуществляется аналогично случаю одноранговых сетей диаграмм Венна (в силу установленного соответствия между вероятностными диаграммами без букв р и диаграммами Венна). Если на диаграмме Dρ1,i (m) оканчивается m кривых (возможно только для сетей с обратными связями), то число кривых, оканчивающихся на увеличивается до n (некоторые из кривых повторяются несколько раз; похоже на операцию 6, § 1.5).

Рис. 1.54
Рис. 1.54

Если на всех входных диаграммах нет букв p, то n положим равным шах (n1,..., nk), где ni - число переменных на i-той диаграмме; k - число диаграмм в первом ранге; i = 1,..., k.

Рис. 1.55
Рис. 1.55

Например, сеть на рис. 1.56 заменяем сетью на рис. 1.57.

Каждой сети вероятностных диаграмм будем ставить в соответствие одну или несколько вероятностных диаграмм n переменных а1,...,аn, где а1,..., аn - различные переменные каждой из диаграмм первого ранга. Такие диаграммы будем называть результирующими диаграммами сети. Их число совпадает с числом выходных диаграмм сети. На рисунках результирующие диаграммы помещаем в квадратных скобках справа от соответствующих выходных диаграмм.

Перейдем к построению результирующих диаграмм.

Способ 1.Перебор всех сетей диаграмм Вен-на, соответствующих данной сети вероятностных диаграмм. Пусть дана сеть G вероятностных диаграмм без обратных связей с одним выходом. Пусть I - число всех букв р на диаграммах сети G.

Тогда число сетей диаграмм Венна, соответствующих данной сети G, равно 27.

Пример 1.18. На рис. 1.59 приведены все 8 сетей диаграмм Венна, соответствующих сети вероятностных диаграмм на рис. 1.58,

Для каждой из 27 сетей диаграмм Венна можно построить соответствующую результирующую диаграмму n переменных, n - число различных переменных в первом ранге.

Рис. 1.56
Рис. 1.56

Рис. 1.57
Рис. 1.57

Предположим, что все 27 результирующие диаграммы Венна построены; обозначим их Dτ1,..., Dτ2I. Тогда результирующая вероятностная диаграмма исходной сети G такова:

возьмем символ Венна n переменных;

если в ячейках s1,.....,sk на каждой из диаграмм Dτ1,.....,Dτ2I есть точки, то в соответствующих ячейках s1,..., sk символа Венна поставим единицы;

если ячейки i1,.....,ir на каждой из диаграмм Dτ1,......,Dτ2I пусты, то в соответствующих ячейках i1,...,ir символа Венна поставим нули;

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

В полученной результирующей диаграмме сети G буква р стоит в тех и только тех ячейках, которые пусты, по крайней мере на одной из диаграмм Dτ1,..., Dτ2I, и в которых на некоторых из них обязательно есть точки.

Пример 1.17 (продолжение). Вернемся к рис. 1.59. В ячейке 3 на всех результирующих диаграммах Dτ1, ..., Dτ8 есть точки, поэтому в ячейке 3 на результирующей диаграмме сети (рис. 1.58) находится единица. Ячейки 6 и 7 пусты на всех диаграммах Dτ1 ,...,Dτ8, поэтому в них на рис. 1.58 стоят нули. Для всех остальных ячеек имеются диаграмма Dτi, на которой эта ячейка пуста, и диаграмма Dτj, на которой в этой ячейке есть точка, поэтому в них на результирующей диаграмме сети (рис. 1.58) расположены буквы р.

Рис. 1.58
Рис. 1.58

Рис. 1.59
Рис. 1.59

Следует обратить внимание на то, что не любая комбинация значений букв р на результирующей вероятностной диаграмме дает некоторую из диаграмм Dτ1 ,..., Dτ2I. Так, на рис. 1.59 всего четыре различных результирующих диаграммы, а букв р на результирующей диаграмме сети рис. 1.58 - пять.

Если дана сеть G вероятностных диаграмм без обратных связей с несколькими выходами, то результирующие диаграммы для каждого выхода можно строить независимо от остальных выходов. Для этого вместо сети G рассматривается l сетей G1, ....., Gl с одним выходом, где l - число выходных операторов сети G; все ранги сети G, (i = 1,..., l), кроме последнего, совпадают с соответствующими рангами сети G, а в последнем ранге находится только i-тая выходная диаграмма сети G.

Пример 1.19. На рис. 1.54 содержится трехранговая сеть вероятностных диаграмм с двумя выходами: l = 2, I = 13 для сети G1, I = 15 для сети G2. Результирующие диаграммы сети не содержат букв р, им соответствуют результирующие диаграммы Венна в примере 1.13.

Остановимся на функционировании сетей вероятностных диаграмм во времени, особенно обращая внимание на сети с обратными связями.

Каждой сети вероятностных диаграмм G (G может быть сетью с обратной связью) соответствует 2I сетей диаграмм Венна, где I - число всех букв р на диаграммах сети G. Если G - сеть с несколькими (l) выходами, то и каждая из 2I сетей диаграмм Венна имеет I выходов.

В каждый данный момент времени t + i, i > 0, для каждой из 21 сетей диаграмм Венна можно построить свою результирующую диаграмму (см. § 1.6). Перебирая все 21 сетей диаграмм Венна в момент времени t + i, можно сконструировать результирующие вероятностные диаграммы исходной сети G в момент времени t + i аналогично случаю сетей вероятностных диаграмм без обратных связей, независящих от времени.

Пример 1.20. На рис. 1.55 приведена одновыходная сеть вероятностных диаграмм с обратной связью. Результирующие вероятностные диаграммы сети в различные моменты времени t + i, i ≥ 0, не содержат букв р, им соответствуют результирующие диаграммы Венна сети в примере 1.16.

Для построения результирующей диаграммы сети вероятностных диаграмм мы использовали 2I сетей диаграмм Венна. Нетрудно убедиться, что среди этих 2I сетей диаграмм Венна встречаются попарно эквивалентные между собой. Например, сети диаграмм Венна на рис. 1.59 можно разбить на четыре группы, внутри каждой из которых все сети попарно эквивалентны.

Следовательно, при нахождении результирующей вероятностной диаграммы часто можно не перебирать все 2I сетей диаграмм Венна. Так, в примере 1.18 (рис. 1.58 и 1.59) можно ограничиться только четырьмя попарно неэквивалентными сетями диаграмм Венна.

Для каждой ячейки первого ранга буква в ячейке с тем же номером на результирующей вероятностной диаграмме определяется независимо от букв в остальных ячейках первого ранга, а каждая буква любого оператора, начиная со второго ранга, на сети диаграмм Венна функционирует независимо от остальных букв. Поэтому при конструировании результирующей вероятностной диаграммы можно ограничиться рассмотрением только тех сетей диаграмм Венна, которые получаются, когда все буквы р на каждой вероятностной диаграмме исходной сети принимают одинаковые значения. Обозначив за J количество вероятностных диаграмм данной сети, содержащих буквы р, получим, что при определении результирующей вероятностной диаграммы достаточно перебрать 2J соответствующих сетей диаграмм Венна. В примере 1.18 J = 3, т. е. 2J = = 27, в примере 1.19 J = 4, а I = 15 для сети С2.

Способ 2. Перебор элементарных последовательностей n переменных. Пусть G - любая сеть вероятностных диаграмм (G может быть сетью с обратной связью и с несколькими выходами), n - число различных переменных на каждой из диаграмм первого ранга.

Если G - сеть с обратной связью, то ее поведение исследуется в фиксированные моменты времени t + i, i ≥ 0. Если G - сеть без обратных связей, то ее функционирование можно изучать как независимо от времени, так и в зависимости от момента времени, в последнем случае сеть работает аналогично сетям с обратными связями (для сравнения см. § 1.6.).

При рассмотрении сетей, зависящих от времени, основную роль играют связи между диаграммами; на чертежах эти связи выражаются с помощью кривых (иногда кривые можно опускать, тогда они подразумеваются). В момент времени t + i функционируют только те операторы сети, на которых оканчиваются стрелки кривых. Все остальные операторы сети можно считать пустыми - результатами их работы также являются пустые диаграммы (аналогично см. § 1.6). В момент времени t - начальный момент - функционируют только операторы первого ранга - входные диаграммы, а все остальные операторы можно предполагать пустыми.

Таким образом, в каждый данный момент времени t + i, i≥0, вместо сети G можно рассматривать некоторую другую сеть Gi, отличающуюся от G только тем, что некоторые диаграммы сети G воспринимаются как пустые. Поэтому при изложении второго способа построения результирующих диаграмм не будем специально выделять случай, когда работа сети зависит от времени. Само собой разумеется, что в каждом конкретном примере должно быть указано, зависит результирующая диаграмма от времени или нет (это касается только сетей без обратных связей, сети с обратными связями обязательно зависят от времени). Если предполагается зависимость от времени, то в каждый данный момент t + i сеть G заменяется сетью Gi i ≥ 0 (G0 - сеть в начальный момент времени t).

Каждой ячейке на диаграммах первого ранга соответствует определенная последовательность sl из букв 1, р и 0 (l - номер этой ячейки), l = 0,..., 2n - 1, sl δ1,l,..., δk,l, где k - число диаграмм в первом ранге, δi,l есть 1,0 или р в зависимости от того, какая из букв 1, 0, р стоит в l-той ячейке на i-той диаграмме первого ранга, i = 1,..., k.

Если среди δ1,l,..., δk,l нет букв р, то sl есть элементарная последовательность. Если среди δ1,l,..., δk,l встречается r букв р, то, придавая р значение 1 или 0, получим 2r различных элементарных последовательностей.

Для каждой последовательности sl в случае регулярных сетей можно проследить, переходя от диаграмм j-того ранга к диаграммам (j + 1)-го ранга, 1 - 1, ≤j≤g-1 гдe g - число рангов в сети, какое значение 1, 0 или р принимает данный выход сети G. Для сетей более сложных, чем регулярные, существенную роль при этом играют связи между диаграммами.

Рис. 1.60
Рис. 1.60

Пример 1.21. Построим результирующую диаграмму регулярной сети на рис. 1.60. В первом ранге находится две, во втором - три вероятностные диаграммы двух переменных, а в третьем ранге - одна выходная вероятностная диаграмма трех переменных. На каждой диаграмме есть буквы р; общее число букв р в сети I = 10. Предполагаем, что функционирование сети не зависит от времени.

1. Нулевой ячейке первого ранга соответствует последовательность s0 0 р. Этот случай разбивается на два подслучая: р = 1, р = 0.

1,1. p = 1, т. е. значением первой диаграммы первого ранга Di, 1 (aiy аъ) является 0: записываем Dρ1,1 (0, 0) = 0; значением

второй диаграммы первого ранга Dρ1,21, а2) является 1: Dρ1,2 (0, 0)= 1, при этом а1, а2 - переменные первого ранга. Значения диаграмм первого ранга образуют элементарную последовательность 01, поэтому переходим к ячейке 1 (01 есть 1 в десятичной системе) диаграмм второго ранга. Dρ2,1 (0,1) = 0 - в ячейке 1 диаграммы Dρ2,1 находится 0, Dρ2,2 (0,1) = 0, Dρ2,3 (0,1) = р. Случай 1,1 в свою очередь разбивается на два подслучая.

1, 1, 1. р = 1. Значения диаграмм второго ранга образуют элементарную последовательность 001, переходим к ячейке 1 выходной диаграммы, Dρ3,1 (0, 0, 1) = 0.

1, 1, 2. р = 0. Значения диаграмм второго ранга образуют последовательность 000, смотрим на нулевую ячейку диаграмм третьего ранга, Dρ3,1 (0, 0, 0) = 0.

1, 2. р = 0. Значения диаграмм первого ранга образуют последовательность 00, Dρ2,1 (0,0) = р, Dρ2,2 (0,0) = р, Dρ2,3 (0,0) = 0. Следовательно, случай 1,2 распадается на 4 подслучая.

1, 2, 1. Dρ2,1 (0,0) = 1, Dρ2,2 (0,0) = 1. Значения диаграмм второго ранга образуют последовательность 110; берем ячейку 6 диаграммы Dρ3,1, Dρ3,1(1, 1, 0) = р.

Дальше случай 1 можно не разбирать, так как независимо от остальных подслучаев в нулевой ячейке результирующей диаграммы необходимо поставить р. Это аналогично нахождению двух соответствующих сетей диаграмм Венна, в нулевой ячейке результирующих диаграмм которых на одной из них пусто, а на другой стоит точка; эти сети таковы, что в нулевой ячейке диаграмм Dρ1,2, Dρ2,1, Dρ2,2 на обеих находятся точки, а в ячейке 6 диаграммы Dρ3,1 на одной пусто, а на другой есть точка.

2. Первой ячейке первого ранга соответствует последовательность s1 pp.

2, 1. Dρ1,1(0,1) = 1, Dρ1,2 (0,1) = 1. Переходим ко второму Рангу к ячейке 3 (11 есть 3 в десятичной системе), Dρ2,1(1,1) = 1, Dρ2,2 (1,1) = 0, Dρ2,3 (1,1) = 1. Смотрим ячейку 5 третьего ранга (10 1 есть 5): Dρ1,3(1, 0, 1) = 1.

2,2. Dρ1,1 (0,1) = 1, Dρ1,2 (0,1) = 0, Dρ2,1 (1,0) = р, Dρ2,2 (1,0) = 0, Dρ2,3 (1,0) = 0.

2,2,1. Dρ2,1 (1,0) = 1, Dρ3,1 (1,0,0) = 0.

Дальше случай 2 можно не разбирать, так как независимо от остальных подслучаев в первой ячейке результирующей диаграммы необходимо поставить р, Dρ3,1 (1, 0, 1) = 1, Dρ3,1 (1, 0, 0) = 0.

3. Рассмотрим ячейку 2 первого ранга; ей соответствует последовательность s2 11, которая является элементарной последовательностью двух переменных, Dρ1,1 (1,0) = 1 и Dρ1,2 (1,0) = 1. Следовательно, Dρ1,2 (1,1) = 1, Dρ2,2 (1,1) = 0 и Dρ2,3 (1,1) = 1. Поэтому Dρ3,1 (1, 0, 1) = 1 (во второй ячейке результирующей диаграммы ставим 1).

4. Наконец, перейдем к ячейке 3 первого ранга s 10, Dρ1,1 (1,1) = 1, Dρ1,2 (1,1) = 0, Dρ2,1 (1,0) = р, Dρ2,2 (1,0) = 0, Dρ2,3 (1,0) = 0.

4.1. Dρ2,1 (1,0) = 1, Dρ3,1 (1,0,0) = 0.

4.2. Dρ2,1 (1,0) = 0, Dρ3,1 (0,0,0) = 0.

Таким образом, поставив в ячейке 3 букву 0, завершим построение результирующей диаграммы; на рис. 1.60 она расположена в квадратных скобках справа от выходной диаграммы.

Результаты вычислений приведены в табл. 1,7. В первом столбце даны номера ячеек первого ранга в двоичной системе (т. е. различные элементарные последовательности n переменных, n = 2), которые совпадают с номерами ячеек результирующей диаграммы; в следующих столбцах приведены значения диаграмм сети (числа в соответствующих ячейках диаграмм); ячейки с буквами р разбиваются на подъячейки (подстроки) - перебираются все возможные комбинации значений букв р, столбцы обозначаются парами чисел r, С (r - номер ранга, i - номер диаграммы в ранге), при этом в случае, когда в столбце выходной диаграммы получается или буква р, или 1 и 0 в разных подъячейках, соответствующих одной ячейке диаграмм первого ранга, перебор значений р можно прекратить, в ячейке результирующей диаграммы ставится р (в таблице, чтобы подчеркнуть, что не все возможные комбинации рассмотрены, проводим двойную горизонтальную черту и оставляем пустые под ячейки).

Таблица 1.7
Таблица 1.7

Рис. 1.61
Рис. 1.61

Пример 1.22. Разберем построение результирующей диаграммы сети на рис. 1.61; она расположена в квадратных скобках справа от выходной диаграммы.

В нулевой ячейке результирующей диаграммы стоит р, так как возможны два случая: 1) Dρ1,1 (0, 0, 0) = 0, Dρ1,2 (0, 0, 0) = 0, Dρ1,3 (0, 0, 0) = 0 и Dρ1,4 (0, 0, 0) = 0, тогда Dρ2,1 (0, 0, 0, 0) = 1; 2) Dρ1,1 (0,0,0) = 1, Dρ1,2(0, 0,0) = 0, Dρ1,3 (0, 0, 0) = 0, Dρ1,4(0, 0, 0)= 0, тогда Dρ2,1 (1, 0, 0, 0) = 0.

В ячейке 1 результирующей диаграммы - р, так как Dρ1,1 (0, 0, 1) = Dρ1,2 (0, 0, 1) = Dρ1,3 (0, 0, 1) = Dρ1,4 (0, 0, 1) = 1, а Dρ2,1 (1, 1, 1, 1) = р.

В ячейке 2 - р, так как возможны два случая, как и для нулевой ячейки.

В ячейке 3-1: Dρ1,1(0, 1, 1) = Dρ1,2 (0, 1, 1) = Dρ1,3 (0, 1, 0) = Dρ1,4 (0, 1, 1) = 0, a Dρ2,1 (0, 0, 0, 0) = 1.

В ячейке 4 - p: Dρ1,1 (1, 0, 0) = 1, Dρ1,2(1, 0, 0) = 0, Dρ1,4(1, 0, 0) = 1, возможно Dρ1,3 (1, 0, 0) = 0, a Dρ2,1 (1, 0, 0, 1) = р.

В ячейке 5-1, так как возможны четыре случая:

1) Dρ1,i(1, 0, 1) = 0, i = 1, 2, 3, 4, a Dρ1,2(0, 0, 0, 0) = 1;

2) Dρ1,i (1,0,1) = 0,i = 1,2,3, Dρ1,4 (1, 0, 1) = 1, a Dρ2,1 (0, 0, 0,1) = 1;

3) Dρ1,i (1, 0, 1) = 0, 1 = 1, 3, 4, Dρ1,2 (1, 0, 1) = 1, а Dρ2,1(0, 1, 0, 0) = 1;

4) Dρ1,1(1, 0, 1) = Dρ1,3 (0, 0, 1) = 0, Dρ1,2 (1,0, 1) = Dρ1,4 (1, 0, 1) = 1, a Dρ2,1(0, 1, 0, 1) = 1.

В ячейке 6 - р: возможен случай Dρ1,1 (1, 1, 0) = 1 , Dρ1,2(1,1, 0) = 0, Dρ1,3(1, 1, 0) = 1, Dρ1,4 (1, 1, 0) = 0, a Dρ2,1 (1, 0, 1, 0) = p.

Наконец, в ячейке 7 - 0, так как если Dρ1,1( 1, 1, 1) = 1, Dρ1,i (1,1, 1) = 0, i = 2,3,4, то Dρ2,1 (1, 0, 0, 0) = 0 и если Dρ1,i( 1, 1, 1) = 1, i = 1,2, Dρ1,j( 1, 1, 1) = 0, j = 3,4, то Dρ2,1 (1, 1, 0,0) = 0.

Пример 1.19 (продолжение). Построение результирующих диаграмм сети (рис. 1.54) приведено в табл. 1.8. Столбцы в таблице, соответствующие значениям диаграмм сети, обозначены выражениями r, i (r1, i1) (r2, i2)... (rk, ik), где r - номер ранга; i - номер диаграммы Dρr,i в ранге; r - номер ранга; i - номер диаграммы в rj-том ранге, связанной с рассматриваемой диаграммой Dρr,i(k) кривой с номером i, j = 1,..., k. На рис. 1.54 результирующие диаграммы находятся в квадратных скобках справа от выходных диаграмм сети.

Таблица 1.8
Таблица 1.8

Способ 3. Уменьшение числа рангов в регулярной сети вероятностных диаграмм. Первые два способа построения результирующих диаграмм сети связаны с перебором.

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

Уменьшая число рангов, получаем новую сеть, эквивалентную исходной.

Сети G1 и G2 вероятностных диаграмм называем эквивалентными, если все результирующие диаграммы сети G1 и только они являются результирующими диаграммами сети G2 (для сравнения см. эквивалентные сети диаграмм Венна).

Уменьшать число рангов в данной регулярной сети G можно по способам 1 и 2.

Построим вероятностные диаграммы работы сети, состоящей из двух рангов - последнего и предпоследнего исходной сети G. Заменим найденными диаграммами два последних ранга сети G. Получим сеть G1 вероятностных диаграмм, состоящую из g - 1 рангов, где g - число рангов в сети G. Сеть G1 эквивалентна сети G. И так далее последовательно уменьшаем число рангов в сети G. В конце концов получаем одноранговую сеть, диаграммы которой являются результирующими диаграммами сети G.

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

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

Будем также предполагать, что на выходной диаграмме содержится по крайней мере одно из значений 1, р. В противном случае результирующая диаграмма имеет, как и оператор, только нули; в этом случае выходную диаграмму называем пустым оператором.

Правила работы выходного оператора регулярной двухранговой сети вероятностных диаграмм

П0. Оператор N-переноса. Пусть выходная диаграмма Dρ2,1 сети G имеет только две ячейки, nk+1 = 1. Тогда k = 1, т. е. в первом ранге находится только одна диаграмма (n).

Пусть на диаграмме Dρ2,1 (1) в нулевой ячейке находится 0, в первой - 1; на диаграмме (n) в ячейках β1,..., βl - 1, в ячейках β1,..., βr - р, в ячейках r+1,..., β2n - 0.

Построим символ Венна n переменных, в ячейках поставим буквы, графически равные буквам, лежащим в соответствующих ячейках диаграммы Dρ1,1(n). Получим вероятностную диаграмму [Dρ2,1] - результат работы данной сети G. В этом случае диаграмму Dρ2,1 называем оператором N-переноса, в силу построения [Dρ2,1][Dρ1,1(n)]

Πp0. Оператор Np-переноса. Пусть предположения правила П0 сохраняются, за исключением того, что в первой ячейке на Dρ2,1 (1) стоит не единица, а р. Диаграмму Dρ2,1 (1) называем оператором Np-переноса.

Построим символ Венна n переменных, в ячейках β1,..., βr поставим р, в ячейках βr+1,..., β2n - 0. Получим вероятностную диаграмму [Dρ2,1] - результат работы данной сети G.

Рис. 1.62
Рис. 1.62

Рис. 1.63
Рис. 1.63

Пример 1.23. Работа оператора N-переноса демонстрируется на рис. 1.63, а работа оператора Nр-переноса - на рис. 1.62; диаграммы первого ранга на обоих рисунках совпадают.

П1. Оператор N-отрицания. Пусть предположения правила П0 сохраняются, только пусть на диаграмме Dρ2,1 (1)в нулевой ячейке находится 1, а в первой - 0.

Такую диаграмму Dρ2,1(1) будем называть оператором N-отрицания.

Построим символ Венна n переменных, в ячейкам βr+1,...,β2n поставим 1, в ячейках βl+1,..., βr - р, в ячейках β1,.. , βl - 0. Получим вероятностную диаграмму [Dρ2,1], являющую результирующей диаграммой исходной сети G.

Пp1. Оператор Np-отрицания. Пусть предположения правила П1 сохраняются, только в нулевой ячейке на диаграмме Dρ2,1 (1) стоит не единица, а буква р. В этом случае диаграмму Dρ2,1 (1) называем оператором Nр-отрицания.

Построим символ Венна n переменных, в ячейках βl+1 ,...,β2n поставим р, в ячейках β1,..., βl - 0. Получим вероятностную диаграмму [Dρ2,1], которая является результирующей диаграммой исходной сети G.

Пример 1.24. На рис. 1.64 показана работа оператора N-отрицания при n = 3. На рис. 1.65 - работа оператора Nр-отрицания при n = 4.

П2. Оператор N-конъюнкции. Пусть рассматривается сеть G, выходная диаграмма которой имеет 4 ячейки, nk+1 = 2. Тогда k = 2, т. е. в первом ранге сети G расположены две диаграммы: Dρ1,1 (n) и Dρ1,2 (n).

Пусть на Dρ2,1 (2) в ячейке 3 стоит 1, а в остальных ячейках -0, в ячейках β1,....,βl диаграмм Dρ1,1 (n) и Dρ1,2 (n) = 1, в ячейках βs+1,.....,βm-1 диаграмм Dρ1,1 (n) и Dρ1,2(n) = р, в ячейках βs+1,.....,βq-p на диаграмме Dρ1,1(n) и р на диаграмме Dρ1,2(n), в ячейках βm+1,......,βq-p на Dρ1,1 (n) и 1 на Dρ1,1 (n), во всех остальных ячейках стоит нуль, по крайней мере, на одной из диаграмм Dρ1,1 (n) или Dρ1,2 (n).

Диаграмму Dρ2,1 (2) будем называть оператором N-конъюнкции.

Рис. 1.64
Рис. 1.64

Рис. 1.65
Рис. 1.65

Построим символ Венна n переменных, в ячейках β1,..., βl, поставим 1, в ячейках βl+1,...., βq - p, во всех остальных ячейках - 0.- Получим вероятностную диаграмму [Dρ2,1] - результат работы оператора N-конъюнкции.

Пp2. Оператор Np-конъюнкции. Пусть предположения правила П2 сохраняются, только пусть в ячейке 3 диаграммы Dρ2,1(2) стоит не единица, а р.

Построим символ Венна n переменных, в ячейках β1,..., βq поставим р, во всех остальных - 0. Получим вероятностную диаграмму [Dρ2,1] - результат работы данной сети G. В этом случае Dρ2,1 (2) называем оператором Nр-конъюнкции.

Пример 1.25. На рис. 1.66 и 1.67 дана соответственно работа операторов N-конъюнкции и Np-конъюнкции при n = 4.

П3. Рассмотрим случай, когда на выходной диаграмме Dρ2,1 находится только одна отличная от нуля буква - единица. Предположим, что диаграмма Dρ2,1 отличается от выходных диаграмм в правилах П0, П1 и П2.

Пусть эта единственная единица на Dρ2,1 (m) лежит в ячейке Δ 1,....., d̃m, где d1,..., dm - все графически различные переменные диаграммы Dρ2,1,


j = 1,..., m.

Для определенности пусть Δ 1 ... d̄ii+1... d̄m (0 ≤ i≤ m, i = 0 означает, что Γ d1... dm, i = m - Δ1... d̄m).

Рис. 1.66
Рис. 1.66

Рис. 1.67
Рис. 1.67

Построим N-отрицания диаграмм Dρ1,1(n),..., Dρ1,i (n) (по правилу П1). К полученным диаграммам [Dρ1,1],..., [Dρ1,i] и к диаграммам Dρ1,i+1(n),...., Dρ1,m(n) применим последовательно правило П2: от диаграмм [Dρ1,1] и [Dρ1,2] перейдем к диаграмме Dρ1, от диаграмм Dρ1 и [Dρ1,3] - к диаграмме Dρ2 и т. д. от диаграмм Dρi-1 и Dρ1,i+1 - к диаграмме Dρi, и т. д., наконец, Dρm-2 и Dρ1,m к диаграмме Dρm-1, являющейся результирующей диаграммой работы исходной сети.

Правило П3 можно сформулировать также следующим образом.

Перенесем на символ Венна результирующей диаграммы, во-первых, те и только те единицы, для которых соответствующие ячейки на всех диаграммах Dρ1,1,..., Dρ1,i пусты, а ячейки на всех диаграммах Dρ1,i+1,..., Dρ1,m заполнены единицами, во-вторых, те и только те нули, для которых в соответствующих ячейках, по крайней мере на одной из диаграмм Dρ1,1,..., Dρ1,i, стоит единица или, по крайней мере на одной из диаграмм Dρ1,i+1,..., Dρ1,m - нуль.

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

Правило П3 является обобщением правил П0, П1 и П2. Поэтому, говоря об этом правиле, в дальнейшем предполагаем, что П0, П1 и П2 - частные случаи П3.

Пp3. Правило П3 отличается от П3 только тем, что на диаграмме Dρ2,1 единица заменена на р, а вместо правила П2 применяется правило П2.

Правило П3 короче формулируется так.

Перенести на символ Венна результирующей диаграммы те И только те нули, для которых в соответствующих ячейках, по крайней мере на одной из диаграмм Dρ1,1,..., Dρ1,i, находится единица или на одной из диаграмм Dρ1,i+1,..., Dρ1,m - нуль; во всех остальных ячейках символа Венна поставить буквы р.

Аналогично П3 правило П3 является обобщением правил Пp0, Пp1 и Пp2.

Пример 1.26. Возьмем регулярную сеть вероятностных диаграмм на рис. 1.68. Она имеет два выхода. Первый (слева) выходной оператор действует по правилу П3, второй - по правилу Пp3.

Рис. 1.68
Рис. 1.68

П4. Оператор N-дизъюнкции. Пусть на Dρ2,1 (m) находится s, s > 1, отличных от нуля букв 1, р: Δ1,..., Δr,.,...,Δs, где Δi 1, i = 1, .., r, r > 0; Δj р, j = r + 1 s, s > r.

По правилу П3 для Δ2, если Δr 1, построим вероятностную диаграмму, не обращая внимания на буквы Δs, сотрем на ней все нули, получим диаграмму С1.

По правилу П3 для Δ2, если Δ2 1, построим вероятностную диаграмму, не обращая внимания на буквы Δ1, Δ3,..., Δs, перенесем с нее все знаки 1, р в соответствующие ячейки диаграммы С1, получим диаграмму С2, в некоторых ячейках которой может содержаться две буквы р.

И так далее. По правилу П3 для Δr, если Δr 1. построим вероятностную диаграмму, не обращая внимания на буквы Δr-1r+1,..., Δs, перенесем с нее все знаки 1, р в соответствующие ячейки диаграммы Сr-1, получим диаграмму Сr.

По диаграмме Сr построим вероятностную диаграмму Dρr (n).

Возьмем символ Венна n переменных. В ячейках βj символа Венна, соответствующих пустым ячейкам диаграммы Сr, поставим 0. В ячейке βi поставим 1, если 1 находится в ячейке βi диаграммы Сr или если в m-членной последовательности из знаков 1,0, р, соответствующей ячейке βi вероятностных диаграмм первого ранга, находится только t букв р, а в ячейке β, диаграммы Сr находится 2t букв р. Пусть β1,.....,βu - все ячейки символа Венна, в которых постановлена одна из букв: 1 или 0. Во всех остальных ячейках поставим по одной букве р. Получим диаграмму Dρr (n). Если r - 0, то будем считать, что на Dρr (n) находятся только нули.

По правилу Пр3 для Δr+1, если Δr+1p, построим вероятностную диаграмму, не обращая внимания на буквы Δ1,..., Δr, Δr+2,..., Δs, перенесем с нее знаки р в соответствующие ячейки диаграммы Dρr(n), не занятые 1, р (заменяя 0 на р), получим диаграмму Dr+1(n).

И так далее. По правилу Пp3 для Δs, если Δsр, построим вероятностную диаграмму, не обращая внимания на буквы Δ1,.....,Δs-1 перенесем в нее знаки р в соответствующие ячейки диаграммы Dps~1 (п), не занятые 1, р (заменяя 0 на р), получим диаграмму Dρs-1 (n) - результат работы исходной сети.

В этом случае диаграмму Dρ2,1(m) называем оператором N-дизъюнции, а диаграмму Dρs(n) - результатом функционирования оператора N-дизъюнкции.

Пример 1.22 (продолжение). Оператор Dρ2,1 (4) сети (рис. 1.61) содержит s = 10 отличных от нуля букв, поэтому он является оператором N-дизъюнкции. В ячейках 0, 1, 4, 5 и 14 расположены единицы, r = 5; в ячейках 2, 6, 9, 10 и 15 - буквы р, во всех остальных ячейках - нули.

Диаграмма Сr построена в угловых скобках слева от оператора.

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

Пример 1.21 (продолжение). На рис. 1.60 в фигурных скобках слева от выходной диаграммы - результат работы двух последних рангов. Рассматриваемая сеть эквивалентна двухранговой сети, первый ранг которой совпадает с первым рангом на рисунке, а второй образует диаграмма в фигурных скобках.

Пример 1.27 Трехранговая сеть на рис. 1.69 неэквивалентна сети рис. 1.70, хотя у этих сетей выходные диаграммы совпадают, а первый ранг сети на рис. 1.70 образован соответствующими результирующими диаграммами второго ранга.

Операторы, рассмотренные при третьем способе построения результирующих диаграмм сети, связаны с операциями над диаграммами Венна в исчислении высказываний не только по названию. Если ограничиться сетями вероятностных диаграмм без букв р, то оператору N-отрицания в сетях диаграмм Венна соответствует оператор отрицания, оператору N-конъюнкции - оператор конъюнкции, а результату работы оператора N-дизъюнкции соответствует s-кратное применение операции дизъюнкции (s - количество единиц на операторе N-дизъюнкции).

Рис. 1.69
Рис. 1.69

Рис. 1.70
Рис. 1.70

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

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

В частности, вероятностная диаграмма является не вполне надежной или надежной в зависимости от того, есть на ней буквы р или нет.

Так, сети, разобранные в примерах 1.19 (рис. 1.54) и 1.20 (рис. 1.55), являются надежными, а сети в примерах 1.21 (рис. 1.60) и 1.22 (рис. 1.61) - не вполне надежными.

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

Даны надежные вероятностные диагоаммы n переменных Dρ1(n),...,Dρk (n), k > 1.

Требуется построить надежную сеть G вероятностных диаграмм, состояющую из g рангов, g > 1, и имеющую в r-том ранге n не вполне надежных вероятностных диаграмм, содержащих максимально возможное число букв р, r = 1,....,g, так, чтобы результирующими диаграммами сети G являлись только данные вероятностные диаграммы Dρ1(n),..., Dρk (n), не содержащие букв р.

предыдущая главасодержаниеследующая глава





Пользовательский поиск


Диски от INNOBI.RU




© Злыгостев Алексей Сергеевич, подборка материалов, оцифровка, статьи, оформление, разработка ПО 2001-2017
При копировании материалов проекта обязательно ставить активную ссылку на страницу источник:
http://informaticslib.ru/ "InformaticsLib.ru: Информатика"