Горбатов В.А. - Фундаментальные основы дискретной математики. Информационная математика - 2000 (1019108), страница 59
Текст из файла (страница 59)
1. Выделяем остов могрвфа по матрице смежности фиксацией около диагональных единичных элементов: хт(1,2) хт(3,6) хе(3,4,$) хе(2,6) хь(6,6) Ць(1, 4) О О 1 О 1 Π— 1 1 1 О О 1 — О 1 1 1 1 Π— 1 О О 1 1 1 — О 1 О 1 О О 326 Гл.4. Теория формальных грамматик и агтомотог Обозначим ребра мографа как (хт(З, 6), х4(2, 6)) = а, (хв(5, 6), хз(3, 4, 5)) = у, (хт(З, 6), хв(5, 6)) = Ь, (хь(1, 2), х4(2, 6) ) = д, (хь(1, 2), хь(1, 4)) = с, (хз(3, 4, 5), хв(1, 4)) = р, (хт(3, 6), хз(3, 4, 5)) = И, (х4(2, 6), хв(5, 6)) = е. Цикломвтическая матрица рассматриваемого примера имеет вид Хорды Освод а Ь с И г у д р 1 0 0~1 1 1 0 0 т 0 1 0)1 0 1 0 0 рв ° 0 0 1~0 1 1 1 1 рв 3.
Применением 2" — и — 1 раз операции сложения по модулю 2 циклов выделяем все циклы мографа. Каждый выделенный цикл проверяем нв условие образования запрещенной фигуры типа А или Б. Базисный цикл рт является запрещенной фигурой Ям а базис- ный цикл рз — запрещенной фигурой Яз. Проанализируем остальные циклы на предмет образования ими запрещенных фигур: рь9рт=Р4 р44+11001000~ цикл р4 является запрещенной фигурой Я4, РьЩРз=рв Рв 4+10110011, выделенный цикл является запрещенной фигурой Яэ, Рт ьв Рз = Рт Рв 4-ь О 1 1 1 1 О 1 1, РгЮРт®Рз = Рь ВРв = Рт, Рг+41 1 10 01 11, циклы рм рв и рт пе являются запрещенными фигурами, так как они имеют четную длину.
Находим пары внешне неустойчивых вершин относительно но- сителя каждой запрещенной фигуры. В нашем примере такой па- рой относительно носителя запрещенной фигуры Яь = (хт(3, 6),хз(6, 5), хз(5, 3)) бУДУт веРшины и(х4), и(х4).
После ДобввлениЯ слов (хт, хз, хв) и (х4, хв, х4) фигура Яь неустойчива, и достаточно будет расщепить только х4(2, 6) (см. табл. 3.9): и(хь) < о(хз) < о(хв)> о(хь) < и(х4)1 о(хз) < и(хь) < и(хв)~ о(хз) < и(хт)> о(хз) < и(хв) < и(хт) о(хз) < и(хв) < о(х4) и(х4) < о(хв) < и(хт) о(х~~) < о(хв) < о(х4) 34.Т. Синтез логических ст укту в толологичгскиг баэисах 327 Рассмотрим фактическое построение структурного графа Н по интерпретируемому могрвфу 6~. В случае несложных мографов такое преобразование можно реализовать с помощью операции взятия двойственной структуры, как зто делалось выше. В сложных случаях объем вычислений возрастает настолько, что целесообразно применять частотный анализ мографов и на его основе строить Н.
Рассмотрим этот метод построения Н по мографу См. Буквы, соответствующие минимальным или максимальным элементам диаграммы, будем называть крайнини. Если количество минимальных (максимальных) элементов, покрываемых (покрывающих) одними и теми же вершинами (одни и те же вершины), не меньше 2, то соответствующие им буквы называются крайними второго рода, в противном случае — край- кими первого рода.
Т е о р е м а 4,4. Если буква а является крайкей нерв ого рода, то Уа = ~ Л~ Хи = Л~ Л~ = О~ 4 Ф у~ 41 лл = д~ с~ (4.12) каждая буква 6 Е Я 1 = д, е, ..., к) соответствует вершине, яокрываюиьсй и(а) (рис. 4.43, а) аь ад ав ав а б Рнс. 4.43 Теорема 4.5. Если буквы аь, ат,..., а„являются крайкими второго рода, то (Уаь(ь' 6 (1, 2, ..., я))) (ВЬ,„, 6Р, ..., Ьт(сг, 13> ..., у 6 6 (1,2, ",р))) (У; = Е У.,ь,), 1= Р-т (ьуЬЯ б (1, 2, ..., р1))(Лаг, а„, ..., аб(й, я, ..., С 6 6 (1, 2, ..., и,))) (Дл = ~~ь уввь )~, (4.13) выг,т...,б 328 Гл.4. Теория формальных грамматик и автоматов ~„„= О, й ф 1, lс,1 = 1, 2, ..., и, 1ь„з, = О, дс' Ф д', дс',р = = 1, 2,..., р, гдг каждая буква Ьз (у б (1, 2, ..., р)) еэегшиаает вершину, покрывающую соотагтстаующис минимальныг элементы диаграммы (рис.
4.43, б). Замечание. Теоремы, двойственные теоремам 4.4, 4.5, формулируются аналогично; слово "покрывающие" заменяется словом "покрываемые" ц "минимальные" — словами "максимальные", остальное остается без изменения. Здесь топология синтезируемой диаграммы (структурного графа) однозначно с точностью до применения операции взятия двойственной структуры определяется частотными соотношениями, элементы которых являются элементами частотной матрицы отношений Р = дт(См) х д(См) В общем случае, когда покрывающие вершины находятся в различных ярусах, что возможно при различной длине путей, частотные соотношения, определяющие топологию синтезируемой поддиаграммы, будут более сложными и элементами их будут частоты вершин, принадлежащие более чем двум ярусам.
Сечением структурного графа называется множество попарно несравнимых вершин, через которые проходят все кути. Условия поиска крайних букв первого и второго родов являются необходимыми, так как этим условиям могут удовлетворять как искомая совокупность букв, покрывающих найденные буквы ад, ат, ..., а„, так и совокупность букв, сравнимых с ад, аг, ..., а„, но не покрывающих их. В силу локальности соотношений (4.12), (4.13) поиск крайних букв необходимо осуществлять локальным перебором по всем сечениям диаграммы.
После нахождения покрывающих вершин построенные на этом шаге поддиаграммы представляются в виде гамаков с точкой разделения в покрывающей вершине с последующим свертыванием каждой из них в эту вершину. Известно, что частотная матрица отношений однозначно определяет интерпретируемый в категориях диаграмм мограф СМ и однозначно с точностью до применения операции взятия двойственной структуры — проектируемую диаграмму, поэтому при проведении проектирования на языке частотных матриц отношений свертывание гамака в вершину и зю являющуюся его максимальным элементом, означает разделение частот букв, сравнимых с т(и ) (т. е. тех букв т;, у которых у, .„ф О), на число путей, содержащихся в свертываемом гамаке, и вычеркиванием строк (столбцов), соответствующих буквам свертываемого гамака, за исключением т(о,„).
При этом полученная частотная матрица отношений описывает еше не построенный структурный граф. Алгоритм преобразования См -ь Н состоит из следующих шагов. 14.7. Синтез логических структур а топалогических базисах 329 1. Определяем все обобщенные буквы первого рода. Стягиваем гамаки, соответствующие найденным буквам, в вершину. 2. Определяем все обобщенные буквы второго рода. Стягиваем гамаки, соответствующие этим буквам. 3.
Найдена ли хотя бы одна обобщенная буква первого или второго рода? Если да, переходим к выполнению и. 1, в противном случае — к п. 4. 4. Находим множества букв каждое из которых удовлетворяет одному из условий (4.12), (4.13~. Линейно упорядочиваем найденные множества в виде списка. 5. Рассматривая первое множество букв в построенном (последнем) списке и полагая, что она взвешивает соответствующую поддиаграмму в проектируемом структурном графе, строим эту поддиаграмму. Свертываем полученные гамаки.
6. Определяем буквы, соответствующие вершинам, покрывающим максимальные элементы построенных паддиаграмм, используя пп. 4, 5. Если при выполнении пп. 4, 5 не выполняется ни одно из соотношений (4.12), (4.13), то последнее наше предположение неверно. Рассматриваемое множество букв и соответствующую ей поддиаграмму вычеркиваем, восстанавливаем предыдущую частотную матрицу отношений и переходим к и.
5. Если хотя бы одно из условий (4.12), (4.13) справедливо, то выполняем п. 6. В результате локального перебора поддиаграмм по сечениям строим структурный граф. Предлагаемый алгоритм эффективно реализуется на ЭВМ в силу арифметического характера преобразований. Построим структурный граф И по мографу См (рис. 3.54), используя этот алгоритм. Матрица инцидентности Я(С~), определяющая мограф См, имеет вид хз хз хз хз хз уз х, хза хз .з уз 1 О О О О 1 1 О О О О О О О 1 О 1 О О 1 О 1 О О О О О 1 О О О О 1 О О О О О О О 1 О 1 О О О О О О О О О О О О 1 О О 1 1 О 1 О О 1 О Частотная матрица отношения Р(См), Г = Яхх Я, определяющая частотные свойства мографа СМ, имеет следующую строчную запись: Р(См) = 2хдто(хд) ОХ~~О2Х~~О(х~) о(хэ) охта(х') о О (хз) О 2хэ О 2(ха) О хдхз О хдхз О хдха Олкдхз О хдхь О О Хтхз О Хтхс О хзх,д О ХЭХЭ О ХЗХЬ О хэхг О Хяхь О ХЗХЭ1 330 Гл.4.
Теория формвльнтлх грамматик и автоматов где коэффициенты при тхт равны собственным частотам соотзетствуюших букв, коэффициенты при 4713 равны ненулевым взаимным частотам между соотзетствуюшими буквами а, 13 = хм хт, хт, хз, хтз, хз, х4, х>4, хь, ха, хг, о ' — конструктивный разделитель частот. Анализ частного разложения мографа См показывает, что для множеств (хы хт, хз) и 1хз, х', хг, хг) выполняется частотное соотношение (4.13): для множества (хм хэ, хз) У*, = У..., + У-, „Ут = Ь, .
+ У*-.;, У. = У.*, + У.;.„ Уг' = Уг>зг» Уиз = Л>из> Ь> Ук>гз> Ьз Уиьгз> У*. = Узч ,* У.; = У..., Ум=О, 14~1, й>1=хт,хэ>хз, Уь>т> О, 1с т' 1 ус ! = хм хз х4 хь> хь> хз' для множестза 1х~з, хь, хг, хэ) Ухз Уг>згз > Уг) Уз> г! > Угз Угзгз Ьзгз > Ьз = йъдз + Ьзк» Ьз Ьздз> Ь> = Ул>из> Ьь Ьькз> Ум=О, !с~!> 1с>!=ха>хь>хь>хь Отсюда имеем структурный граф Н, реализующий маграф 07ьт (рис.
4.13). Заменяя вершины графа Н на ключекые элементы первого типологического базиса, например, на переключатели света, а дуги — на спетоводы, получаем логическую схему сложности, равной числу вершин структурного графа Н. Проводя точное решение для примера, рассмотренного з начале этого параграфа, получаем з 2 раза меньше расщеплений хь хт .тз хз Рис. 4.44 (рис. 4.44) по сравнению с решением, црозеденным без учета запрещенных фигур. Частотный анализ можно с успехом использовать и при приближенном преобразовании мографа С~(У) а структурный граф Н(У . ведем ряд понятий. 14.7. Синтез логических стпруктгур в тополагичгских базисах 331 Уровнем таила А называется подмножество Х'4 множестза букв Х = 1х;/ з ='1, ..., т) такое, что: 1) ~~7 У; = В ~ Уг>*, = О, (4.14) теХл > г> фгт *„г> ЕХ' где У,, — сабсткенная частота буквы хб У >, — взаимная частота пары букв х;, х;  — число простых импликант в ДНФ функции У(х), которое обычно называют рангом ДНФ; буквы являются первичными термами рассматриваемой функции; 2) а структурном графе, реализующем эту функцию, найдется ярус, вершины которого взаимно однозначно нзкешены буквами подмножества Хл>, так что не найдется ни одной вершины, не принадлежащей этому ярусу и взвешенной буквой х; (х; Е Хл).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
