Горбатов В.А. - Фундаментальные основы дискретной математики. Информационная математика - 2000 (1019108), страница 78
Текст из файла (страница 78)
Обяаательной МПИ является юсплиааита 1». 5. Заменяем з матрице »2 строки 0011, ОШ, 1011, 1111, соатзетстзующне конституеитшс булевой фуиюсяи ус, не многоаыходную простую имплнпанту 1з. В результате полу сеем матриау В» х» Вг хг хг аг ус 4)(с) МПИ. П ерехадим к б. Строки матрицы с первой по последнюю яе язлшотся д. 7. 7. Частотная катрина отношений имеет зид Вс хг Вг ез Вг е» В» 5 4 4 5 3 9 7 7 9 5 О 3 5 6 3 !4 8 6 8 б 8 11 0 8 3 6 0 П 6 5 8 8 6 14 0 6 5 5 0 8 9 0 0 14 4 5 5 9 4 7 4 7 5 9 3 5 а' с вс ег нг. хз ез х» х» кычисляя зиа сеняе с(1). Для импликаяты 1з = и равна 1, 55.
Выбяраем Ез = — 00 и переходим 8. Оценнзаем каидую МПИ, = — 4Х) зта оценка минимальна кп. 5. 1 О 1 0 1 1 0 1 0 1 1 0 1 0 1 1 0 1 0 0 1 0 1 0 0 1 0 0 1 1 1 0 0 1 1 1 0 О 1 1 0 1 1 0 1 0 1 1 0 1 0 1 1 0 1 0 1 1 0 0 О 1 1 0 0 0 1 1 0 0 0 1 0,1 1 0 1 0 1 1 0 1 0 1 1 0 1 0 1 1 0 1 0 1 1 0 1 0 1 О О 1 О 1 О 0 1 0 1 0 О О О О О 0 1 0 0 1 0 О 0 1 1 1 0 1 0 1 0 1 0 0 1 0 0 0 1 0 1 0 0 1 0 0 О 1 1 1 0 1 1 0 1 0 1 0 1 0 0 1 0 0 1 0 0 0 1 0 0 1 1 1 0 1 1 0 1 0 1 1 0 1 5. В матраце »20) аамеияем конснпуенты единнаы, покрьпые нмплнкантой Дц атой имплнкаитай. В результате получаем матрацу Сег)г) 6.
Матрице С20) садеряит строки, и т. л. В реаультате лолу сена матрица хс ас хг зг ие язляющиеся МПИ. Переходим к и. 7 хз хз х» В» 0 О 0 0 0 0 0 0 0 1 0 0 0 1 0 0 1 0 0 0 0 0 1 0 0 1 0 1 0 1 0 1 1 0 1 00 1 0 0 0 0 0 1 0 1 0 0 0 0 1 О 0 0 0 0 0 которая соотзетстзует решешпо г(Х) = хсхгус чвсвгсс 'чвгх»У, цвсх»уг чвгв»Уз сс хгхзуз ихгх»уз.
Определим удаленность полученного решения от мюшмального. Для зтага зададим кандую ТДНФ втой системы мографом и определим распределение запрещенных фягур. Семантически зкзизааеитпруя полученные мографы мо. графами, интерпретируемыми з категориях структурных графов, долу сеем, что синтеаирозанная ТДЙФ систезяа булез!ах функцнй7(Х) беа перебора всех зккнзалеитных ТДНФ саатзетстзует абсолкнно минимальному решеюпо. В 5Л. Хараитериззция разложения графа переходов в частичное деинртово произведение Сложность и надежность автомата во многом определяются кодами внутренних состояний. Одной нз актуальных является задача минимизации связей между элементами памяти.
Будем считать два элемента памяти иесалзмыми, если функция возбуждения одного из ннх не зависит от состояния другого элемента памяти, и наоборот. В случае несвязности элемента памяти со всеми остальными элементами его функция возбуждения опреде- 1 0 1 0 1 1 0 1 0 1 1 0 1 0 О 1 0 1 О 0 1 0 0 1 1 1 0 0 1 1 0 1 1 0 1 0 1 1 0 1 0 1 1 0 0 0 1 1 0 0 0 1 1 0 0 0 1 О 1 1 О!0 0 1 0 1 1 О 1 0 1 1 0 1 0 1 О 0 1 0 1 0 О 1 О 1 0 О О О О О 0 0 0 0 1 0 1 0 0 0 1 1 1 0 1 0 1 0 1 0 0 0 1 0 ! О 0 0 1 1 1 0 1 1 О 1 0 1 0 1 0 0 1 0 0 0 1 0 0 1 1 1 0 1 1 0 1 0 1 1 0 1 0 1 0 Гл.5.
Приклоднал глсория алгориюлоа 430 55.5. Характериэацил разложение графа переходов 431 ляется состоянием этого элемента и входным вектором: Р; = Р1(х+, Х). Будем характеризовать память автомата ее связностью Я = ~~~се;, 1=1 где э — общее количество элементов памяти; ол — количество элементов памяти, отличных от (-го элемента, значения которых необходимы для вычисления функции возбуждения е-го элемента памяти. Значение связности памяти Я, равное нулю, означает, что эле- менты памяти функционально несвязны и функция возбуждения любого элемента памяти определяется его значением и входным вектором.
Рассмотрим задачу разложения произвольного графа переходов в частичное декартово произведение и функционально не связан- ных друг с другом сомножителей, каждый из которых соответ- ствует подавтомату. Функциональная связность между блоками возникает цри на- рушении детерминированности хотя бы в одном из графов перехо- дов С);. Для описания ситуаций нарушения детерминированности введем граф сцепления С „, каждой вершине которого взаимно од- нозначно соответствует внутреннее состояние автомата, ребру— лара сцепленных состояний, причем каждое ребро взвешено вход- ными векторами, которые сцепляют соответствующие состояния автомата.
Два состояния, Я и Ял, называются сцеплсннььии аекгпором Х;, если найдутся: набор Х;, который переводит состояние 5 в Ят (5 ~ 5„), и набор Х (Х; С Х.), который переводит Ял в Яг (Ял — '> Яб), такие, что Ят уЕ 51 и (5, Ят) и (ЯЗ, Яб) не образуют петли одновременно. Состояние графа переходов С = (У, Щ Х)) после его разложе- нця в частичное декартово произведение алсПа;, а;сс(УО%,Х)), можно охарактеризовать вектором, ечму разряду которого соответ- ствует состояние е-го подавтомата.
При разложении каждый подав- томат характеризуется допустимым количеством состояний )У;). Очевидно, что П~') - ')У) 1 Сцепленным состояниям должны соответствовать векторы, от- личные друг от друга в каждом разряде. В противном случае, если в у-и разряде векторы сцепленных состояний совпадают, то прн подаче на вход автомата вектора Х, по которому они сцеплены, в общем случае будет нарушена детерминированность перехода в этом подавтомате. Следовательно, построение абстрактной параллельной декомпозиции автомата сводится к многокомпонентной раскраске (мультираскраске) графа сцепления, при которой смежным вершинам сопоставляют спектры красок, отличные друг от друга в каждой компоненте.
Разложение графа переходов в частичное декартово произведение не выводит результирующий граф из класса графов перехода. Запрещенными фигурами этой семантики являются квазиполные графы. Теорема 5.4. Если граф сцепления, построенный для каждого из подавтоматоа, нс содержит кааэиполного графа коазиплогпности у+1, то соотостсгппующий автомат разложйм (декомпоэирусм) о частичное декартово произведение функционально нс связанных между собой сомножителей — подаагпоматов, число состояний каждого иэ которых не прсаышаст о. Таким образом, квазиполные графы — запрещенные фигуры, характеризующие достаточное условие функциональной несвязности подавтоматов при поиске параллельной декомпозиции управляющего автомата. В дальнейшем этот класс запрещенных фигур будем обозначать Я .
При этом граф сцепления для первого рассматриваемого подавтомата представляет собой граф сцепления, построенный по графу переходов согласно его определению. Граф сцепления (-го подавтомата представляет собой граф сцепления первого подавтомата, в который добавлены ребра, соединяющие вершины с одинаковым спектром красок. Добавление этих ребер необходимо для однозначной идентификации состояний автомата. Рассмотрим построение абстрактной параллельяой декомпозиции автомата на основе найденной семантики на следующем примере.
Автомат имеет трн вхолных лапала. Граф переходов наобранен на рнс. 3.29, о. Входные вевторы абоаначены десятичными эпзнзалентамн соатветствуююнх двоичных наборов. Найдем параллельную депомпознпюо автомата в виде двух автоматов с числом внутренних состояний соответственно 3 н 4.
Граф слеплення первого подавтомага приведен на рпс. $.3о,о. Он не содерннг аавоеюяннпх фнгур; следовательно, воаманна раскраска тремя пзетамн: (О, 1, 2). Пандый пзег соответствует состаянюо первого подазтомата. Построим его граф перехадоз Ог = (ги (11и Х)). В результате раслраспн графа й, мно. нество састаянпй исходного автомата раабнвастся на трн солвегных мнонестза, вандее пз паторых соответствует состоянию первого падазгомата, Обоеначпм нх соответственно о(е, о(и о(е.
Имеем (А, Вм ае, Уи) = 8(а, (ее, ае, 8е, Уга) = ааги (аи Уз, Вг, ои) = аи. У Отсюда условнямн перехода у;.+г на состояния о(г в состояние 3, . (111 м О, У 1, 2) лерзагоблопа являютсяусловняпереходапа састоянля о б ои з состояние 432 Рис. 5.31 Рис. 5.29 Рис.
5.ЗО Гл. 5. Прикладиаа теория алеоритмов бл Е б'„, определяемые исходным грабюм переходовг его-ео = О, уо-+~ м 1Ч5, Его.ьг = 2ЧЗЧ 4, Рг. г =ЗЧ$, Згг о=2чб, згг. г=4Ч7, Згг~з =1ЧЗЧ5, Из+о =6, рг+г =ОЧ5. Граф сцепления, соответствующий второму блову, нвобранеи на рис. 5.$0, б.
Он не содериит аапрещеняых фигур; следовательно, исходный автомат реализуем а виде параллельно работающих фунвююнальяо несвязных югдавтоматов. Распрасцв второго графе сцепления равбивает мноиество состояний нсхолного автомата на следующие четыре мнааества: йге = (Аы Аго, Аг)~ 8гг = (оз, 8е, Бг), бгг = 1оз, Яз, бз), 8зз = ~Дз, 8з, огг). Фунпцяи перехода для состояний второго цодавтомата имеют следующий вид: его~о = 2, Фо-+г = О, Зге~з = 3, Югмг = 1Ч 7, Уг.ее =3, УЕ-ьг = 4, Егг.+З = 5, Згг.ьг = 4 Чб, Уз.ее ю 2 Ч5, Иг-ьг =ОЧ 7, Юз.+з = 6, Уз-+о ю 2 Ч 5, згз-ьз = 7, ззз-+г = 4. $5.5. Характериэацил роэлогкенш графа переходов 433 Раалонение ааданного графе переходов яа фуяпциональио несвязные сомнонители приведены на ряс.
5.29,6. Построим абстрактную декомпозицию автомата, используя семантику разложения графа переходов в произведение сомножителей. Пусть задан граф переходов С (рис. 5.31, а), который необ- ходимо разложить в произведение С = 61 х Сз, где 01 и Сз— графы переходов, мощность носителя каждого из которых не превышает 3. Построим граф сцепления Ссц и произведем его раскраску по первой компоненте (рис. 5,31,6). Для этого выделим все пустые подграфы 1Я2, Яе, Яв), (Яз Яе), 1Я1, Яв) 1Я1, Яз, Яб), 1Я1, Яг, Яу), (Яз Яб), (Ят, Яв, Яв), (Яу, Яв) графа сцепления.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
