malyshkin_ve_korneev_vd_-_parallelnoe_programmirovanie_multikompyuterov

y1 y2 . . . yn

Информационным маршрутом в модели назовем последовательность X1, X2, ..., Xk такую, что

i ((Xi F X) ((Xi F→Xi+l out(Xi)) (Xi X→Xi+1 F

Xi in(Xi+l))).

Маршрут вида XXi, …, XkX называется циклом. Модель называется ациклической, если не содержит ни одного цикла.

Так, модель на рис.7.4 является ациклической. Простейшим примером циклической модели является модель, изображенная на рис. 7.5.

Пусть V X, F F. Определим множество термов T(V,F),

порожденных V и F. Для t T(V,F) одновременно будут определяться следующие атрибуты терма:

in(t) - множество входных переменных; out(t) -множество выходных переменных;

var(t) - множество всех используемых переменных; top(t) - вершина терма;

248

oper(t) - множество операций; sbt(t) - множество подтермов; d(t) - глубина терма t.

Основным объектом теории является функциональный терм и многие далее рассматриваемые алгоритмы обрабатывают термы. По этой причине нам понадобится детальная терминология, связанная с описанием терма и его составных частей. Для удобства примем следующее соглашение. Если

М=(m1,...,mp), N=(n1,...,nq) - упорядоченные множества, то

МÈN={m1, ..., mp}È{n1., ..., nq},

МÇN={m1, ..., mp}Ç{n1., ..., nq}

и т.д. Таким образом, булевы операции над упорядоченными множествами будут рассматриваться как над неупорядоченными.

Формальное определение терма и его атрибутов задается следующими правилами.

1.Если хÎV, то х есть терм t, хÎT(V,F); in(t)=var(t)={х}; out(t)={х}, top(t)=х, оpеr(t)=Æ, sbt(t) состоит из единственного подтерма - самого терма t, d(t)=0.

2.Пусть t1, ..., ts входят в T(V,F) и для ti, i=1,...,s, все атрибуты определены. Пусть аÎF, in(a)=(x1,...,xs). Тогда терм t,

равный a(t1,...,ts), включается во множество T(V,F) тогда и только тогда, когда выполняется "i(xiÎout(ti)). Атрибуты терма t в этом случае определяются так:

249

s

in(t)= in(ti);

i =1

out(t)=out(a);

s

var(t)=( var(ti)) out(a);

i =1

top(t)=a;

s

ореr(t)= oper(ti)È{a};

i=1 s

sbt(t)= sbt(ti)È{t};

i =1

d(t)=max{d(ti): i=1,...,s}+1.

Зачастую, вместо “ терм t, равный a(t1,...,ts)”, будем просто кратко писать t=a(t1,...,ts). Это сокращение всегда легко будет отличить от предиката равенства.

Используем также следующие обозначения: символом t' t будем обозначать тот факт, что терм t' представляет собой подтерм терма t, а обозначение t'Ît будем употреблять в случае,

когда выполняется t' tÙt'¹t, то есть терм t' является собственным подтермом терма t. Кроме того, будем использовать понятие вхождения подтерма t' в терм t, связывая с ним конкретную позицию, занимаемую t' в записи терма t.

В дополнение к другим функциям определим функцию outt(t'), где t - терм, t' - вхождение подтерма t' в t, не совпадающее с самим термом t. Если t=а(t1,...,ts), in(a)=(x1,...,xs), то outt(ti)=xi,

250

i=1,...,s. Функция outt(t') показывает, какую переменную подтерм t' вычисляет в терме t. Мы будем также часто говорить, что подтерм ti вычисляет в терме t переменную xi.

В дальнейшем будем считать известной обычную процедуру построения по терму t представляющего его дерева и введем конструкцию расширенного дерева так: каждый фрагмент на рис 7.6.а заменяется на более содержательный фрагмент на рис. 7.6.б., в котором показаны и операции и переменные терма.

Рис. 7.6

Большое число формально введенных определений полезно проиллюстрировать примерами. Прежде всего, посмотрим, как строится вычислительная модель.

251

б)

Рис. 7.7.б

Пусть предметная область есть геометрия и необходимо описать понятие треугольник (рис.7.7.а). Напомним, что ключевая идея вычислительных моделей состоит в накоплении

252

множества различных алгоритмов предметной области и их взаимосвязей. Основными величинами, характеризующими треугольник, являются (рис. 7.7.а): x, y, z - стороны; p -

полупериметр; a, b, g - углы; hx, hy, hz - высоты треугольника,

опущенные на стороны x, y, z; s - площадь. Треугольни характеризуют и могие другие переменные и их взаимосвязи, но на текущий момент они не используются и не включаются в ПВМ.

Проанализируем ряд основных закономерностей,

связывающих эти величины. Из формулы a+b+g=180°, разрешая один из аргументов относительно двух других и вводя обозначение a(X,Y)=180°-X-Y, получим

a=a(b,g), b=a(a,g), g=a(a,b).

Аналогично, используя формулу p=(x+y+z)/2, имеем p=(x+y+z)/2=b(x,y,z);

x=2p–y–z =c(p,y,z); y=2p–x -z=c(p,x,z); z=2p– x– y=c(p,x,y),

где b(X,Y,Z) обозначает функцию (X+Y+Z)/2, а c(X,Y,Z) - функцию

2X–Y-Z.

Выражение высот через стороны приводит к следующим соотношениям:

hx =y×sing =d(y,g)=z×sinb=d(z,b); hy =x×sing =d(x,g)=z×sina=d(z,a);

253

hz =x×sinb =d(x,b)=y×sina=d(y,a).

К ним следует добавить все обратные соотношения вида y=hx/sing; g=arcsin(hx/y) и т. д.

Наконец, площадь может быть получена по формулам s=xhx/2=f(x,hx)=yhy/2=f(y,hy)=zhz/2=f(z,hz)=

p( p − x)( p − y)( p − z) =g(x,y,z).

(В последнем обозначении переменная p исключена, так как ее можно выразить через x, y, z). Конечно, выписанный список закономерностей, как и используемых параметров треугольника,

не является полным, но он достаточен для иллюстративных целей.

Приведенные соотношения показывают принципиальную возможность вычисления одних параметров треугольника через другие. Для реализации этой возможности необходимо написать и включить в библиотеку программ соответствующие программные модули. Для нашего примера предположим, что на каком-то этапе эксплуатации в библиотеку включены модули для вычислений по следующим формулам:

p=b(x,y,z); s=g(x,y,z); s=f(x,hx); s=f(z,hz); hx =d(z,b);

(7.1)

hz =d(x,b); b=a(γ,a).

ПВМ, описывающая такое состояние системы, изображена на рис.7.7.б. Заметим, что в списках модулей (7.1) отсутствуют

254

отношения γ=a(α,β), α=a(β,γ), а также аналогичные соотношения для модулей f и d, хотя другие соотношения для этих модулей включены в (7.1), а, следовательно, эти модули должны быть программно реализованы. Кроме того, на рис.7.7.б имена модулей f и d имеют индексы. Все это является следствием определения ПВМ, принятого в этой главе. Для технических удобств простая модель определена так, что все операции имеют различные имена. Таким образом, операции для вычисления s=f(x,hx), s=f(y,hy), s=f(z,hz) считаются различными, несмотря на то,

что отличаются лишь входными переменными.

Теперь можно попробовать сформулировать и решить задачу на этой модели. Пусть есть возможность измерить две стороны треугольника x, z и два противолежащих им угла α и β.

Зная эти величины, требуется найти площадь фигуры. Это стандартная постановка задачи на вычислительной модели:

-известны значения переменных из некоторого подмножества V, здесь V={x,z,γ,α};

-требуется найти значения переменных из множества W,

здесь W={s}.

Анализируя структуру связей модели, видим, что с помощью модуля a можно вычислить из γ и α переменную β; модули d1 и d2

позволяют вычислить переменные hz и hx из переменных x, z, β; а

s можно найти либо из hx и x, либо из z и hz с помощью модулей f1

255

и f2. Таким образом, алгоритм вычисления s можно представить термами

t1 =f1(x,d1(z,a(γ,α))); t2 =f2(z,d2(x,a(γ,α)));

Значения определенных атрибутов для терма t1=f1(x,d1(z,a(γ,α)))

(рис.7.8.)

s

d1

β

z

a

α γ

Рис.7.8

следующие:

in(t1)={x, z, γ, α}, out(t1)={s}, var(t1)={x, z, s, γ, α, β, hx} top(t1)=f1 ; oper(t1)={f, d, a}; d(t1)=3;

sbt(t1)={t1, x, d1(z,a(γ,α)), z, a(γ,α), γ, α}

Подтерм t'=d1(z,a(γ,α)) t1, outt1(t')=hx. Подтерм t' вычисляет переменную hx в терме t1, терм t1 вычисляет переменную s. Это значит, что переменная hx входит в out(t1) и при соответствующей интерпретации значение переменной может быть вычислено при

256

реализации терма. Операция d1 используется в терме (операция входит в терм) t1 для вычисления переменной hx. Будем также говорить, что переменная hx входить в терм t1 (либо используется в терме t1).

В процессе разработки модели на рис.7.7.а было известно, что она строится для конкретной предметной области -

геометрии. Смысл всех объектов модели - переменных и операций - понятен (они интерпретированы) для нас.

Закономерности геометрии нашли свое отражение, во-первых, в

синтаксисе модели, т.е. в характере связей между операциями и переменными, во-вторых, в семантике, т.е. в специфике этих операций.

Когда модель построена и надо найти цепочку операций для вычисления одной группы переменных из другой, тогда ее семантические особенности уже не важны. В процессе планирования - построения цепочки - можно учитывать только синтаксис модели, абстрагируясь от специфики операций. В

общем случае, одна и та же вычислительная модель может соответствовать различным предметным областям и только сопоставление операциям различных конкретных функций

(процедур) определят ее специфику. Таким образом,

вычислительная модель является неинтерпретированным объектом. Именно абстрагирование от конкретной интерпретации позволяет с помощью лишь структурной

257