ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 23.10.2024
Просмотров: 110
Скачиваний: 0
б) ранг отмеченного куба и, следовательно, вопрос об оставлении этого куба в покрытии на следующем шаге определяется правыми п координатами.
После этих замечаний приведем без дополнительных пояснении состоящую из трех шагов процедуру получения равносильных ГСА для покрытия D 0. Производные операторы сведены в табл. 7-7.
Сводная таблица производных операторов
9 |
А'і |
6 |
4 |
32 |
10 |
Л'о |
4 |
5 |
33 |
11 |
хі |
4 |
6 |
34 |
12 |
Л'з |
7 |
4 |
35 |
13 |
Лі |
4 |
5 |
36 |
14 |
5 |
6 |
37 |
|
15 |
Ч |
5 |
8 |
38 |
16 |
Л'о |
5 |
4 |
39 |
17 |
Л'о |
5 |
7 |
40 |
18 |
А'і |
7 |
6 |
41 |
19 |
х,2 |
6 |
5 |
42 |
20 |
X ,, |
6 |
4 |
43 |
21 |
X ., |
6 |
7 |
44 |
22 |
■Ѵ.Ч |
8 |
6 |
45 |
23 |
Лі |
7 |
5- |
46 |
24 |
■ч |
7 |
8 |
47 |
25 |
Ч |
5 |
22 |
48 |
26 |
Ч |
5 |
12 |
49 |
27 |
Ч |
16 |
6 |
50 |
28 |
Ч |
17 |
8 |
51 |
29 |
х3 |
15 |
14 |
52 |
30 |
X ., |
14 |
11 |
53 |
31 |
Х о |
15 |
24 |
|
|
1 шаг |
|
|
|
xll |
1x0 |
4 |
|
|
|
Olx |
6 |
|
|
|
lxl |
7 |
|
|
|
xlO |
11 |
|
|
|
lxx |
12 |
|
|
|
xll |
18 |
|
|
|
Oxx |
19 |
|
|
lxl |
Olx |
4 |
|
|
|
1Ix |
6 |
|
|
|
xlx |
9 |
|
|
|
Oxx |
10 |
|
|
|
1x0 |
20 |
|
|
|
lxl |
21 |
|
|
|
— |
|
|
|
Л'з |
17 |
16 |
54 |
|
А'і |
12 |
22 |
55 |
|
* 3 |
24 |
и |
56 |
|
Х о |
6 |
12 |
57 |
|
Л'2 |
9 |
13 |
58 |
|
*2 |
9 |
23 |
59 |
|
* |
20 |
10 |
60 |
|
л3 |
21 |
10 |
61 |
|
21 |
20 |
62 |
||
X |
l |
4 |
19 |
63 |
X |
i |
12 |
6 |
64 |
Ч |
7 |
19 |
65 |
|
X3 |
18 |
11 |
66 |
|
xa |
11 |
13 |
67 |
|
x\ |
12 |
19 |
68 |
|
x |
l |
12 |
5 |
69 |
x „ |
18 |
23 |
70 |
|
X~3 |
23 |
13 |
71 |
|
X l |
26 |
22 |
72 |
|
4 |
|
32 |
22 |
73 |
X 2 |
25 |
33 |
74 |
|
X o |
25 |
34 |
75 |
|
xll
lxl
Таоліща 7-7
x 3 |
28 |
27 |
-V;i |
31 |
27 |
л’з |
28 |
30 |
Л'о |
29 |
33 |
л-з |
29 |
34 |
31 |
30 |
|
Л'о |
9 |
47 |
Л'о |
9 |
49 |
Лі |
35 . |
10 |
Лі |
40 |
10 |
Лз |
37 |
36 |
Л;, |
39 |
36 |
Л'з |
37 |
38 |
Лз |
39 |
38 |
Лз |
43 |
41 |
А'з |
48 |
41 |
Л'о |
42 |
47 |
Л'о |
42 |
49 |
Л'з |
43 |
45 |
Л'о |
44 |
47 |
*о |
44 |
49 |
Лз |
48 |
45 |
2 шаг
1XX |
12 |
|
Oxx |
19 |
|
ххО |
41, |
45 |
xlx |
42 |
44 |
XX1 |
43, |
48 |
XXX |
46 |
|
xlx |
|
9 |
Oxx |
10 |
|
lxx |
35, |
40 |
xxO |
36, |
38 |
XX1 |
37 |
39 |
148
11* |
1lx |
5 |
|
|
|
|
11* |
|
Ox* |
|
22 |
|
|
O.V'O |
6 |
|
|
|
|
|
|
— |
25, |
29 |
|
|
0*1 |
8 |
|
|
|
|
|
|
*1* |
|
||
|
*10 |
Н |
|
|
|
|
|
|
1** |
|
26, |
32 |
|
ХІ 1 |
15 |
|
|
|
|
|
|
x*0 |
|
27, |
30 |
|
1x0 |
16 |
|
|
|
|
|
|
X*1 |
|
28, |
31 |
|
1*1 |
17 |
|
|
|
|
|
|
*0* |
|
33, |
34 |
|
Ox* |
22 |
|
|
|
|
|
|
|
|
|
|
|
*00 |
11 |
|
|
|
|
**1 |
|
*0* |
|
47, |
49 |
|
*01 |
• 24 |
|
|
3 шаг |
|
|
|
—— |
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
|
|
|
|
|
|
|
|
|
|
|
|
xxl |
00* |
5 |
|
XXX |
46, 68, |
69, |
70, |
71, |
72, |
73, |
74, |
75 |
|
*00 |
13 |
|
|
|
|
|
|
|
|
|
|
|
*01 |
23 |
1*1 |
XXX |
60, 61, 62, 63, 64, 65, 66, 67 |
|||||||
XXX |
10* |
12 |
И* |
XXX |
50, 51, |
52, |
53, |
54, |
55, |
56, |
57, |
58, |
59
Как видно из результатов третьего шага, имеется 9 вариантов реа лизации покрытия для Y lt 8 вариантов для Y 2 и 10 вариантов для Y 3. Все варианты раскрыты с помощью таблицы производных операторов (табл. 7-7) и сведены в табл. 7-81. Очевидно, что, выбрав по одному варианту для каждого из Y lt У 2, Y 3, получим подграф ГСАГ равно сильный подграфу Г на рис. 7-8, в котором будет столько условных вершин, сколько производных операторов (без повторения одинако вых) содержится в выбранных вариантах. Например, выбрав вари
анты Ь-,, Ь1 2 и bls, получим ГСА с 12 условными вершинами. |
. , |
Y m, |
Пусть в общем случае есть т исходящих операторов Y lt . . |
||
для каждого из которых в таблице вариантов имеется Rj (/ = |
1, . |
. . , |
т) вариантов реализации. Очевидно, что задача нахождения подграфа с минимальным числом условных вершин сводится к выбору из этой таблицы таких т вариантов (по одному для каждого Yj), чтобы сум марное число производных операторов в выбранных вариантах (без повторений) было минимальным. Назовем эту задачу задачей опреде ления минимального покрытия таблицы вариантов. Ясно также, что число всевозможных различных подграфов, которое можно построить
по такой таблице, |
равно R x . . . Rj . . . R m. В нашем примере это |
число равно 9-8-10 |
= 720. |
Метод Петрика (Petrick) нахождения минимального покрытия таб лицы Квайна при минимизации булевых функций (этот метод на рус ском языке подробно изложен в[7])может быть модифицирован при менительно к поставленной задаче. Пусть в таблице вариантов для каждого Yj (/ = 1, . . . , т) имеются варианты Ь{ 1 , . . . , bjr, . . . ,
1 В вариантах для Yj операторы заключаются в скобки, если они ветре" чаются хотя бы в одном варианте для У(- Ф Yj.
149
К
Г5
Q s
Q
|Н
Q
Таблица вариантов реализации
. юс о с о — • см —< ^
в
|
|
юсмс о |
—• —- см^ |
||||
• о |
С О О і я Г іЛ я Г я Г — |
||||||
|
|
|
|
|
|
||
|
ѵ; |
t-'- э |
|
ю я т см |
|||
|
|
юсмсо |
—— |
^см |
|||
j - , |
со со о г - |
я т |
— |
||||
|
|
||||||
|
|
t o |
см СО ^ |
|
|
||
|
Тх |
|
|
|
|
|
|
j â |
Ю СО СМ — |
СМ — |
|||||
|
|
ю |
смсм—— |
||||
|
|
СО Ю |
я Г СМ я Г —« |
||||
• г? |
Ю |
СМ СО см см— |
|||||
|
_ |
СМ Ю |
СО см |
|
|
||
-е і |
Ю СМ СО СМ — • |
||||||
|
|
|
|
|
|
||
|
|
— CM CM |
|
СО |
|
||
J a |
юс о |
см—— |
|
||||
•с> |
о toсм |
|
|
||||
ю смсм — |
|
|
|||||
|
|
г - |
0 5 |
с о |
- - |
© |
о |
•О |
с о с о |
с о см — ■см |
|||||
|
|
СО N . СО С5 СО4о о |
|||||
J a |
c o c o с о см—. |
— |
|||||
|
- |
о со со |
|
см— |
|||
|
„ |
|
|||||
|
СО о |
о |
— о |
|
|||
j T |
о яг—смсм |
||||||
|
|
см юо см |
|
|
|||
j |
T |
t o c o |
— |
— |
|
|
|
|
|
О |
CJ N |
см |
|
|
|
j |
T |
|
|
|
|
|
|
|
|
ю СО ю |
СО с о —• с о |
||||
|
|
г«- 'S * |
яг |
— |
|
— |
|
*а>- |
Т |
- Г С5 СО — СО |
|||||
|
|
^ |
«3- Г Г — |
— |
CM |
||
J a |
с о |
я т |
с о |
— см |
|||
|
|
t'- |
Я Г |
|
|
wCr |
|
|
|
СМ СО юо — с о |
|||||
|
|
Г - |
'Ч * ’ ö* — |
|
|
||
|
. |
|
|
|
|
|
|
|
|
G5 СО — CO CO 0 5 |
|||||
J a |
CD " Г |
я г — |
См -Н |
||||
|
|
|
|
|
|
||
j â |
|
о |
ЯГ я г — |
|
|
||
|
|
t o |
см 05 |
|
|
|
|
j a |
|
4 |
|
|
|
|
|
|
|
|
|
|
|
|
|
bjRj. Каждый вариант bjr можно пред
ставить |
как |
конъюнкцию Кіг символов |
||
производных |
операторов, |
входящих |
||
в |
этот |
вариант. Например, |
варианту |
|
bg |
из табл. 7-8 соответствует |
конъюнк |
||
ция 69-48-41•18-23-19. Совокупность вариантов для оператора У ■. можно вы-
разить как \ j J(/г, тогда совокупность
всех вариантов для Y lt . . . , Y m будет
|
т I к,- |
іг |
|
|
|
|
Л |
V К |
|
|
|
|
/=1 \Т=1 |
/ |
|
все |
|
|
Раскрывая скобки |
и производя |
|||
возможные операции |
вида |
А -А = |
А, |
||
получим дизъюнкцию из R x . . . R j . . . |
|||||
R m |
конъюнкций, |
где |
R j (j |
= |
, |
т) |
— число вариантов |
реализации |
Yj. |
||
Выбирая конъюнкцию |
с минимальным |
||||
числом сомножителей, получим мини мальное покрытие таблицы вариантов и, следовательно, минимальный подграф ГСА. Трудность такого решения этой задачи, в том числе на быстродействую щих ЦВМ, состоит в том, что с ростом числа исходящих операторов и числа вариантов внутри операторов число по
лученных конъюнкций растет |
очень |
|
быстро. Так, при |
т — 10 и R j |
— 10 |
для всех у = \, . . . |
, т число этих конъ |
|
юнкций равно 1010. |
|
|
Покажем, как можно существенно сжать таблицу вариантов без потери минимального покрытия. Начнем с при мера. Рассмотрим варианты Ь1 и 64 из массива У\:
Ьі h
46 70
(12) 42
19(47)
(12) '
Предположим, что варианты для по крытия Y 2 и Y 3 уже выбраны, в связи
счем возможны четыре случая:
1)ни в одном из вариантов для У2 и
Y 3 не встречаются производные опера торы 12 и 47;
150
2)среди этих вариантов встречается оператор 12 и не встречается оператора 47;
3)среди этих вариантов встречается оператор 47 и не встречается
оператора |
12; |
|
вариантов встречаются оба оператора, |
12 и 47. |
|
|||||
4) |
среди этих |
|
||||||||
Обозначим через с\ и с\ число |
операторов, |
которые добавляются |
||||||||
к зафиксированному для У2 и У3 |
покрытию в t-м случае (из четырех |
|||||||||
перечисленных), если |
Уф покрывается Ьх и 64 |
соответственно. |
|
|||||||
1. |
с) |
= |
3; с' — 4, |
так как ни 12, ни 47 не входят в покрытия для |
||||||
Уа или |
У3; |
|
с|= |
3 (12 входит, 47 — нет); |
|
|
|
|||
2. |
с\ |
-= |
2; |
|
|
|
|
|||
3. |
сз = |
3; |
|
с\= |
3 (47 входит, 12 — нет); |
|
|
|
||
4. |
cf = |
2; |
|
с*= 2 (оба оператора входят впокрытия для У2или У3). |
||||||
Как |
видно |
из |
рассмотренных |
примеров, Ьг |
всегда |
нехуже |
Ь4 |
|||
(с [< с |, |
і — 1, |
2, |
3, 4) независимо от выбора вариантов для покрытия |
|||||||
У2 и У8.
Спомощью рассуждений, аналогичных только что приведенным, нетрудно показать, что среди двух вариантов покрытия некоторого исходящего оператора У;- вариант bs не хуже варианта bt (bs^ b t), если выполняются два условия1:
1. |
LS< L ,; |
|
Bs) > 0, |
где Ls |
и |
Lt — длины |
вариантов |
||||||||
2. |
(Lt — Ls) — Р (Bt \ |
||||||||||||||
bs и bt (число производных операторов в этих |
вариантах); |
Bt |
и Bs — |
||||||||||||
множества операторов, заключенных в скобки в вариантах Ь, и |
bs со |
||||||||||||||
ответственно; |
Bt \ |
Bs — разность множеств |
Bt и |
Bs\ |
Р (Bt \ |
ß s) — |
|||||||||
число элементов в множестве Bt \ |
Bs. |
|
|
|
|
квазипорядка, |
|||||||||
Очевидно, |
что |
отношение |
bs ^ b |
t |
есть отношение |
||||||||||
которое рефлексивно (bs |
bs) |
и транзитивно |
(если |
bt и Ъ, <<; Ьг, |
|||||||||||
то bs sC. br). |
Будем также |
говорить, |
что |
bs |
и Ь( |
несравнимы, |
если |
||||||||
b„ ^ |
bt и b[ |
bs, |
и эквивалентны, |
если |
ös <; |
bt |
и bt ^ |
bs. |
|
|
|||||
Сравним для примера несколько вариантов из табл. 7-8. |
|
|
|||||||||||||
а. |
Ьв и Ь9: |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Lc = 6, |
7-9= 7, |
L e < L 9; |
|
|
|
|
|
|||||
(Lg —Le) — P (В0 \ В в) = (7— 6)—P ((23, 11, 13)\{11, 13))= 1 - 1 |
= 0; |
||||||||||||||
|
|
|
|
|
bß |
bg- |
|
|
|
|
|
|
|
|
|
б. bg и b7: |
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
|
|
7-e= 6, |
L7 = 6, |
Lg — L7; |
|
|
|
|
|
|||||
(L-i —Lg) —P (B7 \B g ) = (6—6) —73 ((47, |
11, 12)\{.l 1, |
13}) = |
|||||||||||||
|
|
|
' = ( 6—6)— P (47, |
12) = |
—2; |
|
|
|
|
|
|||||
|
|
|
|
|
b g ^ b 7. |
|
|
|
|
|
|
|
|
||
1 Строго говоря, первое условие вытекает из второго,- поэтому достаточно выполнения лишь условия 2.
151
Проверим обратное: |
|
|
|
|||
|
|
|
|
L7 — L(i, |
|
|
(LG- L |
7) - P ({ 1 1 , |
13)\(47, 11, 12}) = (6 —6) —Р ({13}) = — 1; |
||||
|
|
67 ^ Ьв |
. Варианты Ьй и 67 несравнимы. |
|||
в. |
62 |
и Ь4: |
|
|
|
|
|
|
|
ZLо — 4, |
— 4, |
7.о — I.j ] |
|
|
|
(Lj — L2) - P |
({47, |
1 2 j\Q ) = 0—2 = —2; |
||
|
|
|
|
ь2 4 =&4- |
|
|
Проверим обратное: |
|
|
|
|||
|
|
|
|
Lj ~ L2, |
|
|
|
|
(Lo— Lj) —Р (0 \{ 4 7 , 12}) = О—Р (0 ) = 0—0 = 0; |
||||
|
|
|
|
£ > J |
& 2 . |
|
г. |
Сравнение Ь21 |
и Ь24 |
показывает, |
что Ь2 1 0 Ь2 4 и ö2j- 0 ö 21> т. е. |
||
они эквивалентны.
Алгоритм сжатия таблицы вариантов очевиден. Сравнивая попарно варианты в пределах каждого массива У) (/ -- 1, . . . , т), оставляем только те варианты, которые ни разу не оказались хуже других. Если какая-либо пара вариантов из оставшихся эквивалентна, то доста точно оставить в таблице любой из них. Таким образом, в каждом мас сиве Yj (j = 1, . . . , in) после сжатия будут только несравнимые ва рианты. Сжатие табл. 7-8 приводит к табл. 7-9, в которой У7 и Y 3 содержат по одному варианту, а УС,— два варианта, £>10 и Ьг1. Од нако если в табл. 7-8 в Ьіг операторы 49, 23 и 13 были заключены в
скобки, то в табл. |
7-9 они без скобок, |
так как их нет в вариантах для |
|||||
Уі |
и Y 3. |
|
|
|
|
|
|
|
|
|
Таблица 7-9 |
|
Таблица 7-10 |
||
Результат |
первого сжатия |
таблицы |
Минимальное |
покрытие |
таблицы |
||
|
|
вариантов |
|
вариантов |
|
||
|
К, |
|
|
V, |
V, |
|
Y:, |
|
ь. |
friu |
Ьп |
fr14 |
by |
fr10 |
fr16 |
|
46 |
60 |
61 |
50 |
46 |
60 |
50 |
' |
(12) |
9 |
9 |
26 |
(12) |
9 |
26 |
|
19 |
47 |
49 |
22 |
19 |
47 |
22 |
|
|
(12) |
23 |
(12) |
|
(12) |
(12) |
|
|
|
13 |
|
|
|
|
152