Файл: Основы теории алгоритмов учеб. пособие.pdf

-

20

-

кортежа

В

можно упростить,

умножив кортеж

A j

на число

его повторений R j

в множестве

В

. Для сокращения запи­

си множества

В

введем обозначения для одинаковых кортежей

так

что

Й

Л

-

А

Г

,

Такой кортеж будем на-

зывать сложным, т ,к ,

e j4 \эффективность не определена, Парамет-

ры нового элемента

A i *

можно вычислить по следующим зави-

симостям;

'<1

(Rj>

Ri

d j

•

(1.6)

ф '

- R, V

KfiJ

- К, .

- G, ■

после чего сложный кортеж превращается в простой.

Естественно,

что

и

Q

также будут изменять­

ся и могут быть вычислены для каждого конкретного случая.

■ Если алгоритм

В

содержит

программы

P j

, повторя­

ющиеся на наборном поле программы

Р р .

раз,

то их можно рас­

сматривать как некоторые алгоритмы

Д ;

,

повторяющиеся R;

раз, для которых применимы операции

(1 .6 ).

Рассмотрим случай,

когда алгоритм

А ]

повторяется

в цикле

N j

раз.

Обозначим такие

алгоритмы через

" А

и будем называть их кортежи сложными.

Для нахождения простого

кортежа

р . '

i '

очевидны следующие соотношения:

d

- ф

-

d j .

№

.

N

i t

,

■j

~

-

22 -

its " ( R j

+ 5 .

П

N ^ ) b ; ,

>

*

vr

i

4

' d

(1.9)

При

*?

=

0 система

(1.9)

преобразуется в систему

(1 .6 ).

При

R, -

о .

4J =

I получаем систему (1 .8 ).

Таким ооразом, если алгоритм

В

содержит множество

сложных кортежей,

то для перевода

их в простые можно., исполь­

зовать

систему преобразований

(1 .9 ),

после чего оистемы опе­

раций (1 .2 ),

(1 .3 ),

(1 .4 ),

(1.5) позволяют получить

В -

< Х а , Х г ь , . . . , X g s > .

Обозначим в

системе

(1.9)

Rj

+ Z

П N't;* =Si2 .

<I-I0)

4

V.L

4

4

Здесь ^ j i

-

число

одноименных

j -x алгоритмов, набран­

ных на наборном поле программы и подпрограммы;

опреде­

ляет количество обращений к данному

„

j -му

алгоритм в пронес

се реализации

алгоритма

£> .

Чиоленные значения

£ j L и

u j z

могут быть легко по­

лучены из операторной схемы алгоритма

0>

. Для этого над one

ваний.

В операторной схеме ш(декоом

р

обозначим алгоритмы,

размещенные на подпрограммном поле.

Кроме того,

стрелкой с чис

яоы М

над операторами обозначим,

что данные операторы на­

ходятся в

цикле о числом циклов N .

Например. Пусть алгоритм

имеет следующую опера­

торную схему:

^

М s С Вр Ар УС р Ур СС

( i . i i )

где С , 5 , р

I Д

,

, V - некоторые простые ал­

горитмы, кортежи которых определены.

х

W

A

- это алгоритм (группа алгоритмов),

который заключен в

цикл с

количеством циклов N

►Здесь

В соответствии

с (1 .8) для

"fc-j

,

если некоторый ал­

горитм Д

охвачен несколькими циклами с числом циклов N i .

N a .........

N y ,

то

его показатель степени

т

т .е .

Wa

а

П

N + ,

(1 л з)

Перешшем ( I .I 2 ) , используя

( I .I 3 ) ,

тогда

М* с ВрЛ’рf

ус у у

с'с

л ’ &’р М ^ р У ^ с .

(I .I4 )

Одноименные алгоритмы

с индексом

р

можно аапаоать

один раз, т .к . они на

наборном поле подпрограмм не повторяют­

ся,

причем показатели степени этих алгоритмов складываются.

Выделив эти алгоритмы в квадратные скобки а исключив г

них

индексы р

, получим