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

- 30

-

Данную методику перехода^ от сланных матриц к простым

можно применить в алгоритме £>

-

, содержащего разветвления.

При этом элементы

&j't

матрицы С .

составляются для

алгоритмов, находящихся на ветви о "Ь

а значения

->

для алгоритмов,

не входящих в ветвь о rkmatt.

Таким образом, множество наборов

H ji

может быть опи­

сано некоторой

£ -системой:

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

. Выбирая из какого набора но одному алгоритму,

мож­

но получить множество

|

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

& .

Задачу выбора наилучшего варианта набора алгоритмов,

составляющих алгоритм

D

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

если перед опти­

варительные операция над матрицами параметров.

Обозначим через 0

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

ми матрицы

.

Тогда при определении

для некоторого

-варианта

над выбраннымииз каждой колонки по одной

компоненте

# j l

матрицы

)Cj> проводится операция в

,

Например, для Х ? жЯ и

Й1=

4 имеем, что О

представля­

ет собой операцию сложения, т .е .

т

*

jEj

X j i .

алгоритмов.

I .

Если кошюяенты некоторого набора колонки E j

ны между собой

то

можно вывести за мат­

рицу. Например,

6 »

Шщ

) C u JCw

К+х

- 31

-

где число вариантов

S *

Г Т ^

=

3 4 2

3 = 72.

Пуоть компоненты голонкя

Е* X u * )С а * Х « в X i

а Е*.

1Счш Х и .ш Хи

. Тогда

Eg

Е<

К.

Б*

Kai

Х*<

л »

X u

X f -

K .Q * t 8

х «

X u

ХгЧ

(1*27)

Запись

(1 .27)епдержитыеныпее число вариантов, т.в.

S =

1 - Г 4 - 3

= 12.

2 .

Бели набор

состоит

только из одной компоненты

X u ,

то

ее можно вынести за матрицу.

3 .

Если компоненты X jl

матрицы Хр есть множества и

ву

Xji , то такие элементы можно вынести за матрицу без

обо­

значения принадлежностей к колонкам,

;

Например, в выражения

Eg

_

Et

Cg

( 1 . к> М

{ к» k g }

f k « k , k , j

( к . к , 1

{ к* kg k i }

( к . к . )

I U

( к» кi J

{ к . k . i

( к , 1. 1

1 к . J

за

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

kg

, так как любой вариант,

со­

множеотво с элементом

kg . Тогда

1 k* kj t

1 K.I

1 к * Ы

K “ (ka} U

l k , k , l

( Ы

( Ы

( k i j

0

( M

Ф

32

где

-

пустое тожество.

Данный прием является частным случаем более общего:

если компоненты множества некоторой

| -ой колонки содержат

одинаковые элементы, то их можно вынести за матрицу (напри­

мер.;

k s

) .

Тогда

(

к .

) Ф

{

кл]

Ф

(

Ы

Ф

К

'

|

Щ

и

Ф

Ф

(

Ы

(

к,1

Ф

что позволяет

сократить количество операций соединений.

4.

К двум и более

алгоритмам,

описанным системами п

тых матриц, применима операция соединения, а над соответству­

ющими параметрами проводится операция Q ,

если алгоритмы не­

зависимы (независимыми считаем те алгоритмы, которые имеют

один вход и один выход).

I

Пуоть

где

b i *

В и*-

независимые алго­

ритмы и B i* {Ei.Ea, Е * ] ,

а

Ьа.*{ Еа, Е »,

3

я

E ,s ‘ *»

SaEjE*

»

X f а * -

^*fM ~ I

0

# |* j 4 I-

Рассмотрим обобщенный случай

( €• « i i

• • ' ? £ * , )

# a t p 35 I

1 .

жить сложную матрицу на матрицу-строку L

, содержащую

постоянные коэффициенты.

* ги - | * мИ

),

( f - i ,*»••••% )■

которые описывают множество решений алгоритма

М ‘

.

1 .2 . Обобщенный критерий

Представляя эффактнвнесть вычислительных алгоритмов

перечислением их параметров в виде кортежей и матриц,

прихо­

дим к чаотным показателям алгоритмов, с одной стороны,

и

ность параметров

алгоритма А в виде множеств

X

- { Х , , - - - » Х « ] . ( i “ M , •••> £)'

где \}L - чиоло компонент параметра

;

6 - число параметров алгоритма

А

.

Если X i характеризует состав

операций в алгоритме, то

V i)

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

1.-го