--PAGE_BREAK-- A15 A16
6
5 1
X3 A12
0
7 8
A6 A13
КіНЕЦЬ Аk
Мал.1.3. Часткова граф-схема алгоритму Г3
ПОЧАТОК A0
1
0 1
X1
2
A13
3
A9
4
A8
5
1 X2
6 0
A17
7
A6
8
A2
9
A18
КіНЕЦЬ Ak
Мал.1.4. Часткова граф-схема алгоритму Г4
ПОЧАТОК A0
1
A1
2
A6
3
A19
4
0 1
X1
5
0 X2
1
6
A20
7
A17
8
A2
9
A21
КіНЕЦЬ Ak
Мал.1.5. Часткова граф-схема алгортиму Г5
Стовпці МСА відмітимо всіма мітками Ai, що входять до ГСА, крім початкової A0. На перетині рядка Ai і стовпця Ajзапишемо формулу переходу fij від оператора Ai до оператора Aj. Ця функція дорівнює 1 для безумовного переходу або кон`юнкції логічних умов, відповідних виходам умовних вершин, через які проходить шлях з вершини з міткою Ai у вершину з міткою Aj.
За методикою об'єднання закодуємо МСА таким чином:
Таблиця 1.1
Кодування МСА
МСА
P1P2P3
М1
0 0 0 (ùp1ùp2ùp3)
М2
0 0 1 (ùp1ùp2p3)
М3
0 1 0 (ùp1p2ùp3)
М4
0 1 1 (ùp1p2p3)
М5
1 0 0 (p1ùp2ùp3)
Часткові МСА М1-М5 наведені в табл.1.2-1.6
Таблиця 1.2
Часткова МСА М1
A1
A2
A3
A4
A5
A6
A7
A8
Ak
A0
ùx1
ùx1ùx2
x1x2
A1
1
A2
1
A3
1
A4
1
A5
1
A6
1
A7
1
A8
1
Таблиця 1.3
Часткова МСА М2
A1
A3
A6
A7
A9
A10
A11
A12
A22
Ak
A0
1
A1
1
A3
1
A6
1
A7
x3
ùx3
A9
1
A10
1
A11
1
A12
1
A22
1
Таблиця 1.4
Часткова МСА М3
A6
A12
A13
A14
A15
A16
Ak
A0
1
A6
1
A12
1
A13
1
A14
ùx1
x1
A15
x3
ùx3
A16
1
Таблиця 1.5
Часткова МСА М4
A2
A6
A8
A9
A13
A17
A18
Ak
A0
ùx1
x1
A2
1
A6
1
A8
x2
ùx2
A9
1
A13
1
A17
1
A18
1
Таблиця 1.6
Часткова МСА М5
A1
A2
A6
A17
A19
A20
A21
Ak
A0
1
A1
1
A2
1
A6
1
A17
1
A19
x1ùx2
x1x2
ùx1
A20
1
A21
1
На наступному етапі побудуємо об'єднану МСА М0, в якій рядки відмічені всіма мітками Аi, крім Аk, а стовпці — всіма, крім А0. На перетині рядка Аi і стовпця Аjзапишемо формулу переходу, яка формується таким чином: Fij=P1fij1+...+Pnfijn (n=1...N). Де fijn-формула переходу з вершини Аi у вершину Аj для n-ої ГСА. Наприклад, формула переходу А0®А1 буде мати вигляд F0,1=ùx1ùp1ùp2ùp3+ ùp1ùp2p3+ +p1ùp2ùp3. У результаті ми отримаємо об'єднану МСА М0(табл.1.7). Ми маємо можливість мінімізувати формули переходу таким чином: розглядаючи ГСА Г0 як ГСА Гn, ми підставляємо певний набір Pn=1, при цьому змінні p1..pq не змінюють своїх значень під час проходу по ГСА. Таким чином, якщо у вершину Аi перехід завжди здійснюється при незмінному значенні pq, то це значення pq в рядку Аi замінимо на “1", а його інверсію на “0". Наприклад, у вершину А3 перехід здійснюється при незмінному значенні ùp1 і ùp2, отже в рядку А3ùp1 і ùp2 замінимо на “1", а p1 і p2 на “0". У результаті отримаємо формули F3,4=ùp3, F3,11=p3. Керуючись вищенаведеним методом, отримаємо мінімізовану МСА М0 (табл.1.8).
По таблиці складемо формули переходу для об'єднаної ГСА Г0. Формулою переходу будемо називати слідуюче вираження: Ai®Fi,1А1+..+Fi,kАk, де Fi,j-відповідна формула переходу з мінімізованої МСА. У нашому випадку отримаємо слідуючу систему формул:
A0®ùx1ùp1ùp2ùp3A1+ùp1ùp2p3A1+p1ùp2ùp3A1+x1ùx2ùp1ùp2ùp3A2+x1x2ùp1ùp2ùp3A3+
+ùx1ùp1p2p3A8+x1ùp1p2p3A13+ùp1p2ùp3A14
A1®ùp1ùp3A2+p1ùp3A6+ùp1p3A7
A2®ùp1ùp2ùp3A6+ùp1p2p3A18+p1ùp2p3A21
A3®ùp3A4+p3A11
A4®A5
A5®А6
--PAGE_BREAK--