Горбатов В.А. Фундаментальные Основы Дискретной Математики. Информационная Математика

§5.2. Методы оптимального размещения данных

411

/-графа по линейному мографу (будем считать мограф связным).

Т абли ц а 5.3

Запрещенная Способ преобразования

фигура

Расширение носителя Расширение сигнатуры

*i(2,3)

1(*2,*з)

г, (1,3)

2(* 1,хз)

*з(1,2)

3 (ц ,х 2)

*о(3,( 1,2))

1(*0, *1)

К4

*о(2,(1,3))

2(*о,*г)

*о(1,(2,4))

3(*о,*з)

* i(1.4)

1(*1,Х0)

к :

* 2(2, 4)

2(х2,х 0)

хз(3,4)

3(х3,* о)

*о(1, (2,3,4))

4(*i, (х2,х з,х 0))

*о(2, (1,3,4))

4(х2, (х1,х3, х0))

х0(3, (1,2,4)) 4(х3,(х1,х2,х0))

* i ( l,5)

l(x i,x 0)

Кь *а(2, 5)

2(х2,х 0)

*з(3,6)

З(х3,х 0)

*4(4,6)

4(Х4,Х0)

*о(1, (2,3,4, 5,6)) 5(х1,(х0,х 2))

*о(2, (1,3, 4, 5,6))

5(x2,(x0,xi))

*о(3, (1,2,4, 5,6))

6(х3, (х0,х 4))

*о(4, (1,2,3, 5,6))

*о((1,2, 5), (3,4,5))

6(Х4,(Х0,Х3)) -

Определим отношение упорядочения Ре на носителе мографа

такое, что (х,-, Xj) € Ре, если Е(х$ cE (ij) (одноэлементные слова

при этом не учитываем). Найдем множество минимальных эле

ментов Х\ отношения упорядочения Ре- Оставим в нем по од

ному элементу из тех, которые входят в одинаковые слова, а за

тем только такие элементы х,, удаление которых вместе с E(xi) не

делает мограф несвязным. (Можно показать, что таких элементов

всегда не более двух.) Пусть останутся элементы

х,- и хп. Зафикси

руем один из них, например, хп, как конечную вершину /-графа.

Удалим другой элемент х, из мографа и введем его в /-граф. Если

в /-графе уже есть вершины, то соединим предыдущую введен

ную вершину Xj дугой с х,-. Продолжаем этот процесс до тех пор,

пока в мографе не останется одна вершина хп. Поступаем с ней

аналогично.

Рассмотрим процесс семантического эквивалентирования мографа (см.

рис. 5.12) в линейный /-граф. Запрещенные фигуры для свойства линейности,

присутствующие в Ф„, приведены на рис. 5.19. Если критерием является ми

нимизация функционала ^(Фь), равного мощности носителя Фь, при условии

неувеличения мощности сигнатуры Фо, то можно применять только преобразо

вание, основанное на расщеплении элементов носителя. Семантическая таблица

имеет вид табл. 5.4.

412

Гл. 5. Прикладная теория алгоритмов

Т абли ца 5.4

Фг

Ф5

*в *7 Фв

* з ( 1, ( 2, 6 )) 1

* з ( 2, ( 1, 6))

1 1

* з ( 6 , ( 1, 2)) 1 1

* з ( 1. 2)

* в ( 2. 3)

* < ( 1, 3)

* 2(1, 5)

* 4(1,4)

*т(4, 5)

* 4(1, (3, 4))

* 4(3, (1,4))

1 1 1 1

* 4(4, (1,3))

Рис. 5.20

§5.2. Методы оптимального размещения данных 413

Рассмотрим покрытие к = {хз(2, (1, 6)), г<(1, (3, 4))}. Выполнение этих

преобразований в Ф„ приведет к линейному мографу Ф* (рис. 5.20, а). По

строим, следуя предложенному алгоритму, линейный /-граф, представляющий

Фь. Определим отношение упорядочения Р е (рис. 5.20,6). Минимальными его

элементами являются x i, х«, xg, х'3. Удаляя из рассмотрения xi или х4 со сло

вом М, приходим к несвязному мографу. Элемент х£ фиксируем как конечную

вершину /-графа. Вводим в /-граф вершину хв. удаляя этот элемент из Фь-

Затем снова строим отношение упорядочения Р е (рис. 5.20, в). Минимальными

элементами являются x i, х3, х4, х3. Первые три входят в одно множество слов;

выбираем элемент хз, остальные из рассмотрения удаляем. Вводим хз в /-граф

(рис. 5.20,г). Продолжая эту процедуру, строим /-граф (рис. 5.20, д).

Мограф Фа представляет систему инвертированных списков

для файла библиотечной информационной системы (см. рис. 5.13).

При использовании обычной списковой организации с линейной

функцией осмотра инвертированные списки (см. рис. 5.14, а) за

нимают 14 элементов памяти; при использовании оптимального

размещения (см. рис. 5.14, б) — 9 элементов. Таким образом,

экономия памяти на инвертированных списках составила прибли

зительно 35 %.

Если критерием являетсяминимизация функционала ^(Фь), равного мощно

сти сигнатуры Фь, при условии неувеличения мощности носителя Фа, то можно

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

Семантическая таблипа имеет вид табл. 5.5.

Т аб л и п а 5.5

Ф1 Фг

Фз

Ф4

Ф5 Фв

Ф7 Фв

l(xi,x3)

2(х3,х5)

1 1 1

6(хз,хв)

1 1

1(Х2,Х3)

1(х3, Xi)

3(14,15)

1(12,14)

4(х4 , Х7)

1 1 1

5(хг, Х7)

1(Х1,Х4)

Одним нз покрытий, определяющих минимальное решение, является не

минимальное (по числу преобразований) покрытие я = (l(x i, хз), 1(^2, х3),

1(хз, х*), 1(хг, xt), l( r i, Х4)}. Специальный граф для слова М (а все способы

расщепляют только его) приведение рис. 5.21, а. Раскраска его в три цвета опре

деляет минимальное расщепление M i: М[ = {xi, хг}, М" = {хз}, М[" = {х4};

после расщепления мограф становится линейным (рис. 5.21, б) и представляется

линейным /-графом (рис. 5.21, в).

Решение этой задачи позволяет в соответствии с построенным

/-графом так упорядочить записи файла библиотечной информаци

онной системы (рис. 5.22), что записи, имеющие идентичное значе

ние ключевого слова, сгруппированы в наименьшее число цепочек.

414 Гл. 5. Прикладная теория алгоритмов

Если в первоначальном файле (рис. 5.13) таких цепочек было 10

(для ключевого слова “математические методы” — 1 цепочка, для

ключевого слова “автоматизация” — 2 и т. д.), то в полученном

размещении (рис. 5.22) таких цепочек 8 (для ключевого слова “ма-

Рис. 5.21

Адрес

Фамилия И.О.

Хв

Ржевский В.В.

Хз

Макаров И.М./

ред.

Брейер М.

х 4

Свами М.,

Тхуласираман К.

Х7

Питерсон Дж.

Х2

Марчук Г.И.

XI Самарский А.А.

Рнс. 5.22

тематические методы” — 3, для остальных — по 1). Таким обра

зом, быстродействие при обработке файла в результате оптимиза

ции увеличилось на 20%. Для обоих критериев получено мини

мальное решение.

§ 5.3. Характеризация выходной связности

логических структур

Проектирование многовыходных логических схем в топологи

ческих базисах не отличается от проектирования одновыходных

схем, если допускается съем информации с элементов, не являю

щихся минимальными или максимальными; при этом накладыва

ется только одно ограничение — не расщеплять элементы графа,

взвешенные выходными буквами /,-. При проектировании мно

говыходных схем в функциональных базисах, как правило, реа

лизуемую систему булевых функций сводят к одной функции или

ищут пересечения единичных областей булевых функций и син

тезируют схемы по булевым функциям, описывающим эти пере

сечения. Окончательная схема представляет собой композицию

схем, реализующих поведение данных булевых функций на пере

сечениях рабочих областей, и схем-сборок, выводы которых совпа

дают с выходными каналами искомой схемы. В случае же, когда

единичные области не пересекаются, при использовании извест

ных методов имеет место несвязная реализация системы булевых

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

булевых функций вида

А = XiX2X3X4y X iX 2 X 3X4, / 2 = x1x2x3xi \/ X1XiX3Xi .

12 3 4

§5.3. Характеризация выходной связности структур

_____

415

Преобразуем мограф GM ({/«})) задающий эту систему

(рис. 5.23, а), в структурный мограф #({/,}) так, чтобы макси-

(1 , з, 4 )

(1 , 4 )

(1, 3, 4)

(1,2, 3)

*4-1

ХН

*з-

*4-1

* 3-Н

мальные элементы были взвешены

буквами, идентифицирующими вы -.

ходные каналы, и ни одна из вер

шин, не являющихся максимальным

элементом, не была взвешена выход

ной буквой fi. Структурный граф

Я (Ш ) изображен на рис. 5.23,5.

С помощью коалгебры графов прео

бразуем его в логическую схему

(рис. 5.23,в). Вершины мографа и

структурного графа, определяющие

многовыходную логическую схему,

будем раскрашивать в два цвета: вер

шины, взвешенные входными буква

ми Xi, Xi, белым цветом, вершины,

взвешенные выходными буквами

fi, — черным (на рисунках черному

Рис. 5.23 цвету соответствует штриховка).

При преобразовании мографа

GM ({/»}), задающего систему булевых функций, в структурный

граф #({/»}) на последний накладывается следующее ограниче

ние: максимальные элементы структурного графа, и только они,

должны быть взвешены выходными буквами которые при этом

преобразовании не расщепляются.

Систему булевых функций F(x) = {/;} представим в виде мо

дели

Фа = (M i, р, Si, S2, . . ., Sn),

где Ма = {m.i, тп2, ..., тпп, mn+i, ..., тпп+к}, Si С М'а, i = 1,

2, ..., n; р — одноместный предикат, разбивающий Ма на два

416

Гл. 5. Прикладная теория алгоритмов

подмножества:

_ J 0 на элементах тп,- при * = 1, 2, . . п,

Р ~ 1 1 на элементах mj при j = (n -f 1)..(n + fc).

Структурный граф H(F(x)) представим в виде модели

Фь = (Мь, <, д),

где

_ f 1, если из p(mt) > p(mj) следует тп,- > mj,

Р ~ 1 0 в противном случае.

При исследовании вопроса преобразования модели Фа в модель

Фь и построения многовыходного структурного графа следует рас

сматривать модели со следующими ограничениями:

1) если в модели Фа найдутся два слова, ца и цр, такие, что

ца С Ф/?, то эти слова заменяют одним словом ца;

2) если в слове имеются хотя бы две одинаковые буквы, т а и

т Ь {т а = т ь), то одну из них заменяют другой;

3) если в модели Фа найдутся хотя бы два слова, /х0 и цр,

такие, что

ца — а т г, цр = amt,

где p(mr) = p(mt) — 1, а состоит из букв т ,, р(т^) = 0, то одно

из этих слов заменяют другим.

Очевидно, для того, чтобы было можно частично упорядочить

буквы модели Фа, необходимо, чтобы мограф GM не содержал за

прещенных фигур Qx, Qb (см. рис. 3.52). В этом случае возможно

частичное упорядочение букв модели Qa, Qb без учета предиката

q в модели Фь-

Найдем запрещенные фигуры в мографе GM(F(x)), характе

ризующие фиксирование максимальных (минимальных) элемен

тов в соответствующем структурном графе H(F(x)) при преобра

зовании GM(F(x)) —)• H(F(x)). Для определенности будем фик

сировать максимальные элементы, которые соответствуют выход

ным каналам проектируемой логической схемы.

Условие частичного упорядочения букв модели Фа, в котором

учитываются заданные максимальные элементы, устанавливает

следующая теорема.

Теорема 5.3. Между буквами модели Фа = (Ма, р, Si,

S2, ..., Sn), мограф GM которой не содержит мографов Q\,

Qb, существует отношение частичной упорядоченности то

гда и только тогда, когда мограф GM не содержит модельных

подграфов Qe (рис. 5.24).

Сложность логических схем в основном определяется сложно

стью соответствующего структурного графа Н. Следовательно,

§5.3. Характеризация выходной связности структур

_____

417

структурная минимизация булевой функции / определяется рас

пределением запрещенных фигур Qa,, Qb в мографе GM(f), а

системы булевых функций (fi) — распределением запрещенных

Рис. 5.24

фигур Qx, Qb, Qe в мографе GM({fi}). Таким образом, мини

мальной логической схеме будут соответствовать те ДНФ булевых

функций, в которых необходимо произвести минимальное коли

чество расщеплений первичных термов для того, чтобы образо

вавшийся мограф был интерпретируем в категориях структурных

графов.

Рассмотрим точную структурную минимизацию булевой функ

ции /, которая сводится к покрытию семантической таблицы глу-

Интервалы Первичные

• рабочей области термы

Запрещенные

фигуры

Рис. 5.25

бины 2 (рис. 5.25) и, если необходимо, к раскраске графов, соот

ветствующих покрытиям второй таблицы.

Первая таблица формируется на основе покрытия таблицы

различий для практических булевых функций. Покрытие первой

таблицы порождает тупиковую ДНФ, которой соответствует мограф

GM. Преобразование его в частично упорядоченный, т. е. в ин

терпретируемый структурным графом Н, выполняется с помощью

покрытия второй таблицы. Рассмотрим пример.

П ример 5.1. Определим сложность абсолютно минимального структурного

графа (диаграммы), реализующего булеву функцию

/(х 1, х2, х3, х * ) !^ V(0, 1, 2, 4, 9, 11, 13)

и равного нулю на остальных наборах.

Максимальные

интервалы

14 В. А. Горбатов

418

Гл. 5. Прикладная теория алгоритмов

Выделим максимальные интервалы и построим для рассматриваемой функ

ции таблицу Квайна (табл. 5.6).

Т аб ли ц а 5.6

Номера

строк

Максимальные

интервалы

Единичные точки

0000

0001 0010

0100 1001

1011

1101

000-

2 0 0 -0

3 0 0 -0 1 I

-001

1 1

5 10-1 1

6 1-01 1

Подчеркнутая единица в таблице Квайна соответствует обязательному мак

симальному интервалу. (Максимальный интервал является обязательным, если

найдется единичная точка, принадлежащая этому и только этому интервалу.)

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

Находим тупиковые ДНФ заданной функции, покрывая столбцы Квайна

строками таблицы. Имеем два покрытия: первая, вторая, третья, пятая, шестая

строки и вторая, третья, четвертая, пятая, шестая строки. Этим двум покрытиям

соответствуют ТДНФ функции / вида

/'(х 1 , хг, х3, х*) = Х1Х3 Х4 V Х1Х3Х4 V Х1Х3 Х4 V x^Tjuy г 1 г??з ,

1 2 3 4 5

f"(x 1, Х2, хз, Х4) = Х1Х3Х4 VX1X2X4 V Xl Х3Х4 VX1X2X4 V Х2Х3Х4.

Первой ТДНФ соответствует мограф, изображенный на рнс. 5.26, а. В этом

графе имеются циклы нечетной длины с циклической перестановкой весов

(1, 3, 5) (1, 3, 5)

следующего вида:

Qai =

Ялз =

хг(4, 5), x3(5, 3), x4(3, 4)

x i(l, 2), x 2(2, 5), x3(5, 1)

x4(l, 2), хг(2, 5), x3(5, 1)

Первой ТДНФ соответствует семантическая таблица — табл. 5.7.

§5.3. Характеризация выходной связности структур

419

Т абли ц а 5.7

* 1 (1 , 2 )

*2 (4 , 5 )

*2 (2 , 5)'

*з(3,5)

*з(1 ,5)

*<(3,4)

*4(1,2)

0 1 0

1 0 1 0

0 1

1 0

Одним из минимальных покрытий является ж = {*2 (4, 5), £2(2, 5)}. По

скольку преобразования, входящие в него, расщепляют лексикографически

одинаковые буквы, строим граф на словах {2, 4, 5} (рис. 5.26,5). Этот граф

раскрашивается в два цвета: {2, 4} и {5}-

Следовательно, достигнуто минимальное расщепление букв. После штри

ховки буквы xt в пятом слове получаем ДНФ, интерпретируемую в категориях

диаграммы Хассе со сложностью 7 (рис. 5.26, в):

f'(x 1, Х2, Хз, Х4, г£) = Г1Х3Х4 V Х1Х2Х4 VX1X3X4 VX1X2X4 VXlX^X3.

Рассматривая аналогично остальные покрытия и распределение запрещен

ных фигур в мографе второй тупиковой ДНФ, получаем, что найденная упоря

дочиваемая ДНФ является абсолютно минимальной. Следовательно, сложность

диаграммы, реализующей эту функцию, также равна 7 (рис. 5.26,г).

Приведем точное решение задачи структурной минимизации

системы булевых функций, основанное на использовании зап

рещенных фигур преобразования мографа в диаграмму с фик

сированными максимальными элементами. Оно заключается в

выполнении следующих этапов.

1. С помощью одного из известных методов формируют множе

ство многовыходных простых импликант (МПИ) (многовыходных

Максимальных интервалов). Множество точек пространства, вхо

дящих в единичные области булевых функций /1, Д , ..., Д и

Образующих гиперкуб, называется многовыходным (к-выходным)

интервалом функций Д , /2, ..., Д.

Многовыходной интервал булевых функций Д , Д,..., Д назы

вается многовыходным максимальным интервалом, если не най

дется многовыходного интервала этих функций, включающего его.

Конъюнкция, соответствующая многовыходному интервалу буле

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

импликантой.

2. Строят импликантную таблицу Квайна, в которой каждой

строке соответствуют МПИ, столбцу — конституенты единицы

(Или импликанты) исходных булевых функций fi(X) € F(X). При

Этом конституента единицы (импликанта) столько раз входит в

таблицу, сколько функций принимают на ней значение единица.

3. Находят покрытия столбцов строками импликантной табли

цы. Таким образом определяются ТДНФ системы булевых функ

ций.

4. Для каждой ТДНФ системы булевых функций, которой со

ответствует модель Фа, строят решетчатую ДНФ (РДНФ) системы

булевых функций минимальной сложности, т. е. осуществляют

цреобразование Фа —> Фь.

420

Гл. 5. Прикладная теория алгоритмов

5. Из всех РДНФ системы булевых функций выбирают РДНФ

минимальной сложности. Далее строят многовыходной структур

ный граф Н.

Для того чтобы удалить все запрещенные фигуры, построим

семантическую таблицу Д, каждой строке которой взаимно од

нозначно соответствует буква (в скобках указываются идентифи

каторы двух слов, в которые эта буква входит при образовании

запрещенной фигуры), а столбцу — одна из запрещенных фигур

Qa , Qfii Qei

{

1, если буква, соответствующая г-й строке, входит

в j -ю запрещенную фигуру,

0 в противном случае.

Строкам соответствуют буквы модели тгц С Ма, для которых

p(m,i) = 0. Тогда покрытие столбцов строками в матрице R со

ответствует множеству букв, которые необходимо расщепить при

преобразовании Фа -4 Фь.

Проиллюстрируем точный метод минимизации системы буле

вых функций с учетом их теоретико-структурных свойств.

П ример 5.2. Пусть задана система булевых функций F(X) =

fi(X), fs(X), ft(X)}, зависящая от пяти переменных (табл. 5.8). Выделим

все МПИ, затем строим таблицу Квзйна н в результате получаем две ТДНФ

Т абли ц а 5.8

Xi ха

хг XI

h h h

0 0

0 1

0 0 0 1

0 1 0 1

0 1 1

0 0 0

0 0 1

0 0 0 1

1 1 0

0 1

1 0

0 1

0 1 1

1 0

0 1

1 1

1 0

0 1

1 0

0 0 0

0 0

0 1

1 0

0 1

1 1

0 0

1 0

0 0

0 1

1 0

1 0 1

0 1 1 1

1 0

1 1

0 0

1 1

1 0 0

1 1

1 0 0

0 1 1

1 1 1

1 1

1 1 1

1 1

Горбатов В.А. Фундаментальные Основы Дискретной Математики. Информационная Математика

Подождите немного. Документ загружается.