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

А1 А2 А3 Аj Аk

Условия функционирования МПУ можно описать также с помощью матричных схем алгоритмов. Матричная схема алгоритма - это квадратная матрица типа представленной на рисунок 4.6, строки которой обозначены символами операторов А ₀, А ₁,..., А _i,..., А_{к- 1}, а столбцам поставлены в соответствие символы операторов А ₁,..., А_i,... ,А_к.

А0 А1 Аi Аk-1

	Рисунок 4.6

Элементами a_ij матрицы являются логические функции перехода от операторов, соответствующих строке к операторам, соответствующим столбцу. Оператор А_j, сопоставленный с j -м столбцом матрицы, выполняется после оператора А_i, сопоставленного с i -й строкой матрицы, при тех комбинациях логических условий, при которых обращается в единицу логическая функция: а_ij=a_ij(x ₁ ,x ₂ ,...x_n).

Функция a_ij называется функцией перехода от оператора А_i к оператору A_j. Если функция перехода тождественно равна нулю (нулевая функция переходов), это означает, что операторы соответствующей пары никогда не выполняются последовательно друг за другом. Для простоты нулевые функции переходов a_ij =0 в матрицу могут не заноситься.

Логические функции переходы МСА обладают следующими свойствами:

1) a_ij·a_il =0, если j <> l;

2)

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

Из второго условия очевидно, что после оператора Аi всегда должен выполняться хотя бы один оператор. Таким образом, из этих двух условий следует, что после оператора A_i(i<>k) всегда выполняется только один оператор.

Из приведенного описания матрицы МСА следует, что оператором "Начало" обозначается верхняя (первая) строка матрицы, а оператором "Конец" - крайний (правый) столбец матрицы (А_к).