Автоматизация анализа вычислительной и емкостной сложности алгоритмов…
3
а
б
в
Рис. 1.
Модели базовых структурных конструкций:
а —
Следование (
G
1
);
б —
Ветвление (
G
2
);
в —
Цикл-пока (
G
3
);
Формальное описание структуры структурного алгоритма и
правила разбора таких алгоритмов определяет аксиоматика операции
свертки
factor( )
над сложными структурными конструкциями, также
описанная в [5]:
0
0
0
1 1 2 2
3 3
0
1
2
3
1
2
1 1 2 2
3 3
2
01 02
01 02
3
1 1 2 2
3 3
3
0
0
( )
,
(
{ ,
,
,
,
,
})
,
({ }
& { ,
})
,
( ,
& ,
{ ,
,
,
,
,
})
,
(
& { ,
,
,
,
,
})
,
i
k
F
F
F
F
F
С
F F
F
k
C
F
F
F
F
C
F
F
F
F
factor G G G
factor G G G G G G G G
factor G G G G G G
factor G G G G G G G G G G G G
factor G G G G G G G G G G
где
G
1
C
— кусок управляющего графа, соответствующий линейной после-
довательности операторов обработки данных, операторов Ветвления и
операторов Цикла-пока (в свою очередь, возможно, включающих внутрен-
ние структурные конструкции), т. е.
G
1
C
=
Ch
(
G
i
,
G
j
). Здесь
Сh
—
последовательность кусков, являющихся моделями указанных выше после-
довательных операторов, причем
(
k
=
,
i j
)
G
k
{
G
0
,
G
2
,
G
2
F
,
G
3
,
G
3
F
};
G
2
C
— кусок управляющего графа, соответствующий оператору ветвле-
ния (сложной структурной конструкции типа
G
2
), ветви которого
G
01
,
G
02
G
2
C
могут содержать вложенные структурные конструкции,
т. е.
G
01
,
G
02
{
G
1
,
G
1
F
,
G
2
F
,
G
3
,
G
3
F
};
G
3
C
— кусок управляющего графа,
соответствующий оператору Цикла-пока (структурной конструкции типа
G
3
),
