1.1.3. Логические схемы алгоритмов (лса).

ЛСА – это более компактная, но менее наглядная форма представления ГСА. В ЛСА используют:

• символы операторных вершин Y_j

• символы условных вершин X_j

• ^I, ^I –верхние и нижние стрелки. Верхние стрелки ^I ставятся после символов условных вершин X_j и их надстрочный индекс I указывает номер нижней стрелки ^I , к которой надо перейти, если X_j = 0)

• W ^I – безусловный переход, где i - номера переходов к нижней стрелке ^I.

Для правильной записи ЛСА отметим на ГСА (рис.1) номерами 1, 2 и 3 вершины, к которым подходят более одной стрелки. Перед символами этих вершин в ЛСА ставятся нижние стрелки с отмеченными на ГСА номерами.

Если возникают затруднения при записи ЛСА, можно вводить дополнительные нижние и верхние стрелки и использовать безусловный переход W ^I.

ЛСА, соответствующая ГСА на рис.1 имеет вид:

Y_н ¹ X₁ ¹ Y₁² Y₂ X₂² Y₄ X₃³ Y₃ ³ Y_k

1.1.4. Формулы переходов.

Формулы переходов описывают все пути между операторными вершинами в ГСА . Они имеют вид:

Y_m  U b_msּY_s – и описывают все возможные переходы из вершины Y_m в вершины Y_s, где:

b_ms = ∩ X_sj – произведение логических условий, записанных в условных

^j вершинах ГСА, лежащих на пути из Y_m в Y_s . Если выход из условной вершины X_k по стрелке «1», то в ∩ записывается X_k, если «0» – то записывается X_k ( - символ операции «инверсия»).

Формулы переходов, соответствующие ГСА на рис.1 имеют вид:

Y_н  X₁Y₁  X₁Y_н

Y₁  Y₂

Y₂  X₂Y₂  X₂Y₄

Y₃  Y_к

Y₄  X₃Y₃  X₃Y_к

1.1.5. Матричные схемы алгоритмов (мса).

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

Ym\ Ys	Yн	Y1	Y2	Y3	Y4	Yк
Yн	X1	X1
Y1			1
Y2			X2		X2
Y3						1
Y4				X3		X3

1.1.6. Преобразование гса с помощью формул переходов.

Преобразование основано на разложении булевых функций переменным.

Например.

Дан фрагмент ГСА (рис.2а). Запишем формулу перехода Y₄U b_4sּY_s:

Y₄  X₂ X₁ Y₅  X₂ X₁ Y₁  X₂ X₁ Y₁  X₂ X₁ Y₇.

Данному фрагменту ГСА соответствует следующее разложение формулы перехода по переменным X₁ и X₂:

Y₄X₂(X₁Y₁X₁Y₅)X₂(X₁Y₁X₁Y₇).

Разложим исходную формулу по переменной X₁:

Y₄X₁(X₂₁Y₁X₂Y₁)X₁(X₂Y₅X₂Y₇)

 X₁Y₁X₁(X₂Y₅X₂Y₇).

Этому разложению соответствует фрагмент ГСА, приведенный на рис.2б.