Операторные схемы алгоритмов систем управления

Способы записи алгоритмов многообразны и, видимо, не исчерпываются существующими операторными схемами, наиболее применяемыми в дискретной технике. Известны также алгоритмы Маркова, Ван Хао, машины Тьюринга–Поста, которые используются в математической теории [1].

В программировании и в теории автоматов наиболее применимы оператор­ные схемы алгоритмов (ОСА) в форме граф-схем (ГСА), логических схем (ЛСА), регулярных схем (РСА), матричных (МСА) и таб­лич­ных схем (ТСА). Все виды ОСА эквивалентны, поэтому может быть осущест­влен взаимный переход (рис. 50) от одной формы к другой.

Замыкающие стрелки в графе рис. 50 отображают возможность эквивалент­ных преобразований самой формы ОСА без нарушения правильности алгоритма. Например, для ГСА рис. 51 формы а, б, в – эквивалентны. Однако переход от а) к в) допустим всегда, но от а) к б) – лишь в том случае, если по условиям работы опе­рационного устройства, которым управляет автомат, реализующий ГСА, воз­можно одновременное исполнение операторов А₁ и А₂.

Рис. 50

Рис. 51

Переход от ГСА к МСА осуществляется в следующей последо­вательности:

- составляется матрица с перечислением всех операторов действия А₁А₂…А _n А _к (где А_к – оператор окончания алгоритма – «end») в заголовке столбцов мат­рицы и операторов А₀А₁…А _n (где А₀ – оператор начала алгоритма) в перечис­лении строк;

- прямая связь А _i к А _j отображается 1 на пересечении соответствующей i -й строки с j -м столбцом;

- если связь осуществляется с проверкой логического условия, ставится α, соот­ветствующее значению «0» или «1», т.е. или α.

Однако часто при переходе от ГСА к МСА допускается ошибка, если не обо­значить новым номером А _{n+ 1} повторяющийся оператор А _i с записью примечания, А _n+1 = А _i. Например, для ГСА рис. 52 а правильная запись МСА, приведенная в табл. 22, может быть осуществлена только по рис. 52 б, где А₇ = А₂.

Рис. 52

Переход от ГСА к ЛСА неоднозначен и поэтому не формализован.

Определим формализованную процедуру преобразования ОСА, обеспечи­вающую однозначное преобразование ГСА в ЛСА. Для этого первоначально пре­образуем ГСА в ТСА по следующей последовательности действий:

1 - отметим на ГСА самый длинный путь от А ₀ до А _к (для рис. 52 а этот путь со­ставляет последовательность операторов 1, 2, …, 10, отмеченную «двойными» линиями;

2 - если на отмеченном пути встречается ветвь логического оператора α _i со значе­нием 1, то соответствующий оператор α_i заменяется оператором β_i, для которого β_i = ; тогда отмеченный путь будет проходить через операторы, без­условные переходы (стрелки) от А _i к A _j и через стрелки α_i со значением «0»;

3 - каждому оператору А _i, следующему со значениями α_i или β_j, равными «1», при­пишем метку (буква с цифрой, например Q₁, Q₂, …,Q _r);

Таблица 22

	А1	А2	А3	А4	А5	А6	А7	А к
А0
А1
А2
А3
А4
А5
А6
А7
А7 = А2

4 - нумеруются также последовательности операторов (по правилу 1, 2, 3) на уча­стках ГСА, не покрытых самым длинным путем;

5 - отмечаются также с помощью меток операторы, к которым подходят не­сколько стрелок.

По рис. 52 а осуществим переход к ТСА, т.е. запишем последователь­ность операторов отмеченного пути в столбик:

		А0
Q2		А1
		А2
		α 1	→ Q1
		А3
Q3		А5
		А2
		β 2	→ Q2
		А0
		А6
Q1		А4
			→ Q3

Здесь команда 12 обозначает безусловный переход на Q₃, а команды 4 и 8 – услов­ные переходы, например, команда 4 читается как «если α₁ = 1, то иди Q₁, иначе А₃».

Эти правила перехода от ГСА к ТСА рекомендованы для на­писания программ на алгоритмических языках низкого (ассемблер) и высокого уровня. Здесь же определим процедуру перехода от ТСА к ЛСА.

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

- запись операторов (команд) осуществим в строчку (развернем ТСА на 90° про­тив часовой стрелки);

- стрелки перехода по условиям α_i и β_j также повернем вверх и припишем им номера (индексы) i, j;

- метки Q _k заменим стрелками, направленными вниз, с индексами тех логических операторов α_i, β_j, которые определяют переход к Q _k;

- для безусловных операторов (в примере команда 12) так же определяются стрелки (вверх по команде и вниз по метке), но присваивается следующий по порядку номер после α_i, β_j;

- после оператора A _k ставится точка с запятой (;), если отмеченный путь не покры­вает всего алгоритма;

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

Для рис. 52 а по соответствующей ТСА получим ЛСА в виде:

A₀↓²A₁A₂α₁↑¹A₃↓³A₅A₂β₂↑²A₆A_k; ↓A₄↑³.

Вернувшись к первоначальному обозначению , получим окончательно

A₀↓²A₁A₂ α ₁↑¹A₃↓³A₅A₂ ↑²A₆A _k; ↓A₄↑³.

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

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

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

Глава 3