Математическая логика и теория алгоритмов [Г. И. Анкудинов] (pdf) читать постранично, страница - 9

Y=f(X).
Последовательные (линейные) структуры
Рассмотрим последовательность двух блоков g={(X,Y)} и
h={(Y,Z)}, изображенную на рис.2.1. Программная функция такой

*

Дал У., Дейкстра Э., Хоор К. Структурное программирование. – М: Мир, 1975.

X

p=
Рис.2.1.

Y

g

112

Z

h

последовательности является композицией h°g двух частных
функций h и g: [P]={(X,Z)⎥ Z=h(g(X))}.
Пример 2.13. Задана программа в виде последовательности операторов
присваивания на алгоритмическом языке PASCAL (рис.2.2). Требуется
определить функцию, реализуемую этим алгоритмом.
Рассмотрим поле данных (x,y,z), которое используется в данной
программе. Начальное значение поля данных (x0,y0,z0).
Процесс прослеживания состояния
x:= y + z; y:= x - z; z:= -x + y; поля данных после выполнения каждого
Рис.2.2.
оператора называется трассировкой. Его
удобно представить таблицей 2.1.
Таблица 2.1

Оператор

x

y

z

x:=y+z

x1=y0+ z0

y1=y0

z1=z0

y:=x-z

x2=x1

y2=x1-z1

z2=z1

z:=-x+y

x3=x2

y3=y2

z3=-x2+y2

После выполнения первого оператора присваивания первоначальное значение
x0 стирается и заменяется новым значением, x1=y0+z0, причем значения y и z не
меняются, т.е. y1=y0, z1=z0. После выполнения второго оператора присваивания
получаем:
x2 = x1= y0 + z0,
y2 = x1 - z1 = y0 + z0 - z0 = y0,
z2 = z1 = z0 .
После выполнения третьего оператора присваивания получаем:
x3= x2 = x1 = y0 + z0,
y3 =y2 = y0,
z3 = -x2 + y2 = -y0 -z0 + y0 = -z0.
Таким образом, функцию реализуемую алгоритмом, можно представить
как одновременное присваивание (x,y,z):= (y0+z0 , y0 , -z0) , в результате
которого первоначальное значение поля данных (x0,y0,z0) изменится на (y0+z0 ,
y0 , -z0).

113

Структуры с ветвлениями
Для программы с ветвлениями все возможные пути выполнения
определяются так называемым деревом выполнения (E-деревом).

f
X
p=

s

1

q

g

1
0

Y

0

h

r

1
0

Рис. 2.3.

Пример 2.14. Рассмотрим блок-схему программы на рис.2.3. Эта
программа имеет дерево выполнения, представленное на рис.2.4. Условия
ветвления выражаются предикатами s, q, r. Программная функция программы с
ветвлениями без циклов определяется как объединение композиций
программных функций, которые получаются непосредственно из E-дерева.
Необходимое и достаточное условие выполнения конкретной ветви
определяется композицией каждого предиката с предшествующей функцией
пути.
В рассматриваемом примере имеется пять путей выполнения,
пронумерованных как показано на рис. 2.4. Выпишем программную функцию
каждого пути:
1.

{(X,Y): s(X) & q(f(X)) & Y=g(f(X))}.

2.

{(X,Y): s(X) & ⎤ q(f(X)) & r(h(f(X))) & Y=g(h(f(X)))}.

3.

{(X,Y): s(X) & ⎤ q(f(X)) & ⎤ r(h(f(X))) & Y=h(f(X))}.

4.

{(X,Y): ⎤ s(X) & r(h(X)) & Y=g(h(X))}.

5.

{(X,Y): ⎤ s(X) & ⎤ r(h(X)) & Y=h(X)}.

114

f

1

q

0

1

h
s

g

1

g

2

r

0

3

1

g

0

h

1

4

r

0
Рис. 2.4.

5

Результирующая программная функция может быть определена как условное
правило:
[P]={(X,Y) ⎥ s(X) & q(f(X)) → Y=g(f(X));
s(X) & ⎤ (q( f(X) )& r(h(f(X)))→ Y=g(h( f(X)));
s(X) & ⎤ (q(f(X))) & ⎤ (r(h(f(X)))) → Y=h(f(X));
⎤ s(X) & r(h(X))→ Y=g(h(X));

⎯⎤ s(X) &⎤ (r(h(X))) → Y=h(X)}.
Пример 2.15. Задан алгоритм с использованием операторов ветвления
(Рис.2.5).

IF x