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

Скачать файл
Заказать решение

ВУЗ: Не указан

Категория: Не указан

Дисциплина: Не указана

Добавлен: 24.10.2024

Просмотров: 87

Скачиваний: 1

ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.

 

- 25

-

Ajt К

• ' • ,

( j - C O t t s i ,

l * i,2 ,„ .t

Hj) ,

( I . 17)

где

l

лено " j

-

номер алгоритма

no

j -ой операции;

-

общее число

этих алгоритмов в

j -ом наборе.

ли имеется

И1

операций я по кавдой операции состав

 

алгоритмов,

то

общее число таких алгоритмов равно

В развернутом виде такая система представляется следующей!

 

 

( I . 18)

л 55 К ЭСш, Х а з , . .

,

>

12 — t^Cl21, № ш , - •

* X i i j >

>

ifli —К X ilii, #1*1,2, • •

>X i n t y

>

V

 

^ 2 1

®*

^

X a n ,

X n t , • • • > ?Caij>

^

N

< /Aaa

*

^

# * i t ,

РСлп, * • • >

f

>

# • *

 

*.< • • • * • < » • * » ♦ •

 

 

/4 a/7г =

^

 

Xin»i, • • • » Яиц**

>

 

*

 

 

 

 

 

 

Д mt

“

^ X m it(X«m, • • • >Xnuif

>

 

J/AtfU

“

^

X t m i , X m u t • ••, ЭСтгф >

” ,Xmnm{ >

Из множества алгоритмов системы (1,18) можно составите

шокество Р * { ^ ] решений некоторого алгоритма Б

, где

§* 1 , 2 , . . . , S ; ( S - число решений). Каждое^ -

решение характеризуется тем,

что из каждого набора ( j =

c o n s t) внбираетоя до одному алгоритму,

который может быть

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

. Тогда число всевозмож­

ных решений

т

 

S - QHj.

 

4

1

 

 

 

Для более удобного сравнения однозначных параметров ал­

горитмов системы (I.I8) представим их в виде матриц однознач­

ных параметров.

 

 

 

 

Кортежи одного простого алгоритма, например,

 

X tu ( X ju , •••> Х н ц ^

можно записать в виде системы порядка £

однокомпонентных

матриц

:

 

 

 

 

4 *

I

1

(1,19)

 

Х<а *

XJ

|

 

 

Вели алгоритм повторяется нЪ наборном поле програгш R , рае, то система (1*19) является сложной и переход к простой системе соответствует умножению однокомпонеатных

- 27 -

матриц Хр на однокомпонентную матрицу

|Rt| .

При этом

операция умножения Хр для d , t ,

К , &

н а | в , {

должна проводит^оя в соответствии, о сиотемой оптация

(1 .6 ):

 

| d m

 

R i

| d m

R i 11

(1.20)

 

 

 

 

 

 

 

 

■Ьш

 

R i

Jt* it

R i

J*

 

 

 

 

K iU

• | R .

К m l

»

 

 

 

 

G i u

T

‘

G m

 

 

 

 

 

 

 

 

 

ttl

 

 

Рассмотрим матриц» однозначных параметров для

 

 

(

j - 1 , 2 , . . . , ГП

),

полагая,

что для кадой

j

-« •

операции имеетоя по одному проотону алгоритму (

Н; *

I ) . За­

пишем матрица однозначных параметров в вика терт

’

 

 

X т j

X in i Xjtt j • • * 9Cmu j

 

 

 

 

X a ■ |

X h*

Xtct • • ♦ X mu |

(IJ2 I)

 

 

 

 

 

 

 

a

 

 

 

 

X iip

 

• * • X w tx j| t

 

 

 

Пусть теперь имеется одна операция ( торой составлен набор t -ых ( i = 1 ,2 ,. мов. Тогда

m

=

I ) ,

дмя ме-

♦

Hi

 

« ■ "!■ * -

Xi -

Хг

X iii

Xi a t

** •

X i e ,! ,

X u t

(1.22)

X m

 

9

- 28 -

Hi f

 

Как ввдим, здесь матрица сворачивается в одну колонку

при

Hi

строках,

 

j

 

1 ,2 ,3 , ..., Ml

 

 

В общем случае для

=

и 1 = 1 ,2 ,... ,

ttj

однозначные параметры цростых алгоритмов

могут быть

представлены в виде системы порядка

? многокомпонентных

матриц:

 

 

 

*

•

X l тир

 

 

 

 

Х д р

•

 

 

х

X1iiij*

X u p

■

'

‘

X i i i j p

 

 

у —

 

 

 

 

 

 

 

 

 

X<Hip

X щгр

 

*

*

Xm nmp

 

 

 

( f =

i, 2 , . .

■ ><L

) .

(1.23)

 

 

 

 

 

 

 

 

 

 

 

 

 

И большинстве практических случаев матрицы X)j» не яв­ ляются прямоугольными, так как число алгоритмов в наборе мо­ жет быть различно, т .е .

П%Ф Мг • * ' 4* Пт .

Матрицу (1.23) будем считать простой в том случае, ког­ да она составлена из компонент простых алгоритмов. Если же в

нее входит хотя бы одна компонента сложного

кортежа

,

то Х р назовем

сложной и обозначим через

3 # f •

 

Так как в матрице записаны количественные значения

 

параметров

и отсутствуют индексы кортежа, то надпишем

над каждой колонкой ее алгоритм Ед , к которому относится данная колонка.

 

 

 

 

 

 

 

 

 

-2 9 -

 

 

 

 

 

 

 

Пусть матрица

 

# j>

сложная и составлена из

компонент

 

ояокных кортежей

 

Ej

,

тогда

 

 

 

 

 

 

 

 

 

Ei

 

 

 

 

 

 

 

Егг)

 

 

 

 

 

 

 

З х ,-

ЭСир

 

 

 

 

 

• • • X W p

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

XitUf)

 

iCutif

' '

•

 

 

 

 

 

(1.24)

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

p

-

 

i,

2,

• • •,

.

 

 

 

 

 

 

 

Для перехода

от

 

 

 

простой матрице

ЭС f>

составим

 

дополнительно матрицу-строку

 

t-< i в которой запишем необхо­

 

димые для преобразований по системе (1.9) численные значения

 

( j

-

( ( R j

-t V j),

( R j

+

^

П

N

^

) j .

 

 

Пусть

 

 

 

 

 

^

 

f

^i> v j

tt*

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Тогда

 

, f

 

 

 

 

 

 

 

V

1

*"1

1

 

 

 

 

 

L

“ I f t u , t u j

 

 

 

 

f t m i , t m i ] |

 

 

или

 

 

 

L = U

 

L---U\.

(1.25)

 

 

 

 

 

 

 

 

 

 

 

Переход

от

 

J X f K

tfp

осуществляется

путем умножения

матрицы-строки

L

 

на

каждую матрицу Э х ? в

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

 

соотношения!.ш Л . 9 ) .

 

При этом

 

умножается на каждую ком­

 

поненту колонки

E t,

 

£z — на

Е г , . . . ,

£,Ц1 —

н а

£ m .

 

В множестве

t j

 

величина

I j i

умножается на матрицу

$ d

,

a

-

на

J

i

 

 

.

 

 

 

 

 

 

 

 

 

 

 

Следует

заметить,

что

если все

W

операций в

алгоритме

В> повторяются

по одному разу,

то все компоненты матрици-

 

строки

| .

равны

единице,

тогда

J *

f -

* > •

 

 

 

Смотрите также файлы