Анализ задачи минимизации операторных схем алгоритмов

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

Широкое распространение информационных технологий и постоянно  растущая сложность средств автоматики, вычислительной техники и программного обеспечения наряду с требованием быстрого и безошибочного их проектирования в настоящее время неизбежно приводят к применению ЭВМ на различных этапах их проектирования. В связи с этим особую актуальность имеет задача создания эффективных машинных методов проектирования средств автоматики и вычислительной техники, в частности, микропрограммных автоматов (МПА).

Для задания законов функционирования МПА широко применяются операторные схемы алгоритмов (граф-схемы и логические схемы алгоритмов – ГСА и ЛСА). Затраты оборудования в МПА существенно зависят от сложности операторной схемы алгоритма, задающей закон его функционирования. В связи с этим возникают задачи минимизации ГСА и ЛСА, которые практически совпадают.

Минимизация числа вершин в ГСА необходима при решении часто встречающейся задачи объединения множества частных ГСА в единую минимизированную граф-схему. Эта же  задача возникает при автоматизации микропрограммирования, а также при разработке программного обеспечения микро-ЭВМ, когда требуется решать задачу рационального использования её памяти.

Методы построения минимизированных ГСА необходимы при решении задачи трансляции таблиц решений, которые используют для задания алгоритмов с большим числом разветвлений.

Предлагаемые в литературе методы минимизации граф-схем алгоритмов либо не позволяют за приемлемое время минимизировать ГСА практической сложности, либо часто приводят к результатам, далеким от минимальных.

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

Задача минимизации операторных схем алгоритмов рассматривается во многих работах. Однако в литературе отсутствует анализ возможности получения с помощью этих методов ГСА, минимальных по числу условных, операторных или по суммарному числу вершин при различных распределениях сдвигов и при наличии повторяющихся операторов в граф-схемах. Рассмотрение этих вопросов, а также разработка общей методики минимизации ГСА (без детального рассмотрения задач отдельных её этапов) проводятся в данной статье.

Эквивалентность граф-схем алгоритмов и нахождение множеств запрещенных наборов

Пусть задана ГСА Г(A, Р, Y, X), у которой A = {Ao, ..., AG+1 } - множество операторных вершин (Aо – начальная, AG+1 - конечная), P = {p1, ..., pQ} - множество условных вершин, Y = {Y0, ..., YT+1} – множество операторов (Y0 - начальный, YT+1 - конечный), X = {x1, ..., xL} - множество логических условий (переменных). В каждой операторной вершине записан один из операторов множества Y, причем в вершине А0 - оператор Y0 , а в вершине AG+1 - оператор YT+1. В различных операторных вершинах могут быть записаны одинаковые операторы из множества {Y1, ..., YT}. В каждой условной вершине записано одно из логических условий множества Х. В различных условных вершинах могут быть записаны одинаковые логические условия. Предполагается, что значения логических условий x1,..., xL могут изменяться только в моменты выполнения операторов [1] .

Если каждому оператору Yt (t = 0,1, …, Т) поставлено в соответствие некоторое подмножество Bt логических условий, которые могут изменяться во время выполнения оператора, то говорят, что задано распределение сдвигов. Если Bt = X для (t= 0, 1,…, Т), то такое распределение сдвигов называют универсальным.  Можно рассматривать более общие распределения сдвигов, чем соответствие Yt  → Bt

(t=0,1,…, Т). Например, в виде соответствия Yt  → B0   ,B1  ,Bx

,B‾x  ,B

(t=0,1,…, Т), где  B0   ,B1  ,Bx

,B‾x   ,B –

t          t         t            t        t

t          t          t            t        t

множества  логических  условий,  которые  после  выполнения  оператора  Yt   соответственно принимают

значение 0(B0 ), принимают значение 1 (B1 ), сохраняют свои значения (Bx ), изменяют свои значения на

t                                                                                   t                                                                                           t

обратные (B‾xt), могут изменяться произвольным образом (Bt ).

Пусть в ГСА Г имеется путь из вершины Ai в вершину AJ вида Ai  pi1…pir…piRAJ  , проходящий только через условные вершины pi1…pir…piR. Каждому такому пути соответствует конъюнкция α ij логических условий xi1…xir…xiR, записанных в вершинах pi1…pir…piR. Причем, переменная xir входит в эту конъюнкцию с инверсией, если выходу условной вершины pir, через который проходит путь, приписана цифра 0.

Если между Ai  и Aj  имеется несколько (например, H) путей, проходящих только через условные

вершины, то αij = V H      αh

ij , где αh

ij - конъюнкция, соответствующая h -му пути из Ai  в Aj. .Функцию   αij

называют функцией перехода от операторной вершины Ai  к операторной вершине Aj , а выражение Ai   →

G+1

Vj         =1 αij Aj - формулой перехода для операторной вершины Ai [1].

В работе [ 2 ] определен процесс выполнения ЛСА, не содержащих повторяющихся операторов, на

произвольной последовательности наборов значений логических условий x1,..., xL , который очевидным образом распространяется на ЛСА и ГСА с повторяющимися операторами (при этом, кроме строчки выполняемых операторов, требуется выписывать и строчку проходимых операторных вершин). Результатом выполнения ГСА Г на произвольной бесконечной последовательности наборов Δ1 ... Δm ... является строчка выполняемых операторов Y0Yi1... Yim …, называемая значением ГСА Г на последовательности наборов Δ1 ... Δm ... .

Эта строчка может быть либо бесконечной, либо конечной - заканчиваться конечным  оператором

Υt+1 или фиктивным oпeратором пустого периода (пустого цикла) Yt+2 [1-5].

Пусть  распределение  сдвигов для  ГСА Г задано  соответствием  Yt  → Bt    X (t=0,1,…,Т).  Тогда, последовательность наборов Δ1 ... Δm ... называется допустимой для ГСА Γ при заданном распределении сдвигов, если всякий набор Δm+1 либо совпадает с набором Δm , либо отличается от него только значениями переменных из множества Bim , где Yim - оператор, выполняемый при наборе Δm .

Причем, если значение ГСА Γ на некоторой последовательности наборов Δ 1 ... Δ m конечно и при наборе Δт выполняется оператор YT+1 или YТ+2 , то будем считать, что любая последовательность Δ1 ... Δm Δm+1... является недопустимой для Г. Подобным же образом определяется допустимость последовательности наборов для ГСА с более общими распределениями сдвигов.

ГСА Г1 и Г2 эквивалентны при заданном распределении сдвигов (Г1 ≡ Г2), если для всякой последовательности наборов, допустимой для ГСА Г1 или Γ2 при этом распределении сдвигов, значения этих ГСА совпадают [ 2 ].

Поскольку в практических применениях ГСА важны, как правило, лишь конечные значения ГСА, то часто целесообразно рассматривать более слабую эквивалентность ГСА - конечную эквивалентность, которую определим следующим образом (см. также [5, 6]).

Будем говорить, что ГСА Г1 и Г2 конечно эквивалентны (Г1 ≡к Г2), если для любой последовательности наборов, допустимой для Г1 или Γ2 и приводящей к выполнению конечного оператора в Г1 или Г2 , значения этих ГСА совпадают.

Множество ГСА, конечно эквивалентных заданной ГСА Г, включает в себя множество граф-схем, эквивалентных Г, поэтому, рассматривая задачу минимизации в классе конечно эквивалентных граф- схем,  можно  рассчитывать  на  получение  результатов  не  хуже,  чем  в  классе  эквивалентных    ГСА. В настоящей работе будут рассматриваться как эквивалентные, так и конечно эквивалентные преобразования ГСА.

Отметим, что если распределение сдвигов для ГСА не задано, то оно предполагается универсальным. Если для исходной ГСА задано неуниверсальное распределение сдвигов, то эта информация может быть использована при её минимизации, что дает возможность получать более оптимальные решения.

Наиболее полно можно учитывать распределение сдвигов при минимизации ГСА, если первоначально для каждой операторной вершины Аi заданной ГСА Г найти множество всех наборов (обозначим его Кi), которые могут образовывать логические условия x1,..., xL непосредственно после выполнения оператора, записанного в Аi, при выполнении ГСА Г на всевозможных допустимых последовательностях наборов [2-9]. А затем, считая, что на остальных (запрещенных) наборах функции перехода αij не определены, учитывать эту неопределенность при минимизации числа вершин в Г. Будем обозначать множество запрещенных наборов для операторной вершины Аi через Ni. Для их нахождения из методов [2-9] наиболее удобен для машинной реализации метод работы [9], в котором все действия описываются  как  соответствующие   операции  над   кубами.   Рассмотрим  этот   метод применительно к задаче нахождения множеств запрещенных наборов N0 ,…, NG для операторных вершин А0,…, AG заданной ГСА Г.

Пусть  множества  Кi,  Ni  и  функции  перехода  αij   для  операторной  вершины  Ai представляются в виде множеств L-мерных кубов, т.е.·в виде кубических покрытий (кубическое представление булевых функций описано в работе [10]). И пусть распределение сдвигов для ГСА Г задается соответствием Ai

→ci (i=0,…,G), где ci=(ci1,…,ciL) куб, в котором значение каждой координаты cil определяется следующим образом:

cil =0, если xl Î  B0 ;   cil

=1, если xl

Î B1 ;  cil

=x, если xl

Î Bx ;  cil

=‾x ,если xl

Î B‾x ; cil

=x~, если

xl  Î Bi.

Над произвольными кубами ar =(ar1,…,arL)   и ci=(ci1,…,ciL), где аrl Î {0,1,х}, определяется операция γ.

Операция γ  задастся координатной таблицей γ - операции (таблица 1): ar γ ci =(ar1 γ ci1,…,arL γ ciL).

Таблица 1 – γ - операция

Очевидно, что если Δ1 ... Δm - допустимая для ГСА Г последовательность наборов такая, что при наборе Δ m выполняется оператор, записанный в вершине Аi , то любая последовательность наборов Δ1 ... Δm Δm +1, где Δm +1 Í (Δ m γ ci) - также допустима для Г.

Для множества L - мерных кубов D и куба ci   γ-операция определяется следующим образом:

Dγ ci={ ar γ ci| arÎD }.

Путем итерации находятся устойчивые множества Ki (i=0,…,G).

Пусть на t-том шаге итерации (t=0,1,...) получены множества K t (i=0,…,G).

Тогда Ki

= Ki  U[(K0 ∩α0i)U…U( KG ∩αGi)] γ ci ,где Ki

= Æ;

t+1            t                  t                                          t                                                  0

t

K0 =K0 =(xx…x) γ c0  для любого t=0,1,...; i=1,...,G.

r              r-1

Если  при  t=r  Ki  = Ki

(i=1,...,G),  то  процесс  вычислений  считается  законченным  и  находим

множества Ni= (xx...х)#Ki (i=0,1,...,G), которые будут являться кубическими покрытиями множеств запрещенных  наборов для операторных вершин А0,…, AG   ГСА Г.

Здесь  и  в  дальнейшем  будем  использовать  одни  и  те  же  обозначения  для  множеств наборов

значений логических переменных и для их кубических покрытий. Операции ∩ и # над кубическими покрытиями определены в [10] .

При рассмотрении задачи минимизация ГСА в классе конечно эквивалентных граф-схем вместо множеств К0 ,..., KG. будут использоваться множества F0 ,..., FG. Через Fi будем обозначать множество всех наборов, которые могут образовывать логические условия после выполнения оператора, записанного в вершине Ai, при выполнении ГСА Г на всевозможных допустимых последовательностях наборов, приводящих к работе конечного оператора YT+1. Для нахождения множеств Fi ( i=0,1,...,G), предложим следующий способ, также использующий операции над кубами (множества Fi можно получать и с помощью «правил нижней разметки», предложенных в работе [3]).

Найдем для ГСА Г множества Ki ( i=0,1,...,G), используя рассмотренный выше метод. Получим функции αij’ =αij ∩Ki  (i=0,…,G; j=1,…,G+1).

Над произвольными кубами ar =(ar1,…,arL) и ci=(ci1,…,ciL),где аrl Î {0,1,х}, cilÎ {0,1,х,‾x, x~}, определим операцию Ω, которая задается координатной таблицей Ω-операции (таблица 2). Прочерки в таблице 2 соответствуют ситуациям, которые не могут возникать при нахождении множеств Fi.

Таблица 2 – Ω-операция

Множества Fi (i=0,…,G) будем искать путем итерации. Принимаем F 0=Æ (i=0,…,G). Пусть на t - том шаге итерации (t=0,1,...) получены множества F t (i=0,…,G).

t+1            t                  t                                                              t

Тогда Fi

= Fi  U[(F1  Ω c1) ∩α’i1]U…U[(FG  Ω cG) ∩α’iG] Uα’i,G+1.

r               r+1

Если   при   t=r   Fi  = Fi

(i=0,…,G),  то  процесс  вычислений  множеств  считаем     законченным

и находим множества Ni= (xx...х)#Fi( i=0,1,...,G), которые будут определять множества запрещенных наборов для вершин А0,…,AG   ГСА Г при минимизации Г в классе конечно эквивалентных ГСА.

Разработка общей методики минимизации граф-схем алгоритмов

Пусть задана ГСА Г(A, Р, Y, X), у которой A={Ao,..., AG+1 } - множество операторных вершин (Aо  – начальная, AG+1  – конечная), P – множество условных вершин, Y={Y0,..., YT+1,YT+2} – множество

операторов (Y0– начальный, YT+1-конечный, YT+2 – фиктивный оператор пустого периода, который не записан ни в одной из вершин Γ), X={x1,...,xL} – множество логических переменных. Пусть распределение

сдвигов для ГСА Г задано соответствием Yt → B0   ,B1 ,Bx

,B‾x  ,B

. (t=0,1,…,Т).

t          t         t            t        t

И  пусть  задан  автомат  Мура  S  (As  ,Ζ  ,Υ,δ,λ,a0,aK+1,aK+2),  где  As   –  множество  состояний, Ζ - множество входных сигналов – всевозможных наборов значений логических переменных x1, ..., xL, Y={Y0,..., YT+1 , YT+2} – множество выходных сигналов, δ: As * Z→ As – функция переходов, λ: As →Y – функция выходов, а0 – начальное состояние, aK+1 – первое конечное состояние, aK+2 – второе конечное состояние (назовем его состоянием пустого периода), причем  λ(а0)=Y0 ,  λ(aK+1)=YT+1 , λ(aK+2)=YT+2.

Последовательность наборов ζ= Δ 1 Δ 2 ... будем называть допустимой для автомата S , если при подаче её на вход автомата, начиная с состояния a0, всюду определены его переходы. Обозначим через ΣS множество всех допустимых последовательностей наборов для автомата S , а через ΣГ множество всех допустимых последовательностей наборов для ГCA Г при заданном для Г распределении сдвигов.

Будем говорить, что автомат S реализует ГСА Г, если ΣГ Í Σs и для любой последовательности наборов ζÎ ΣГ реакция автомата S на последовательность ξ совпадает со значением ГСА Γ на этой последовательности.

Очевидно, что если S реализует Γ и М - множество всех ГСА, эквивалентных Г, то S реализует любую ГСА из М.

Будем говорить, что автомат Мура S интерпретирует ГСА Г, если K=G и состояния автомата S можно перенумеровать так, что для любого набора Δm ÎΖ и для любого состояния ai Î As (ai ≠aK+1 , ai ≠aK+2) будет выполняться следующее:

• δ(ai, Δm)=aj↔ ( ΔmÎ Ki)& αij(Δm)=1;
• δ(ai, Δm)=aK+2 ↔( ΔmÎ Ki)&αij(Δm)=0 для любого j;

3)  λ(аi)=Yt , если и только если в вершине Ai записан оператор Yt,

где Ki - множество наборов, которые могут образовывать логические переменные x1,..., xL непосредственно после выполнения оператора Yt в вершине Ai при выполнении ГСА Г на всевозможных допустимых последовательностях наборов.

Очевидно, что:

• если автомат S интерпретирует ГСА Г, то S реализует Г (обратное, вообще говоря, неверно);
• с точностью до обозначения состояний, для любой ГСА Г существует единственный интерпретирующий ее автомат.

Пусть  M  –  множество  всех  ГСА,  эквивалентных  заданной  ГСА  Г;  MA

,  MP

,  M   ,

M -

min

min

min

множество ГСА, минимальных в М соответственно по числу операторных вершин, по числу условных

вершин и по суммарному числу операторных и условных вершин; R – множество всех автоматов, реализующих Г.

Рассмотрим задачи нахождения для ГСА Г граф-схем из множеств MA

, MP         M   .

min

min,

min

Очевидно,   что   задача   нахождения   ГСА  из   M A

может   быть   решена   путем нахождения

автомата Smin минимального в R, и построения по нему одной из интерпретируемых им ГСА.

Однако, получение автомата Smin Î R путем минимизации автомата S, интерпретирующего заданную ГСΑ Г, может быть гарантировано только в том случае, когда в R не существует автомата S' , покрываемого автоматом S, но не покрывающего S, т.е. когда ΣS= ΣГ , что часто не выполняется.

Рассмотрим сначала случай, когда для ГСА Г задано универсальное распределение сдвигов. Тогда N i = Æ, где Ni – множество запрещенных наборов для вершины Аi ГСА Г. Следовательно, для всех состояний из множества АS , кроме конечных, функция переходов δ автомата S, интерпретирующего Г, определена при любом входном сигнале, т.е. S – полностью определенный автомат (не учитывая неопределенные переходы из конечных состояний). Отсюда следует, что ΣS= ΣГ и единственный минимальный в R автомат может быть найден путем разбиения множества состояний автомата S на максимальные классы эквивалентности и отождествления состояний каждого класса (см. [1]) .

Общую  методику  решения  задачи  нахождения  ГСА  из   множеств  MP      ,       M

для   ГСА  Г

min

min

с универсальным   распределением   сдвигов   обосновывает   следующая   теорема,     сформулированная

и доказанная автором данной статьи в работе [11] (здесь доказательство опускаем).

Теорема.  Пусть  M  -  множество  всех  ГСА,  эквивалентных  заданной  ГСА  Г  с универсальным

распределением сдвигов; M A

P

min

Í M – множества ГСА, минимальных в М по числу операторных и

условных вершин соответственно. Тогда M A

min  ≠ Æ

Следствие. Пусть Mmin  Í М – множество всех ГСА, минимальных в М по суммарному числу

вершин. Тогда Mmin =M A

P

min  .

Из следствия ясно, что множество всех ГСА, минимальных в M A

по числу условных  вершин,

совпадает с Mmin, а  так  как  минимальный  автомат  Smin   Î  R  интерпретирует  любую  ГСА  из MA

, то

построив по нему ГСА, минимальную по числу условных вершин среди всех граф-схем, интерпретируемых автоматом Smin , получим некоторую ГСА Г'Î Mmin.

Таким  образом,  для  ГСА  с  универсальным  распределением  сдвигов  обоснована     следующая

методика их минимизации:

1. Строим полностью определенный автомат S, интерпретирующий заданную ГСА Г'.

2. Для автомата S находим эквивалентный ему минимальный автомат Smin.

• Находим ГСА Г', минимальную по числу условных вершин среди всех граф-схем, интерпретируемых автоматом Smin(эта задача будет рассмотрена в одной из следующих статей автора).

В результате получим ГСА Г'ÎMmin  = M   A

P

min

, т.е. ГСА, которая будет минимальной по   числу

условных, по числу операторных и по суммарному числу вершин среди всех ГСА, эквивалентных Г.

Если же для ГСА Г задано неуниверсальное распределение сдвигов, то в общем случае ΣГ ≠ ΣS, а ΣГ Í ΣS , где ΣГ и ΣS множества допустимых последовательностей наборов для ГСА Г и автомата S, интерпретирующего Г. Следовательно, автомат, минимальный среди всех автоматов, покрывающих S, может оказаться неминимальным во множестве R всех автоматов, реализующих Г.

Среди методов, учитывающих заданные распределения сдвигов для построения частичного автомата, лишь метод из работы [8] позволяет для исходной ГСА Г с неуниверсальным распределением сдвигов находить автомат S’ такой, что ΣS’= ΣГ . Этот метод будет рассмотрен в одной из следующих статей автора. Там же предлагается эффективный точный метод минимизации получаемого частичного автомата. Метод работы [8] предложен для построения частичного управляющего автомата по заданным полностью определенному управляющему автомату Мили и функции редукции. Рассматриваемая в [8] функция редукции является более общим распределением сдвигов, чем заданное в виде соответствия Yt

→ B0

,B1  ,Bx

,B‾x   ,B

. (t=0,1,…, Т). Метод может быть очевидным образом изменен для нахождения

t           t          t             t         t

частичного автомата Мура.

Отметим, что автомат, получаемый с помощью метода [8] может иметь число состояний значительно большее, чем число операторных вершин в исходной ГСА Г. Однако только при минимизации  такого  автомата  можно  гарантировать  нахождение  автомата,  минимального  в  R,       а,

следовательно, и ГСА из множества MA        .

Автором данной статьи в работе [11] показано, что для ГСА с неуниверсальным распределением сдвигов приведенная выше теорема в общем случае не выполняется. Таким образом, требования оптимального доопределения неопределенностей при минимизации операторных и при минимизации условных вершин могут быть противоречивы, и для ГСА Г с неуниверсальным распределением сдвигов может оказаться, что

MA                    P                A

min ∩ M min =M min ∩  Mmin=

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

MA                        P                 A

min  ∩ M

min =M min  ∩ Mmin=; то в общем случае не ясно, каким должен быть автомат S Î R ,

чтобы известные методы минимизации числа условных вершин гарантировали бы нахождение ГСА из

min   или Mmin .

Таким образом, раздельное решение задач минимизации числа операторных вершин и числа условных вершин с использованием известных методов не гарантирует для ГСА Г с неуниверсальным

распределением сдвигов нахождение граф-схем из множеств  MP

и M    . Совместное же решение задач

min

min

минимизации числа операторных и числа условных вершин для гарантированного нахождения ГСА из

множеств  MP

и  Mmin

(если  бы  такие  методы  были  разработаны)  вряд  ли  было  бы    практически

приемлемо из-за чрезвычайно большого объема вычислений, так как даже раздельное точное решение

указанных задач на ЭВМ возможно лишь для сравнительно простых ГСА. Поэтому в настоящее время, на наш взгляд, для минимизации достаточно сложных ГСА практически неизбежно применение приближенных методов. В качестве общей методики минимизации ГСА, которая, хотя и не гарантирует нахождение минимальных решений, но позволяет получать их довольно близкими к минимальным, может быть использована предложенная выше методика минимизации ГСА с универсальным распределением сдвигов. Сформулируем её применительно к ГСА с любым распределением сдвигов:

1. Для операторных вершин Ao, ..., AGзаданной ГСА Г находим множества запрещенных наборов значений логических переменных (соответствующие методы были описаны выше).
2. Строим автомат S , интерпретирующий ГСА Г (для ГСА с неуниверсальным распределением сдвигов автомат S чаще будет частичным).
3. Минимизируем число состояний автомата S , используя для этого точные или приближенные методы минимизации.
4. Находим для автомата Sтin, полученного на предыдущем шаге, одну из интерпретируемых им ГСА, минимальную или приближено минимальную по числу условных вершин.

Задачи первых трех этапов могут решаться в соответствии с изложенным в одной из следующих

статей автора. При этом всегда гарантируется нахождение ГСА из множества М A     .

Задача четвертого  этапа  представляет  собой  наибольшую  трудность,  хотя  для  реальных  ГСА с большим числом разветвлений выигрыш от минимизации условных вершин может быть значительно существеннее, чем от минимизации операторных вершин. Эти методы также будут рассмотрены в одной из следующих  статей автора.

Если задачу минимизации ГСА рассматривать в классе конечно эквивалентных ГСА, то при построении интерпретирующего автомата, а также на четвертом этапе вместо множеств Ki (i=0,…,G) следует использовать множества Fi. Кроме того, в интерпретирующем автомате будет отсутствовать состояние пустого периода а K+2 .

На основании вышеизложенного сформулированы следующие выводы:

1. При практических применениях ГСА задачу их минимизации целесообразнее рассматривать не в классе эквивалентных, а в классе конечно эквивалентных граф-схем.
2. Предложенный в данной статье способ нахождения множеств запрещенных наборов, необходимых при минимизации ГСА в классе конечно эквивалентных граф-схем, предпочтительнее существующих для машинной реализации.
3. Для гарантированного нахождения минимального автомата, реализующего заданную ГСА Г, необходимо предварительно найти автомат, область определения которого совпадает с областью определения ГСА Г. Нахождение такого автомата возможно с помощью метода из работы [8]. Автомат, интерпретирующий заданную ГСА, может не удовлетворять указанному требованию.
4. В любом непополнимом классе эквивалентных ГСА с универсальным распределением сдвигов подкласс граф-схем, минимальных по числу операторных вершин, пересекается с подклассом ГСА, минимальных по числу условных вершин. Это пересечение образует подкласс граф-схем, минимальных по суммарному числу операторных и условных вершин.
5. Требования оптимального доопределения неопределенностей при минимизации операторных и при минимизации условных вершин ГСА с неуниверсальными распределениями сдвигов могут быть противоречивы.
6. В настоящее время для минимизации сложных ГСА представляется неизбежным применение приближенных методов. В качестве методики нахождения приближенно минимальной ГСА можно рекомендовать методику, предложенную в данной статье.

СПИСОК ЛИТЕРАТУРЫ

• Баранов С.И. Синтез микропрограммных автоматов (граф-схемы и автоматы). – 2-е изд. – Л.: Энергия,
• Янов Ю.И. О логических схемах алгоритмов // Проблемы кибернетики: сб. ст. – 1958. – Вып. 1. – С. 29–53.
• Янов Ю.И. О локальных преобразованиях схем алгоритмов // Проблемы кибернетики: сб. ст. – – Вып. 20. – С. 255–259.
• Ершов A.П. Операторные алгоритмы 3 (об операторных схемах Янова) // Проблемы кибернетики: сб. ст. – 1968. – Вып. 20. – С. 181–201.
• .Ершов А.П. Введение в теоретическое программирование. – М., Наука,
• Горель Э.А. Об операторских схемах Янова с отношением конечной эквивалентности // Кибернетика. – 1971. – № – С. 63–65.
• Глушков В.М. К вопросу о минимизации микропрограмм и схем алгоритмов // Кибернетика. – – № 5. – С. 1–8.
• Чеботарев А.Н. К вопросу о взаимодействии двух автоматов // В кн.: Теория автоматов и методы формального синтеза вычислительных машин и систем. – Киев: Наукова Думка, 1968. – Вып.
• Сидоров Ю.Н. Автоматизация построения неполностью определенных управляющих автоматов

// В кн.: Теория релейных устройств. – Челябинск, 1976.

• Миллер Р. Теория переключательных схем. – М.: Наука, 1970.
• Наумов В.В. О минимизации числа вершин в граф–схемах алгоритмов // Приборостроение.

Известия Вузов СССР. – 1978. – № 8.