Презентации лекций / Презентация лекции 16 ДМ 20
.pdf
Пример построения упорядоченной бинарной диаграммы решений функции
Функция
( , , ) = (10011101)
01
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
0 |
1 |
|
|
|
0 |
|
|
1 |
|
||||
|
|
|
|
|
|
|
|
|
|
|
|
|||
0 |
1 |
0 |
|
1 |
0 |
1 |
0 |
1 |
||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
1 |
|
0 |
|
0 |
|
1 |
|
1 |
|
1 |
|
0 |
|
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Сольем все листья с меткой 0 воднувершину с меткой 0
Сольем все листья с меткой 1 воднувершину с меткой 1
01
|
|
|
|
|
|
|
|
|
|
|
|
|
|
0 |
1 |
|
|
0 |
|
1 |
|
|
|
|
|
|
|
|
0 |
1 |
0 |
1 |
0 |
1 |
|
|
|
10
0 1
Получим однуиз упорядоченных бинарных диаграмм решений функции
1
2
11
Пустьдля переменныхзафиксированпорядок: ( ), ( ),…, ( )
Упорядоченнаябинарнаядиаграммарешенийотносительнопорядка
-этоориентированныйграф безцикловс одним корнем
-(вершиной,в которуюдугиневходят),в котором:
1
2
Существуют |
|
|
Остальные(внутренние) |
|
|
|
вершины помечены |
||
ровнодвевершины, |
|
|
||
|
|
переменными. |
||
в которые дуги |
|
|
||
|
|
Из каждой из них |
||
тольковходят |
|
|
||
|
|
выходит по дведуги, |
||
|
|
|
|
|
|
|
|
|
однаиз которых |
|
|
|
|
помечена 0,другая -1 |
|
|
|
|
|
|
|
|
|
|
|
1 |
|
|
0 |
0 |
1 |
|
|
|
стоки
Порядок, в котором переменныевстречаются на любомпути из корня в сток,совместимспорядком
( ) |
< |
( )
( ) |
< |
Говорят,чтоУБДР реализуетфункцию ( , ,…, ), |
( ) |
||
если для каждогонабора |
, |
,…, |
|
|
|
|
|
значенийпеременныхветвьдерева,соответствующаяэтомунабору, |
( ) |
||
завершаетсястокомс меткой |
, ,…, |
|
|
|
|
Числовнутреннихвершин– сложностьУБДР 12 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
1 |
|
|
|
|
|
|
|
Примеры УБДР |
|
|
|
|
|
|
2 |
||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
Пример1: |
|
|
|
|
|
|
Пример2: |
|
|
|
|
|
|
|||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
0 |
|
1 |
|
0 |
|
0 |
0 |
0 |
0 |
1 |
|
0 |
|
0 |
0 |
0 |
|
|
|
|
|
|
|
||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
|
|
|
0 |
|
0 |
1 |
0 |
|
|
|
0 |
|
0 |
1 |
0 |
|
1 |
0 |
|
0 |
|
1 |
0 |
1 |
1 |
0 |
|
0 |
|
1 |
0 |
0 |
0 |
|
1 |
|
0 |
|
1 |
1 |
1 |
0 |
1 |
|
0 |
|
1 |
1 |
1 |
|
|
|
1 |
|
0 |
0 |
0 |
|
|
1 |
|
0 |
0 |
0 |
||
|
|
|
|
|
|
|
|
|
||||||||
0 |
|
1 |
|
1 |
|
0 |
1 |
1 |
0 |
1 |
|
1 |
|
0 |
1 |
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
0 |
|
1 |
|
1 |
|
1 |
0 |
1 |
0 |
1 |
|
1 |
|
1 |
0 |
1 |
|
|
1 |
|
1 |
1 |
1 |
|
1 |
|
1 |
1 |
1 |
||||
|
|
|
|
|
|
|
|
|
||||||||
УБДР функции ( , |
, |
) |
= |
00110111 |
|
УБДР функции ( , |
, |
) |
= |
00010111 |
|
|||||
|
относительнопорядка |
, |
, . |
|
относительнопорядка |
, |
, . |
|
||||||||
|
|
СложностьУБДР равна4 |
|
|
|
СложностьУБДР равна4 |
|
13 |
||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2 |
|
|
0 |
|
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
0 |
|
|
|
|
0 |
|
||||
|
|
|
|
|
|
|
|
1 |
|
|
|
1 |
|
||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||
0 |
1 |
|
|
0 |
|
1 |
0 |
|
1 |
|
0 |
0 |
|
1 |
1 |
||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
0 |
||||
1 |
0 |
1 |
0 |
1 |
|
|
|
|
|
|
|
|
|
|
|
||
0 |
1 |
|
|
0 |
|
|
|
|
|
0 |
|
||||||
1 |
0 |
1 |
|
|
1 |
0 |
1 |
|
|||||||||
|
0 |
|
|
|
|
|
0 |
1 |
|
||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
|
0 |
|
1 |
|
|
|
|
0 |
|
1 |
|
|
|
0 |
|
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
|
СложностьУБДР 1 равна7 |
|
|
СложностьУБДР 2 равна6 |
|
СложностьУБДР 3 равна5 |
|||||||||||
|
|
|
|
Все триУБДР реализуютфункцию ( , , ) = (10011101) |
|
|
|
||||||||||
|
|
|
|
|
|
|
УБДРсравниваютпосложности. |
|
|
|
|
|
|||||
|
УБДР,имеющаясредивсехУБДР,реализующихфункцию,наименьшуюсложность, |
|
|||||||||||||||
|
|
|
|
|
называется минимальнойУБДРфункции |
|
|
|
|
14 |
|||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
1
2
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||
|
|
|
|
|
|
|
|
|
|
0 |
|
1 |
0 |
1 |
0 |
|
1 |
0 |
1 |
|
|
|
|
||||||
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
15
1
2
УБДР – сокращенная, если
Улюбойвнутреннейвершины |
|
|
|
Нет такойпары внутреннихвершин и , |
|
|
|
||
|
|
|
для которыхподдиаграммыс корнями |
|
|
|
|
||
0-сыни1-сыннесовпадают |
|
|
|
|
|
|
|
и являютсяизоморфными |
|
|
|
|
|
Поддиаграммыизоморфны, если они взаимнооднозначноотображаются
друг на друга с сохранениемвсехметок
УБДР является |
КУБДР не применимо |
|
ни правило удаления, |
||
сокращенной |
||
ни правило слияния вершин |
||
|
16
-йшаг
Применимпоследовательноковсемвершинамсметками( ) правилоудаления(вершиныможноперебиратьв произвольномпорядке),
азатем–правилослияния(еслиэтовозможно)
-йшаг
ПустькначалуэтогошагапостроенанекотораяУБДР.
Применимпоследовательноковсемвершинамсметками( ) правилоудаления(вершиныможноперебиратьв произвольномпорядке),
азатем–правилослияния(еслиэтовозможно)
Позавершении ( − )-гошага получимсокращеннуюУБДР.
1
2
Построим сокращенную УБДР для функций:
1.( , , ) = (10011101)относительно порядка , ,
2.( , , ) = (10011101)относительно порядка , ,
3.( , , ) = (00001111) относительно порядка , ,
17
1
2
Описанный выше алгоритм строит сокращенную УБДР, которая реализует ту же функцию, что и исходная УБДР
Эта сокращенная УБДР является приданном порядке
переменныхединственной 
(сточностью до изоморфизма) и минимальной (т.е. онаимеет наименьшую сложность среди всех УБДР данного порядка)
18
Функции, реализуемые в вершинах УБДР
( , , )
01
|
|
|
|
|
, |
=(0, |
, ) |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
, |
=(1, |
, |
) |
|
|
||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||
|
|
|
|
|
|
|
|
|
0 |
|
1 |
|
|
0 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
1 |
|
|
|
|
|
|
|
|
|
|||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
|
|
= 0, |
=(0,0, ) |
|
|
|
|
|
|
|
|
|
|
|
|
|
= |
1, |
= (1,1, ) |
|
|||||
|
|
|
|
|
|
|
|
|
|
|
0 |
1 |
0 |
1 |
0 |
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||
|
|
|
= 1, |
=(0,1, ) |
|
|
1 |
0 |
|
|
|
|
|
|
|
|
|
|
|||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
= |
0, = (1,0, ) |
|||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
0 1
01
|
|
|
|
|
УБДР |
функции |
|
1 0 |
0 |
1 |
( |
, |
, ) |
= (10011101) |
|
|
|
|
|
Поддиаграмма |
|
|
|
|
0 |
|
1 |
с вершиной |
|
|
|
1
2
19
-йшаг Ищемвспискепеременных , ,…, первую,откоторой зависитсущественно,и
помечаемееименемкорень.
Дляэтогоищемнаименьшеезначение,прикотором… ≠ ….Переменная -искомая.
Дляфункции … путемсравненияееостаточныхфункцийищемпервуювсписке
переменную , откоторой … зависитсущественно.Извершины,помеченной ,
выпускаемдведуги,помеченные0и1,ввершины,помеченные .Вершина,вкоторую ведетдуга0,соответствует ….Вершина,вкоторуюведетдуга1,соответствует ….
|
|
|
|
-йшаг
Пустькначалуэтогошагадлявсехразличныхостаточныхфункций ,…, ,существенно
зависящихот , построенывершины.Длякаждойизэтихфункцийвыпишемдвеостаточные функции ,…, , и ,…, ,.Выберемизмножестваэтихфункцийразные,идлякаждойиз
|
|
|
|
нихпостроимвершину,помеченнуюименемпервойвсписке ,…, переменной , от которойэтафункциязависитсущественно.Проведемсоответствующиедугииз в .
1
2
… ,…,
=
,…,, ,…,
-остаточнаяфункция
ПостроимУБДР относительнопорядка
, , , :
|
1) ( , |
, |
, ) |
= |
|||
|
|
|
|
|
|
|
|
|
|
|
1 |
|
|||
|
2) ( |
, |
, |
, |
) |
= |
|
|
|
|
|
|
|
||
20