Файл: Горбатов В.А. Синтез композиции операционного и управляющего автоматов в вычислительной технике учеб. пособие.pdf
ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 05.08.2024
Просмотров: 45
Скачиваний: 0
c b u ty fc u v C )
НИсУЕРСТфГ рЫСШЕГеГ И СРЕДНЕГО СПЕЦИАЛЬНОГО ОБРАЗОВАНИЯ СССР
МОСКОВСКИЙ ордена ЛЕНИНА ЭНЕРГЕТИЧЕСКИЙ ИНСТИТУТ
В. А. ГОРБАТОВ
СИНТЕЗ КОМПОЗИЦИИ ОПЕРАЦИОННОГО
УПРАВЛЯЮЩЕГО АВТОМАТОВ ВЫЧИСЛИТЕЛЬНОЙ ТЕХНИКЕ
! |
‘V |
я |
? |
Ф И ? -k |
г |
|
|
к, |
|
|
І |
|
|
--------- |
Москва |
1973 X |
О
a « •
о я
оw о
:v - . Р-4Л H
оч Ш
* V
3S 0} CD
'■''■С'; M H
|
О SS |
|
а t=s - |
«■О |
а о о |
cd ss . |
|
/ |
Рма я |
(US) ч |
|
«■Q |
СЗ Я К |
|
о |
|
Я CD |
|
! Sä Я |
|
а яо |
|
сто о |
|
SS H о |
|
со cd о |
|
о я cs |
|
сз о • |
|
s HO |
|
о я аз |
|
w cd »* |
Й M о
»CD t-l I CD
er
03 JSS cs а
оw
•о
к <u
оз tr/-*>
Рна •
он а оз к
аа а
•РМк
аCD X
о Ш 03\
а СОН • |
||
я |
|
• я |
о |
к н со |
|
о |
а cd |
|
и о |
ч и |
СS3 О sa • а п
ѵ>Рн р-н
•о Я>*ч чо wm
ао |
о |
|
|
еды |
|
СЗ и й |
• |
|
• а |
к о |
|
О Я 03 |
• |
О
о [СЛ^1і
(■
ь
МИНИСТЕРСТВО ВЫСШЕГО И СРЕДНЕГО СПЕЦИАЛЬНОГО ОБРАЗОВАНИЯ СССР
МОСКОВСКИЙ ордена ЛЕНИНА ЭНЕРГЕТИЧЕСКИЙ ИНСТИТУТ
Кафедра вычислительной техники
. I
В. А. ГОРБАТОВ
Утверждено Учебно-методическим управлением МЭИ в качестве учебного пособия для студентов
СИНТЕЗ КОМПОЗИЦИИ ОПЕРАЦИОННОГО
ИУПРАВЛЯЮЩЕГО АВТОМАТОВ
ВВЫЧИСЛИТЕЛЬНОЙ ТЕХНИКЕ
З А Л /
Ф ИЗ.-М АТЕМ &Т.
ЛИТЕРАТУРЫ
Москва |
1973 |
001
і ч ч Г
I
iljr о:;»ч: ^;>Oj5j ways*іо « ■•■.'.л,\ »*•'ңая
ÖhO !іУ ^ ; OK^ С С С Р Э К S К I* 1П."; >2г*
ЧИТАЛЬНОГО ЗАЛА
I
I
|
Г л а в а |
І |
|
|
|
|
АЛГОРИТМИЧЕСКИЙ ЭТАП СИНТЕЗА |
|
|||||
'§ 1-1. Граф. Сеть |
|
|
|
|||
Рассмотрим множества М\, |
М2, |
..., М п. |
|
|
||
Декартовым произведением множеств М\, М2, ..., М п |
||||||
|
І—1 |
|
|
|
|
|
называется множество последовательностей |
(гпі/і = 1ч -я), |
|||||
где пц 6 М і для каждого і. |
[W ' |
|
|
. |
||
Рассмотрим декартово произведение вида ІЧХМХ...ХАГ= |
||||||
= М". Будем говорить, |
что |
элементы |
mit |
т2, ..., |
||
тп находятся в я-арном отношении R в том и только в том |
||||||
случае, если последовательность |
(inі, іп2, ..., |
тп) принадле |
||||
жит подмножеству R(R с |
Мп) ( т ь т2, ..., mn)eR. |
|
||||
Моделью называется совокупность множества М с задан |
||||||
ными в нем отношениями R t, |
R 2, ..., Ru, |
причем М называет |
||||
ся носителем модели, г'-арные отношения |
(і = |
1ч-&) Ri, |
R 2 |
|||
(/^-сигнатурой модели. |
|
|
|
|
|
|
Частным случаем я-арного отношения является бинарное отношение (отношение при п-= 2). Бинарным отношением, например, является отношение соединения каналом связи двух устройств. Частным случаем модели является «граф».
Графом G называется |
< Х , Г>, где множество X назы |
вается носителем графа, |
а отображение Г X в X — сигнату |
рой графа. |
|
Будем элементы множества X геометрически интерпрети ровать кружочками і(точками или прямоугольниками), а пары кружочжов X и у, для которых уеѴх, соединять линией со стрелкой, направленной от ж к у и называть каждый элемент множества X вершиной графа, а пару элементов (х, у) (у 6 Гл:) — дугой графа.
3
Подграфом графа <ІХ |
Г> |
называется |
граф вида <*А, |
||
Гд>, где А С X и ТАх = Г* П А. |
|
|
|
||
Частичным графом графа <.Х, Г> |
называется граф вида |
||||
<^Х, Д>, где Ах СГ% для всех хеХ. |
|
|
|
||
Частичным подграфом |
графа < Х , |
Г> |
называется |
граф |
|
вида <А, ЛА> , где А С Х |
и Аах СГл'п А. |
|
|
||
Если дуга и = (а, Ь), |
то |
вершины а |
и b будем |
на |
зывать граничными, причем а — началом^ а b — концом дуги.ч Две дуги иа и щ называются смежными, если они имеют
общую граничную вершину.
Две вершины а и b , называются смежными, если существует дуга, идущая от одной из них к другой..
Если вершина а является началом или концом дуги и, то будем говорить, что дуга и инцидентна вершине а, а верши на а коинцидентна дуге и. В данном и в последующих слу чаях приставка «ко» образуется взятием двух первых букв
от латинского слова conversus (обратный). |
множество из |
||
Ребром графа G = < X, U > |
называется |
||
двух вершин х и |
г/, для которых |
(х, у) е U или {у, х), е U. |
|
Понятие ребра нельзя смешивать с понятием дуги, в ко |
|||
тором участвует ориентация. |
|
|
|
Определим понятие взвешенного графа. |
1 б- п) графа |
||
Сопоставим |
каждой вершине X = ( х 4 і = |
G —< X , U > вес Wi из множества весов W = {щц/£= 1, 2, ...). В результате получим множество взвешенных вершин
[(Xi, Wi)/і —! 1 б- п\,
при этом необязательно, чтобы зсе веса были различными.
Сопоставим каждому |
элементу |
множества дуг U — |
— { Ui/i = l-i-m )вес рі из |
множества |
весов Р ={р,// = 1, 2, ..■}, |
в результате получим множество взвешенных дуг |
||
{{Ui, |
pi)/i — l ~ m } , |
при этом необязательно, чтобы все веса были различными. Определенные выше множества взвешенных вершин и взвешенных дуг определяют в совокупности взвешенный
граф G = < (X, W), (U, Р) > .
Взвешенный граф, у которого множество W или множе ство Р, или W и Р являются множеством .булевых функций, называется булевым графом.
Путем в графе G = > < X , U > называётся такая последо вательность (uai, иа2, ..., Uav) дуг, что £онец каждой предыду щей дуги совпадает с началом следующей.
4
Контуром называется конечный путь (иа\, иа2,..., иаі), у которого начальная вершина совпадает с конечной.
. Длиной пути называется число дуг последовательности, образующей путь.
Цепью называется последовательность ребер (гп,, га2, ..., гап), в которой у каждого ребра гаі (і = 2-^п—1) одна из гра
ничных вершин является граничной |
вершиной для гаг-ь a |
другая — граничной вершиной для гаі+і. |
' |
Циклом называется конечная цепь, начинающаяся в нег которой вершине х и оканчивающаяся в той же вершине х.
Длиной цепи называется, число ребер, образующих эту цепь.
В зависимости от наличия цикла в графе графы класси фицируются на деревья и недереБья.
Деревом называется граф без циклов.
Ориентированной сетью называется граф G = < X, U > без контуров, множество вершин которого разбито на три подмножества Х +, Х~ и ,А!\(X+UX~) так, что дуги, инцидент ные X в Х+ направлены только от вершины х, дуги, инцидент
ные X вХ~ направлены только в вершину х, |
и для |
любой |
|
вершины х в |^ Г \ ( ^ +и х - )) |
найдутся дуги, |
направленные |
|
как от вершины х, так и к вершине х. |
|
|
|
Если в вышеопределенной |
сети для каждой дуги |
(х, у) |
имеется дуга (у, х), которые обе заменены на одно ребро, соединяющее вершины х и у, то сеть называется неориенти
рованной. |
4 |
|
§ 1-2. Дифференцирование графов. |
|
Частотная матрица отношений |
Известно, что понятие производной в математическом анализе характеризует степень изменения функции при из менении ее аргумента в «малом». В силу отсутствия понятия предела в дискретной математике, нет возможности механи чески перенести понятие производной из непрерывной мате матики в дискретную. Тем не менее целесообразность поня тия производной в дискретной математике очевидна.
Введем понятие производной от графа.
Пусть нас интересует степень участия компонент графа G вѵнаперед заданном событии 5 в Графе G, другими словами, степень неоднородности компонент графа относительно за данного события. Будем характеризовать эту неоднородность
(эти изменения) производной |
графа G по событию 5 . |
д о
5
Каждое событие определяет двухвходовую двоичную мат рицу Q =• [quin.™, каждому столбцу которой взаимно одно значно соответствует элемент, входящий в событие, строке совокупность элементов, при наличии которых событие имеет место (при наличии которых событие истинно), и
(1, если /-;и элемент входит в і-ю совокупность эле- qn = | ментов, при наличии которых событие истинно
ІО, в противном случае
Другими словами, каждое событие определяет модель, матрица инцидентности которой является матрица Q, т. е. элементы, входящие в событие, являются буквами модели, совокупности элементов, при наличии которых событие ис тинно, — словами модели.
Интенсивность участия элементов (букв) в событии (в словах) можно характеризовать частотой их вхождения. Для этого введем частотную матрицу отношений іF —<[{ц]пхп, ха рактеризующую модель г|>, матрица инцидентности которой
есть Q (^) = [,'7;j]mx4i-
Частотной матрицей отношений F — [)',,]„!Х называется матрица, каждой строке (каждому столбцу) которой взаимно однозначно соответствует буква и fa равен числу слов, в ко
торые входят буквы і и /. При этом, |
если і = /, то |
назы |
вается собственной частотой буквы, |
в противном |
случае |
( іф /) —взаимной частотой б}'кв і и /. ■
Из определения частотной матрицы отношений ^ ='[/«] mm следует, что частотная матрица отношений симметрична от носительно главной диагонали
|
|
(І-D |
|
что позволяет не записывать одну из половин матрицы, и что |
|
|
собственная частота любой буквы не меньше взаимной часто |
|
|
ты этой буквы с любой другой буквой |
|
|
. fu > fij . |
(1-2) |
|
Нетрудно показать, что частотная матрица отношений F, |
|
|
характеризующая модель, матрица инцидентности которой |
|
|
есть Q, связана как |
(1-3) |
|
QT X Q ^ F . |
|
I |
Производной —— графа G по событию 5 |
называется |
|
öS |
|
|
л о |
которого |
|
взвешенный граф'—— = <V, (U, Р )> , носитель |
öS
6