Формальная постановка задачи структуризации алгоритмов - page 8

G 01 , G01 ⊂ G 2C могут содержать вложенные структурные конструк -
ции , т. е.
G01 , G 02 ∈ {G1 , G 1F , G2 , G 2F , G3 , G 3F };
G 3C — кусок управляющего графа, соответствующий оператору цикла-
пока (структурной конструкции типа G3 ), тело которого G0 ⊂ G3C
может содержать вложенные структурные конструкции , т. е. G 0 ∈
∈ { G1 , G1F , G 2 , G2F , G 3 , G3F }.
Таким образом , получаем множество моделей конструкций, изо-
морфных базовым G B и получаемых из сложных посредством свертки:
GBF = {G 0F , G1 F , G2F , G 3F }.
Формальная постановка задачи структуризации алгоритма.
Формально задачу структуризации алгоритмов можно поставить сле -
дующим образом .
Выполнить преобразование
GУН (< X1 , T >, < U1 , P >) F1 −→ GУС (< X2 , T >, < U2 , P >) и
G ДН ({< X1, T >, < Y 1 , < W1 , C1 >>},
{< −→V 1
1 , T 1
1 >, < −→V 2
1 , < T 2
1 , D3
1 >> }) F1 −→
F1 −→ GДС ({< X2 , T >, < Y2 , < W2, C2 >>},
{< −→V 1
2 , T 1
2 >, < −→V 2
2 , < T 2
2 , D3
2 >> }),
такое что
(∀i ∈ I ) AН (Si ) = AС (Si ),
где GУН и G УС — куски управляющих графов неструктурной и струк-
турной программ без вершин , сопоставленных началу и концу програм-
мы; S = {Si /i ∈ I } — множество всех допустимых наборов входных
данных задачи, для решения которых предназначен данный алгоритм;
AН — неструктурная программа, управляющим графом которого явля-
ется граф GУН ; AС — структурная программа, соответствующая пре -
образованным графам G УС и G ДС ; при выполнении следующих усло -
вий , вытекающих из свойств алгоритмов:
|X1| |X2| , X1 ∩ X2 = ∅,
|U1 | |U2| , U1 ∩ U2 = ∅ ;
и существует разрезание B куска графа GУС на совокупность кусков
В (G УС ), удовлетворяющих условиям
ISSN 0236-3933. ВестникМГТУ им . Н .Э. Баумана . Сер . “Приборостроение”. 2005. № 3 71