12

3. Граф-схемы алгоритмов.

Иногда с целью большей наглядности, особенно в случае простых алгоритмов, удобно представлять их с помощью языка графов. Такое формальное описание было предложено российским математиком Л.А. Калужниным [3].

Алгоритмическая систем такого вида получила название «граф-схемы алгоритмов» (ГСА).

Определение

Граф-схема алгоритма (ГСА) есть конечный связный ориентированный граф G, удовлетворяющий следующим условиям:

1.В графе G имеется два отмеченных узла – входной, из которого выходит не более одной стрелки, и выходной, не имеющий ни одной выходящей стрелки.

2.Из каждого узла, отличного от входного и выходного, исходит либо одна стрелка (γ-узел), либо две стрелки (β-узел). Стрелки β-узла помечены – одна плюсом, другая минусом или одна 0, другая 1.

3.Имеется два конечных множества функциональных элементов – множество преобразователей информации Q = {A1 , A2 ,..., An } и множество распознавателей P = {p1 , p2 ,..., pm }.

4.Каждому γ-узлу однозначно сопоставлен преобразователь Ai ÎQ , а каждому β-узлу – распознаватель al ( p1, p2 ,...)Î P. В зависимости от алгоритма преобразователи и распознаватели могут повторяться в графе G

Определение

Подграф-схема алгоритма есть связный подграф G* графа G, удовлетворяющий следующим условиям:

1.В подграфе имеется один входной γ-узел (может быть входной узел графа G), один или несколько выходных γ-узлов и β-узлов с помеченными стрелками.

2.Узлам подграфа G* сопоставлены те же самые функциональные элементы, что и узлам графа G.

13

Пример 3.1

Рис 3.1

На рис. 3.1 представлен некий алгоритм в терминах ГСА, где A1 – начальный оператор (входной γ-узел) A13 – конечный оператор (выходной γ-узел), а так же фрагмент алгоритма в виде подграфа.

Если связный подграф G* не имеет ни одного контура, то согласно терминологии подграфов мы будем говорить, что он содержит «дерево», вершины которого есть γ -узлы (A3, A4, A5, A6) вместе со своими выходными стрелками. В каждом дереве, имеющем более одной вершины, можно выделить «поддеревья». Последовательности вида p1 p2 A3 , p1 p2 A4 , p1 p2A5 , p1 p2 A6 будем называть «ветвями».

Из ранее сказанного следует, что множество преобразователей Q содержит операторы, а множество распознавателей P – логические функции. Входному узлу естественно сопоставить служебный оператор A0, символизирующий начало работы алгоритма, а выходному - конечный оператор Ak, означающий завершение работы алгоритма. Остальные узлы – операторы и ЛУ.

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

Будем считать две ветви ГСА (подГСА) равносильными, если они совпадают с точностью до порядка следования ЛУ. Два дерева также равносильны, если между их ветвями существует взаимно однозначное соответствие.

Назовём две подГСА равносильными если:

1.Входному узлу каждой подГСА сопоставлен один и тот же оператор

Ai.

2.Они содержат равносильные деревья ЛУ.

14

Назовём две ГСА равносильными, если между путями от входного оператора A0 до выходного Ak существует взаимно однозначное соответствие.

Будем говорить, что ГСА U1 равносильна ЛСА U 2 и МСА U 3, если при заданном распределении сдвигов при всякой допустимой последовательности наборов ЛУ значения их совпадают.

В разделе 2 приведён пример перехода от ЛСА U 2 к МСА U 1. Рассмотрим процесс перехода от МСА U 1 к ГСА U 3.

Пример 3.2

Построить ГСА U 3 равносильную МСА U 1 из примера 2.1. Вначале строим подграфы каждой строки МСА, а затем «склеиваем» совпадающие вершины

Рис. 3.2 (а)

15

В результате наложения одноимённых узлов получаем окончательно описание ГСА

Рис. 3.2 (б)

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

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