Графические схемы алгоритма

 

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

Поскольку ГСА предложена для алгоритмов операций ЭВМ, то в ней нет средств для отражения ввода-вывода.

Вместо блоков в ГСА используются вершины: начальные Y₀, конечные Y_к, операторные вершины Y₁,Y₂, …, условные вершины X1,X2, ….На рис.2 показана СА классического алгоритма нахождения наибольшего общего делителя (ННОД),

где: А и С - исходные числа,

НОД - наибольший общий делитель.

Видно, что заданные числа при А<С меняются местами (блоки 5¸7). Поскольку после этого получается А >С, то число А заменяется на значение

А - С. Подобные циклы повторяются до получения А= С (блоки 3¸8), число А и будет требуемым результатом (блок 9).

Имеются отличия применительно к условным вершинам. Прежде всего,

условие (чаще всего отношение) записывается в закодированном виде.

Если оно выполняется, то результату присваивается единичное значение, в противном случае - нулевое значение. С учетом этого выходы вершины отмечаются указанными значениями вместо “да” и “нет”.

Содержательная и закодированная граф-схемы алгоритмов представлены на рис. 2 и 3 соответственно, коды микроопераций у _i, микрокоманд Y_i и условий XI - в табл.1.

 

 

1

 

2

                       8

			A:=A-С

 

3

                                                    =

НОД:=А

 9

                                  ¹

 

4             >    

10

5 >

НОД:=А

                                   

                                                                              

11

6

	A:=С

 

 

7

	С:=НОД

 

 

 Рис. 2. СА ННОД чисел A и С

 

Условия корректности ГСА похожи на условия корректности схемы алгоритма [4]:

1) у ГСА должна быть одна начальная и одна конечная вершины;

2) каждый выход соединен только с одним входом операторных вершин;

3) каждый вход соединен, по крайней мере, с одним выходом;

4) выходы условных вершин помечаются с помощью цифр “0” и “1”;

5) из начальной вершины должен быть путь к любой вершине;

6) из любой вершины должен быть путь в конечную вершину;

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

 

Матричные схемы алгоритма

 

Матричная схема алгоритма представляет собой квадратную матрицу,

строки которой соответствуют вершинам с выходами, столбцы – вершинам с входами. На пересечениях строк и столбцов записываются функции перехода. Такая функция представляет собой конъюнкцию кодов логических условий (логических переменных), переменная пишется без инверсии, если выход осуществляется по 1, в противном случае переменная пишется с инверсией. Функция перехода, равная 1, соответствует безусловному переходу.

Для указанного выше алгоритма МСА (МСА ННОД) представлена в табл.2

Таблица 1

Коды микроопераций, микрокоманд и условий

 

Коды		Микрооперация, условие	Коды		Микро- операция, условие
микро- операции, условия	микро- команды		микро- операции, условия	микро- команды
y 1 y 2 y 3	Y1 Y2 Y3	НОД:=А А:=С С:=НОД	y 4 X1 X2	Y4	A:=A-C A=C A>C

 

 

Таблица 2

 

МСА ННОД	Y1	Y2	Y3	Y4	Y5	YK
Y0, 4	__ __ Х1Х2			__ Х1Х2	Х1
Y1		1
Y2			1
Y3				1
Y5						1

 

 

y 3

С: =НОД

                                                                                                                               Y₃

Y₀

A:=A-С

Начало

                  

y 4

               1                                                         1 Y₄

 

НОД:=A

      0                                                          0

y 1

                                                                                                   Y₅

               1                                                                 1

     0                                                          0

	НОД:=A		Конец

y 1

                                                                                                   Y₁                           Y_K                       

 

Y₂

y 2

A:=С

 

Рис.3. ГСА ННОД           Рис.4. Закодированная ГСА ННОД

 

Для МСА можно сформировать условия корректности:

1) в МСА не должно быть строки Y_k;

2) в МСА не должно быть столбца Y₀;

3) должны быть столбец Y_k и строка Y₀;

4) не должно быть пустых строк и столбцов;

5) на строке не должно быть одинаковых функций перехода;

6) на строке не должно быть сочетаний 1 и функций перехода через логические переменные;

7) в столбце могут быть одинаковые функции перехода;

8) на строке может быть только одна 1;

9) дизъюнкция всех функций переходов на строке должна быть равна единице;

10) разные строки с одинаковыми функциями переходов разрешается оформлять в одной строке с указанием всех индексов вершин старта.

По МСА можно упрощать алгоритмы и, следовательно, автоматы.

Системы формул переходов

 

Все переходы, соответствующие строке МСА, можно отразить в формуле переходов. Формул будет столько, сколько имеется строк в МСА. Получается система формул перехода (СФП).

Каждая формула переходов начинается с вершины, из которой рассматриваются переходы, в правой части формулы пишется дизъюнкция логических произведений вершин захода с соответствующими функциями перехода.

Между левой и правой частями формулы ставиться стрелка ®, которая отражает переходы от вершины левой части к одной из вершин правой части.

Переход совершается к той вершине, соответствующая функция перехода которой становится равной единице.

Для рассматриваемого алгоритма СФП включает в себя:

Y_0,4 ® Х1Х2Y₁+Х1Х2Y₄+Х1Y₅;

Y₁ ® Y₂;

Y₂ ® Y₃;

Y₃ ® Y₄;

Y₅ ® Y_K.

Применительно к СФП можно сформулировать условия корректности:

1) не должно быть формулы перехода для Y_к;

2)  в правой части любой формулы не должно быть вершины Y₀;

3) логическая сумма всех функций перехода любой формулы должна быть равна единице;

4) конъюнкция любой пары функций перехода формулы должна быть равна нулю;

5) в формуле не может быть одинаковых функций перехода;

6) у данной операторной вершины формул переходов может быть одинаковая функция перехода.

СФП позволяет производить формальные преобразования, упрощать алгоритм, следовательно, и автомат.

 

1234	Поделиться:

Воспользуйтесь поиском по сайту: