книги из ГПНТБ / Горбатов В.А. Синтез композиции операционного и управляющего автоматов в вычислительной технике учеб. пособие

c b u ty fc u v C )

НИсУЕРСТфГ рЫСШЕГеГ И СРЕДНЕГО СПЕЦИАЛЬНОГО ОБРАЗОВАНИЯ СССР

МОСКОВСКИЙ ордена ЛЕНИНА ЭНЕРГЕТИЧЕСКИЙ ИНСТИТУТ

В. А. ГОРБАТОВ

СИНТЕЗ КОМПОЗИЦИИ ОПЕРАЦИОННОГО

УПРАВЛЯЮЩЕГО АВТОМАТОВ ВЫЧИСЛИТЕЛЬНОЙ ТЕХНИКЕ

О

МИНИСТЕРСТВО ВЫСШЕГО И СРЕДНЕГО СПЕЦИАЛЬНОГО ОБРАЗОВАНИЯ СССР

МОСКОВСКИЙ ордена ЛЕНИНА ЭНЕРГЕТИЧЕСКИЙ ИНСТИТУТ

Кафедра вычислительной техники

. I

В. А. ГОРБАТОВ

Утверждено Учебно-методическим управлением МЭИ в качестве учебного пособия для студентов

СИНТЕЗ КОМПОЗИЦИИ ОПЕРАЦИОННОГО

ИУПРАВЛЯЮЩЕГО АВТОМАТОВ

ВВЫЧИСЛИТЕЛЬНОЙ ТЕХНИКЕ

З А Л /

Ф ИЗ.-М АТЕМ &Т.

ЛИТЕРАТУРЫ

I

Частным случаем я-арного отношения является бинарное отношение (отношение при п-= 2). Бинарным отношением, например, является отношение соединения каналом связи двух устройств. Частным случаем модели является «граф».

Будем элементы множества X геометрически интерпрети­ ровать кружочками і(точками или прямоугольниками), а пары кружочжов X и у, для которых уеѴх, соединять линией со стрелкой, направленной от ж к у и называть каждый элемент множества X вершиной графа, а пару элементов (х, у) (у 6 Гл:) — дугой графа.

3

зывать граничными, причем а — началом^ а b — концом дуги.ч Две дуги иа и щ называются смежными, если они имеют

общую граничную вершину.

Две вершины а и b , называются смежными, если существует дуга, идущая от одной из них к другой..

Если вершина а является началом или концом дуги и, то будем говорить, что дуга и инцидентна вершине а, а верши­ на а коинцидентна дуге и. В данном и в последующих слу­ чаях приставка «ко» образуется взятием двух первых букв

G —< X , U > вес Wi из множества весов W = {щц/£= 1, 2, ...). В результате получим множество взвешенных вершин

[(Xi, Wi)/і —! 1 б- п\,

при этом необязательно, чтобы зсе веса были различными.

при этом необязательно, чтобы все веса были различными. Определенные выше множества взвешенных вершин и взвешенных дуг определяют в совокупности взвешенный

граф G = < (X, W), (U, Р) > .

Взвешенный граф, у которого множество W или множе­ ство Р, или W и Р являются множеством .булевых функций, называется булевым графом.

Путем в графе G = > < X , U > называётся такая последо­ вательность (uai, иа2, ..., Uav) дуг, что £онец каждой предыду­ щей дуги совпадает с началом следующей.

4

Контуром называется конечный путь (иа\, иа2,..., иаі), у которого начальная вершина совпадает с конечной.

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

Цепью называется последовательность ребер (гп,, га2, ..., гап), в которой у каждого ребра гаі (і = 2-^п—1) одна из гра­

Циклом называется конечная цепь, начинающаяся в нег которой вершине х и оканчивающаяся в той же вершине х.

Длиной цепи называется, число ребер, образующих эту цепь.

В зависимости от наличия цикла в графе графы класси­ фицируются на деревья и недереБья.

Деревом называется граф без циклов.

Ориентированной сетью называется граф G = < X, U > без контуров, множество вершин которого разбито на три подмножества Х +, Х~ и ,А!\(X+UX~) так, что дуги, инцидент­ ные X в Х+ направлены только от вершины х, дуги, инцидент­

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

Известно, что понятие производной в математическом анализе характеризует степень изменения функции при из­ менении ее аргумента в «малом». В силу отсутствия понятия предела в дискретной математике, нет возможности механи­ чески перенести понятие производной из непрерывной мате­ матики в дискретную. Тем не менее целесообразность поня­ тия производной в дискретной математике очевидна.

Введем понятие производной от графа.

Пусть нас интересует степень участия компонент графа G вѵнаперед заданном событии 5 в Графе G, другими словами, степень неоднородности компонент графа относительно за­ данного события. Будем характеризовать эту неоднородность

д о

5

Каждое событие определяет двухвходовую двоичную мат­ рицу Q =• [quin.™, каждому столбцу которой взаимно одно­ значно соответствует элемент, входящий в событие, строке совокупность элементов, при наличии которых событие имеет место (при наличии которых событие истинно), и

(1, если /-;и элемент входит в і-ю совокупность эле- qn = | ментов, при наличии которых событие истинно

ІО, в противном случае

Другими словами, каждое событие определяет модель, матрица инцидентности которой является матрица Q, т. е. элементы, входящие в событие, являются буквами модели, совокупности элементов, при наличии которых событие ис­ тинно, — словами модели.

Интенсивность участия элементов (букв) в событии (в словах) можно характеризовать частотой их вхождения. Для этого введем частотную матрицу отношений іF —<[{ц]пхп, ха­ рактеризующую модель г|>, матрица инцидентности которой

есть Q (^) = [,'7;j]mx4i-

Частотной матрицей отношений F — [)',,]„!Х называется матрица, каждой строке (каждому столбцу) которой взаимно однозначно соответствует буква и fa равен числу слов, в ко­

( іф /) —взаимной частотой б}'кв і и /. ■

Из определения частотной матрицы отношений ^ ='[/«] mm следует, что частотная матрица отношений симметрична от­ носительно главной диагонали

öS

6

называется значением производной на дуге ( v it Vj).

Производная-^- графа G по событию S характеризует

Рис. 1-1

степень неоднородности участия компонент графа G в собы­ тии 5 .

Проиллюстрируем понятие производной от графа по со­ бытию на двух примерах.

Пусть заданы граф (рис. 1-1) и событие 5 на нем: «об­ разование ребрами остова графа «G». Найти производную от графа G по событию 5 ,

7

Заданное событие определяет модель, матрица инцидент­ ности которой имеет следующий вид:

В этой матрице каждому столбцу взаимно однозначно со­ ответствует ребро графа G (элемент, входящий в событие), строке — совокупность ребер, образующая остов графа (ус­ ловие, при котором заданное событие имеет место).

с

Частотная матрица отношений F, соответствующая этой матрице, представляет собой следующее:

8