Способы построения циклических вычислительных процессов (стр. 3 из 4)

Логично предположить, что расчет числа путей надо начинать от начальной вершины. Но предлагается более простой алгоритм подсчета, начиная с вершин “результат”. Под вершиной “результат 0” поставим метку “1 / 0”, а под вершиной “результат 1” - метку “0 / 1”. На каждой дуге, заходящей в вершину “результат” поставим такую же соответствующую метку. Далее, для каждой вершины ЛБГ, начиная с последнего атома и следуя вверх, выполнить следующее. Сложить метки “a0 / a1” и “b0 / b1”, указанные на исходящих из данной вершины дугах, в результате чего получится метка “c0 / c1”, где c0 = a0 + b0, c1 = a1 + b1. Полученную метку поставить на каждой заходящей в данную вершину дуге. В результате над самой верхней вершиной ЛБГ получается метка “s0 / s1”, где s0 - число нулевых путей, то есть число путей, определяющих результат 0, а s1 - число единичных путей, определяющих результат 1.

5. Число путей во фрагментах, содержащих циклические операторы

В структурированных программах циклические операторы могут быть сведены к двум типам фрагментов: с проверкой условия цикла до входа в тело цикла и - после тела цикла (рис. 7). Число S путей таких фрагментов определяется четырьмя компонентами: числом Sp путей пролога цикла (где устанавливаются начальные значения переменных, используемых в условии и в теле цикла), числом St тела цикла ( в котором включим счетчики и другие операторы приращений) и числами S1 и S0 единичных и нулевых путей, соответственно, условия (“усл” на рис.7) выполнения цикла.

Рис.7. Два типа циклических операторов.

В первом случае (рис. 7,а) тело цикла может не выполниться ни разу, при этом анализируется S = Sp * S1 путей. Если условие выполнено хотя бы один раз, то анализируется S = Sp * S1 * St * S0 путей. По максимуму принимаем последнее выражение для определения числа путей в циклических операторах первого типа.

Во втором случае (рис. 7,б) тело цикла всегда выполняется хотя бы один раз, даже, если условие не выполняется. При этом анализируется S = Sp * St * S0 путей. Если же условие цикла выполнится хотя бы один раз, то число путей S = Sp * St * S0 * St * S1. С учетом того, что пути тела цикла анализируются только один раз, получим S = Sp * St * S0 * S1.

Таким образом, для любого из двух представленных типов фрагментов с циклическими операторами число анализируемых путей определяется выражением S = Sp * St * S1 * S0.

6. Условно-независимые фрагменты

Кроме циклических операторов фрагменты могут быть образованы операторами ветвления. Такими операторами являются условные (двоичного выбора) и операторы множественного выбора. Пример фрагмента с оператором двоичного выбора показан на рис. 2 (“фрагмент 1”). а с множественным выбором - на рис.3 (“фрагмент 2”). Фрагменты операторов выбора включают вершину, в общем случае, с целочисленной переменной (в том числе операция сравнения есть булева переменная с двумя значениями), из этой вершины исходит по крайней мере две помеченые дуги, заходящие в вершины, соответствующие операторам нижнего уровня и являющиеся вложенными фрагментами, которые и будем называть условно-независимыми. Такое название объясняется тем, что с позиции расчета числа путей эти вложенные фрагменты не зависят друг от друга. Поэтому число путей во фрагменте с оператором двоичного выбора определяется так: вычисляются числа единичных и нулевых путей логического условия (при наличии булевых операций в нем), считается число путей в каждом из условно-независимых фрагменте, которое умножается на соответствующее число единичных (нулевых) путей, и полученные произведения складываются. Для операторов недвоичного выбора просто складываются числа путей условно-независимых фрагментов.

7. Структурный объем памяти модулей циклических программ

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

ЛСП усложняют анализ структуры модуля, так как при разборе очередного цикла необходимо помнить значения этих переменных, полученные в предшествовавшем цикле. Поэтому такого критерия как число маршрутов уже недостаточно. Введем новый критерий структурной сложности для МЦП с памятью, названный структурным объемом памяти (СОП) модуля. Введем обозначения: m - число ЛСП, используемых в модуле, i - порядковый номер маршрута модуля, содержащего всего S маршрутов, ai - число операций присваивания (инициализации, модификации) ЛСП на i-ом маршруте. Значение СОП определяется выражением

где “max” - операция взятия максимума из двух переменных.

Здесь предполагается, что S вычислено по РСМ. Нижняя оценка СОП вычисляется в предположении, что каждой переменной (ЛСП) на одном маршруте присваивается не более одного нового значения: Pmin = m * S.

Для уменьшения СОП следует так изменить МЦП, чтобы уменьшилось число ЛСП и число путей S. Этого можно добиться, создавая независимые или условно-независимые фрагменты с заменой нескольких ЛСП, определяющих маршруты фрагмента, на одну ЛСП с образованием множественного оператора выбора. Решение данной задачи обеспечивается типовой реализацией МЦП, рассматриваемой ниже.

8. Реализация модулей циклических программ С-автоматами

В качестве типовой реализации МЦП с ЛСП предлагается использовать модель С-автомата [6], ориентированную на программную реализацию. Применение моделей конечных автоматов в программировании не ново (например, [7]). В частности R-технология [8] использует модель автоматов Мили, а технология программирования алгоритмов логического управления [9] использует модель автоматов Мура. Программы различного профиля, в том числе и логического управления, требуют, в общем случае, объединения указанных моделей в одну, то есть использовать С-автомат [10].

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

Алгоритм МЦП задается графом переходов С-автомата , пример которого изображен на рис. 8. Граф содержит три вершины, отмеченные внутри прямоугольников, им соответствующих, дробными отметками. В числителе указан идентификатор состояния (символы a,b,c), который может быть либо целым произвольным числом либо произвольным символом. В знаменателе указан идентификатор оператора (Za,Zb,Zc), обязательно выполняющегося в данном состоянии. У вершины может быть петля, также отмеченная дробъю, в числителе которой указано условие, например Xa, а в знаменателе - идентификатор оператора, соответственно Ya, выполняющегося, если условие Xa = 1 (без перехода в другое состояние). Вершины связаны дугами, помеченные аналогично, например, дуга из состояния “a” в состояние “b” отмечена дробью “Xab/Yab”, где Yab - оператор, выполняемый при наличии условия Xab, и после реализации Yab новым состоянием автомата становится “b”. Условия, помечающие дуги, исходящие из одной вершины, включая петлю, должны быть попарно ортогональны.

Рис.8. Граф переходов С-автомата.

Практика программирования показывает, что, в общем случае, переход из одного состояния, например из “а”, в другое состояние, например в “с”, может осуществляться с реализацией не одного (Yac), а нескольких операторов, следующих в соответствии с выполнением ряда условий. Например, по условию Xac1 реализуется оператор Yac1, и выполняется переход из “а” в “с”; по условию Xac2 реализуется оператор Yac2, и выполняется такой же переход. Ортогональных условий вида Xack одинакового перехода из состояния “а” в состояние “с” с реализацией соответствующих операторов вида Yack может быть несколько (k = 1,2,...,Lac). Таким образом граф С-автомата, в общем случае, является мультиграфом.

9. Типовая структура модуля, реализующего С-автомат

Типовая структура МЦП, реализующего С-автомат (согласно рис.8) представлена на рис.9, где используется оператор множественного выбора [11] для определения состояния Т автомата. При этом образуются три похожих условно-независимых фрагмента, первый из которых включает компоненты (Za, Xa, Ya, Xab, Yab, Xac, Yac). Этот фрагмент, в свою очередь, включает снизу-зависимый фрагмент Za. Из этого следует достаточно простой расчет числа условных путей в МЦП:

S = D(Za) * [E(Xa) * D(Ya) + F(Xa) * E(Xab) * D(Yab) +

+ F(Xa) * F(Xab) * E(Xac) * D(Yac) + F(Xa) * F(Xab) * F(Xac)] +

+ D(Zb) * [E(Xb) * D(Yb) + F(Xb) * E(Xba) * D(Yba) +

+ F(Xb) * F(Xba) * E(Xbc) * D(Ybc) + F(Xb) * F(Xba) * F(Xbc)] +

+ D(Zc) * [E(Xc) * D(Yc) + F(Xc) * E(Xca) * D(Yca) +

+ F(Xc) * F(Xca) * E(Xcb) * D(Ycb) + F(Xc) * F(Xca) * F(Xcb)].

Здесь обозначены: D(Za) - число путей во фрагменте Za, E(Xa) - число единичных путей в ЛБГ, реализующем логическое условие Xa, F(Xa) - число нулевых путей в этом ЛБГ.