Горбатов В.А. - Фундаментальные основы дискретной математики. Информационная математика - 2000 (1019108), страница 75
Текст из файла (страница 75)
Это отношение подчинения <5) х используется для характеризации циклических мографов. «, 4, 5) ™ «. 3, 4) Принцип локальности выполняется для свойств линейности и ацикличности при г отношении Р„' и лля свойства цикличности при отношении Р„. 3 5.2. Меьчоды оптимального размещения данных 411 410 Гл. 5. Прикладная теория алгоритмов Нетрудно доказать следующее утверждение. Утверждение. )апрещгнными фигурами для классов допуспзимосгпи мографов являются следующие мографм: 1) для свойства линейносгли и отношения подчинения Р)— оз иК4; 2) для свойства цикличности и отношения подчинения Рй К41 3) для свойства ацикличноспзи и отношения подчинения Р( — Яз, К4, Кб. Мографы Яз, Ке, Ке, Кб приведены на рис.
5.18. 52 (1, 2) Я (2, 3) (1, 3) (2) о 3) Хз (1, 5) (3, 6) 3. 4) 4, 5, 6) (2, 4) (3, 4) (2, 5) о г (4. 6) Рнс. 5.13 Способы преобразования этих запрещенных фигур в разрешенные заключается либо в расщеплении элемента носителя х и в соответствующем разбиении множества слов Е(х), в которые он входил, на два множества, Е1(х) н Ез(х) (обозначим этот способ как х(Е), Ез)), либо в расщеплении слова М; на два, М и Мо, с соответствующим распределением элементов по этим словам (обозначим как з(М, М;")).
Способы преобразования запрещенных фигур в принятых обозначениях объединены в табл. 5.3. Можно показать, что эти способы базисные, т. е. любой другой способ преобразования является суперпозицией этих способов. Для модели в целом данные способы преобразования запрещенных фигур являются неоднозначными. Семантическое эквнвалентирование мографа ьро в мограф (рь с заданными свойствами допустимости осуществляется с помощью обычной процедуры: строим семантическую таблицу; находим покрытия; оцениваем эти покрытия с помощью построения специальных графов и их раскраски. В результате получаем мограф, обладающий заданным свойством допустимости.
По нему строим соответствующий У-граф. Рассмотрим подробнее алгоритм построения линейного у-графа по линейному мографу (будем считать мограф связным). Тоблнва 5.3 Сносов вреобраэования Заврешенная фигура Расширение сигнатуры Расширение носителя хг(2, 3) хз(1,3) аз 1,2 Цхз, хз) 2(хь хз) 3 Хг,хз Хе(3,(1,2)) хэ(2,(1, 3)) а'о 1, 2,4 Цхо,хз) 2(хо,хз) 3 хе,хз Цхы хе ) 2(х2, хо) 3(хз,хо) 4(хз,(хз,хз,хо)) 4(хз,(хз,хз,хе)) хг(1, 4) хз(2, 4) хз(3,4) хэ(1,(2,3,4)) хэ(2,(1, 3, 4)) хе 3, 1,2,4 4 хз, хг,хз,хо хз(1, 5) хз(2, 5) хз(3,6) хь(4,6) хо (1, (2, 3, 4, 5, 6)) хе (2, (1, 3, 4, 5, 6)) хе(3, (1,2,4,5,6)) хо (4, (1, 2, 3, 5, 6)) Цхы хо 2(хз,") 3(хз,хо) 4(хь,хо) 5(хп (хо,хз)) 5(хз,(хэ,хз)) 6(хз,(хо,хь)) 6(хь,(хэ,хз)) Определим отношение упорядочения РЕ на носителе мографа такое, что (х;, х ) б Ре, если Е(х;) сЕ(х;) (одноэлементные слова при этом не учитываем), Найдем множество минимальных элементов Х1 отношения упорядочения Рк.
Оставим в нем по одному элементу из тех, которые входят в одинаковые слова, а затем только такие элементы х;, удаление которых вместе с Е(х() не делает мограф несвязным. (Можно показать, что таких элементов всегда не более двух.) Пусть останутся элементы х( и х„. Зафиксируем один из них, например, х„, как конечную вершину у-графа. Удалим другой элемент х; из мографа и введем его в у-граф. Если в у-графе уже есть вершины, то соединим предыдущую введенную вершину х дугой с х;.
Продолжаем этот процесс до тех пор, пока в мографе не останется одна вершина х„. Поступаем с ней аналогично. Рассмотрим вровесс семантнчесвого эввивалеятнроваиия мографэ (см. рис. 5.12) в линейный у-граф. Заврпяенные фигуры лля свойства лннейности, врисутствуюшие в Ф„лривелены на рис. 5.19. Если врнтернем является минимиэавия фуивниоиала (о(Фь), равного мошиостя носителя Фь, ври условии иеувелнчення мошиости сигнатуры Фь, то моиио врименять тольао вреобрааование, основанное на расшеллении элементов носителя. Семантичесвая таблива шееет вив табл.
5.4. 412 (1, 2) (1, 5) б) х х (2, 5) Чзз х (4) б) б) 15 (1, 5) (1, 4) (4, 5) Х х 4) 4) Ряс. 5.19 Таблица 5.4 5) х х х х х х д Рис. 5.20 Гл. 5. Прикладная теория алгоритмов а 6 6 6 6 -9-6 55.2. Методы олтимальнага размен(гнил данных 413 Рассмотрим покрытие зг = (хз(2, (1, б)), х»(1, (3, 4))). Выполнение этих преабраэозапий а 'т'» приаедет а лкяейнаму мографу Фь (рис.
5.20,а). Построим, слелуя предложенному алгоритму, лянейный у-граф, кредстааляюшнй Фь. Определим отношение упорядочения Ра (рис. 5.20,6). Минимальными его элементамн яаляются хм х», хз, хз. Удаляя на рассмотрения хз илн х» са слоаом М, приходим к несаяаному мографу. Элемент хз фиксируем каа конечную першину у-графа. Взодям а у-граф вершину хз удаляя этот элемент нэ Фь. Затем снопа строим отношение упорядочения Рл (рис. 5,20, о).
Минимальными элементамн яаляются хм хз, х», хз. Первые три аходят а одно множестао слов; зыбираем элемент хз, остальные па рассматреняя улаляем. Ваоднм хз а у'-граф (рис. 5.20,г). Продолжая зту процедуру, строим у-граф (рис. 5.20,д). Мограф Ф, представляет систему инвертированных списков для файла библиотечной информационной системы (см. рис. 5.13). При использовании обычной списковой организации с линейной функцией осмотра инвертированные списки (см. рис. 5.14, а) занимают 14 элементов памяти; при использовании оптимального размещения (см.
рис. 5.14,6) — 9 элементов. Таким образом, экономия памяти на инвертированных списках составила приблизительно 35%. ясли зри теряем яэляезсямияимизацня функционала (а( т ь) разного мошности сигнатуры фь, ари услаани неуаеличения машности носителя Ф», то можно применять только ареабрааоааняя эакрешеняых фигур, расшекляюшие слака. Семантическая таблица имеет зид табл. 5.5. Таблица 5.5 Одним нз покрытий, олределяюшнх минимальное решение, является немнннмальное (па числу креабразоааний) покрытие х = (1(хм хз), 1(хз, хз), 1(хз, х»), Цхз, х»), 1(хм х»)). Специальный граф для слова М (а асе способы расшеклтат только ега) приведен на рис. 5.21, а. Раскраска его а трн цаета определяет митчмальное расшепление М~. .М,' м (хм хз), Ма = (хз), Мо' ю (х,); после расшекления мограф станоаится линейным (рис.
521, 6) и кредстааляется аинейным у-графом (рис. 5.21, е). Решение этой задачи позволяет в соответствии с построенным У-графом так упорядочить записи фаила библиотечной информационной системы (рис. 5.22), что записи, имеющие идентичное значение ключевого слова, сгруппированы в наименьшее число цепочек. 414 К И, 2, З) (д, 4) (2) бй в л в я г х Рис. З.21 Рис. 5.23 з в Гв. 5. Прикладная теория алгоритмов Если в первоначальном файле (рис. 5.13) таких цепочек было 10 (для ключевого слова вматематические методы" — 1 цепочка, для ключевого слова "автоматизация" — 2 и т.
д.), то в полученном размещении (рис. 5.22) таких цепочек 8 (для ключевого слова "ма- тематические методы" — 3, для остальных — по 1). Таким обра- зом, быстродействие при обработке файла в результате оптимиза- ции увеличилась на 20%. Для обоих критериев получено мини- мальное решение. 3 5.3.
Характернзацни выходной связности логических структур Проектирование многовыходных логических схем в тополагических базисах не отличается от проектирования одновыходных схем, если допускается съем информации с элементов, не являющихся минимальными или максимальными; при этом накладывается только одно ограничение — не расщеплять элементы графа, взвешенные выходными буквами Д.
При проектировании многовыходных схем в функциональных базисах, как правило, реализуемую систему булевых функций сводят к одной функции или ищут пересечения единичных областей булевых функций и синтезируют схемы по булевым функциям, описывающим эти пересечения. Окончательная схема представляет собой композицию схем, реализующих поведение данных булевых функций на пересечениях рабочих областей, и схем-сборок, выводы которых совпадают с выходными каналами искомой схемы.
В случае же, когда единичные области не пересекаются, при использовании известных методов имеет место несвязная реализация системы булевых функций. Рассмотрим следующий пример. Пусть задана система булевых функций вида 25.3. Ха актеригация вьдвос)ноа свягиости структур 415 Преобразуем мограф длм((Я), задающий эту систему (рис. 5.23, а), в структурный мограф Н(1Я) так, чтобы макси- мальные элементы были взвешены буквами, идентифицирующими вы-, ходные каналы, и ни одна из вершин, не являющихся максимальным д элементом, не была взвешена выход- ной буквой Д.
Структурный граф г„ Н((Я) изображен на рис. 5.23,б. С помощью коалгебры графов преобразуем его в логическую схему «д Уг (рис. 5.23,в). Вершины мографа и вг структурного графа, определяющие многовыходную логическую схему, будем раскрашивать в два цвета: вер- 4 шины, взвешенные входными буквахг ми х;, У;, белым цветом, вершины, хв взвешенные выходными буквами в уд, — черным (на рисунках черному цвету соответствует штриховка). При преобразовании мографа д'~((Я), задающего систему булевых функций, в структурный граф Н((Я) на последний накладывается следующее ограничение: максимальные элементы структурного графа, и толька они, должны быть взвешены выходными буквами Д, которые при этом преобразовании не расщепляются.
Систему булевых функций Р(х) = (Я представим в виде модели )Рв = (Мв| Р 'Чь Нь 5в) где М, = (г)гд, пгг, ..., т„, ггг„+д,..., гя„+д~, ад С М,', г = 1, 2, ..., п; р — одноместный предикат, разбивающий М, на два $5.3. Характеризацил еыходноа связности структур 417 Гл.б. Прикладная теория алеоритмое 416 подмножества: )( О на элементах гп; при ь = 1, 2, ..., и, 1(1 на элементах гп при у' = (и+1)..., (п+ )с).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
