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

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

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

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

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

Добавлен: 24.10.2024

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

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

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

 

 

 

-

62

-

 

 

 

 

 

ванешшй©

условия (2*14)

и ее компонента

СI^L

определится

 

из (2 .1 3 ).

Если условие (2.14)

не выполняется,

то | - я

опе­

 

рация является подпрограммно-совместимой и

ее показатель d j l

j

определится, выражением (2 .16).

В чаотном случае,

при

1

,!

из

(2.14)

имеем <3j с = ° о

, и

j

-ю операцию следует набирать

да

программном поле.

 

 

 

 

 

 

 

I

 

4.

Перевод матрицы

I t :

в

оконечную

Ь

»

 

,1

 

Элементы оконечной матрицы

 

 

 

 

 

j

 

 

i i t

i z i • * ■ ЧV

 

 

 

 

 

 

 

■fell.

b z z

•

* ■ Чрг

 

 

 

 

 

 

 

Ь т

bzm • ■ -ьрт

 

 

 

 

 

получаются из следующих очевидных соотношений. I . Для совместимых операций

'i

2, Для программно-совместимых операций

■;

j .

•

*

 

Ч 1 •

. •'!

3. Для подпрограмшо-еОвместимых операций

51;

Таким образом,

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

I d

г

I t

в око­

нечные необходимо иметь численные значения dpt

, Zp:

,

 

Они могут быть легко

определены для каждой машины и сведены

в матрицу

з

д

/

~

,

)

 

 

 

Opt

0 <

( '

Cl

py t r i +.

 

 

 

дрг

d p

(Zpj. + t<f,i)

 

 

 

д р п dtj.ni ( Ърт + ’С ут)

 

 

 

■.......... -

ез -------------

' .........

 

 

В случае,

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

и выходов

больше единицы,

то в

матрицу Р

 

следует внеоти

ре показатели

р

и

Ц,

.

 

 

 

 

!

Перевод компонент исходных матриц

I d

и

1 £

к око-.

Нечным можно представить

следующей блок-схемой на рис,

2.4.

 

5.

а) Объем долговременной памяти -

7 )^

,

 

 

Долговременная память машины будет занята программой

алгоритма

и необходимыми константами для вычисления.

 

!Длина программы для I -й машины определится через

компоненты I -й строки оконечного вида матрицы d , т . е .

г 1

Система констант

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

С -й

машины

Ыь

 

“ [ц]-

 

' Из { k i $ ]

, где

^

= 1 , 2 , . . . ,

Yi. , опреде­

ляем число требуемых конотант.

Тогда общая загрузка памяти машины алгоритмом управления

определится внутрикортежной связью

 

в)

D i - D t + Y i .

Время реализации - Т I .

Данный показатель определит­

ся из

Р

 

 

т. “ Z. tji

i

1-1

A t , Компоненты матрица ис­

о)

Погрешность алгоритма -

пользуются в той функциональной зависимости, которая ооотавлена

для вычисления ошибки оконечных результатов и включающая в се­ бя, кроме A j i , ошибку выбранного численного метода, ошибки представления исходных данных и ряд других. Считая погрешности численного метода, яоходных данных и срочна постоянными для любой машины, имеем, что ошибка алгоритма

A t -

■~ т -

Рио* 2,3

•• 65 -

где

показатели

Д |1для

i -й машины выбираются из t -й

стро­

ки и подставляются в

функциональную зависимость.

 

 

Полученные выше показатели эффективности алгоритма уп­

равления для каждой машины сводятся в кортежи

 

 

 

А с * < A i , D i , T i > ->

 

где

i = 1 , 2 , . .. , и1

 

 

 

 

 

 

Из полученных

(11

вариантов выбирается та УВМ,

у кото­

рой

Т = Tmoi <

Т^оп

t

при условии,

что Э с

и

A t ^ Д<р<.

 

 

 

 

 

 

 

Весь процесс выбора варианта эффективной реализации

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

одной из

И1

УВМ можно представить в

виде

следующей охемы па рис. 2 .5 .

 

 

 

 

Исходным для решения данной задачи являются парк машин

и заданный алгоритм (блоки I и 3 ). Определение совместимости

систем команд, оценка эффективности

каждой операции СК Go

и программ р и

Cj, для каждой машины, а также составление

программы алгоритма осуществляется блоками подготовки

2 ,4,5

и 6.

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

L

и формальные преобразо­

вания над показателями эффективности проводятся в- блоках 7, 8 ,9 ,1 9 .

Блок II осуществляет выбор варианта.

В случае большого числа вариантов, что вызывает зна­ чительный объем вычислений, операции формальных превбразований (блоки 7,8,9,10,11) может выполнить ЭЦВМ.

X- 66 -

1

2

Рис. 2.4

-67 -

ШВ А Ш

МИНИМИЗАЦИЯ ВЫЧЙСЛИТЕЛШЬК АЛГОРИТМОВ

НА УРОВНЕ ОПЕРАЦИЙ

3 .1 . Выделение класса эффективно реализуемых алгоритмов

Рассмотрим возможности формирования условий, при.кото­ рых заданная структура (некоторый элемент множества [ М } ) будет наивыгоднейшей в смысле обобщенного критерия алгоритмов.

Для множества структур { М ] с помощью Н можно запивать следующую систему уравнений [47] :

Ft

+■У иХ*г +■•••+

ОСт,

 

F h ^

t y h i X

- t + y

‘h ' i-3 C+

Уz , / +т

(3.1) ,

F h *=■

+ у

h z X-o, +

+ ^nmOCtn-

 

Каждое уравнение характеризует число обращений к памяти при обработке заданного алгоритма Д ( Х ) * гдеХ =0& .г-*ЭСт). При этом предельные значения критерия можно найти из выраже­ ния (1 .3 2 ). Для определения условий выгодного испбльзоваиия

h -ой машины необходимо, чтобы имели место следующие не­ равенства:

F/t - F t

,

,

F h ' - F z ^ O ,

(3.2)

Fh’ Fh О ,

( t i , h *= i,Z ) --4 Н ; h 'l 4 f ) .

-68 -

Сучетом (3.1) получим систему неравенства в виде

+ ' + (tyh'm -

,

+' " -^шп)Х-т ^ О .

Очевидно, что каждое неравенство имеет место лишь в том

случае, если хотя

бы для одного значения

имеет место со­

отношение _

 

 

 

 

 

 

 

 

где

р I

= А

• ■• > Н

( Р

<^) •

 

 

 

Если для всех

I имеем

 

 

 

 

 

Уь

-

У ?

> 0 ,

 

 

(3.4)

что

означает

Fp -

Fo, > 0

,

то имеем в

лучшем случае экви­

валентность машин

Н р и М ц ,

в смысле критерия

F (< 4,fi) .

при этом машина Мр

никогда не может оыть лучше машины М<},

при любом алгоритме

А ( Х ) .

 

 

 

 

 

В качестве дополнительного

условия к системе (3.1) имеем

соотношение

 

m

 

 

 

 

 

 

 

 

 

 

0 - Х . 4 1.

i 3 5 )

 

 

 

 

 

 

 

 

 

 

i=l

 

 

 

есть никоторое М 1 -

 

Каждое неравенство

системы

(3.1)

мерное полупространство в

I'M-мерном пространстве. Поскольку

свободные члены в неравенствах равны нулю, то соответствующие

им гиперплоскости проходят через

начало координат Ш -мерно­

го Пространства, которое является

точкой пересечения всех га - -

перплоскостей. Если система нераватств ( З .и не противоречива, то она определяет в W -мерном пространстве некоторую, выпуклую неограниченную область (конус), которая получается в результа­ те пересечения всех полупространств, соответствующих неравен­ ствам заданной системы.

Если же система (3.1) противоречива, то тогда не суще­ ствует ни одной точки, которая(принадлежала бы одновременно

- 69 -

воем рассматриваемым пространствам* В этом случае возможны

такие группы неравенств, которые между собой оказываются не­

противоречивыми. Тогда в

-мерном пространстве оудут суще­

ствовать локальные неограниченные области, соответствующие

указанным группам неравенств.

 

 

 

 

 

 

Учет условия

(3 .5) приводит к тому,

что

выпуклая область

в

И1

-мерном пространстве становится ограниченной.

Более

того, все точки этой области лечат на гиперплоскости (3 .5 ),

которая пересекается гиперплоскостями,

соответствующими нера­

венствам из системы <3.1). Эта область является областью эф­

фективной реализации

алгоритмов исследуемой структуры

М К ,

Будем обозначать эту

область через

Аэ

,

а в

случае возмож­

ности определения количественной характеристики этой области -

через

S s

 

 

 

 

 

 

 

 

Поскольку отыскание ооласти

А э

есть определение су­

ществования решений системы

(3.1)

при условии

(3 .5 ), то при

использовании методов вычисления величины

Sэ

яри критерии

 

F(A,M )B области

АЭважным является предварительная оценка

системы

(3.1) с целью определения существования решений ука­

занной системы, используя условие несовместимости для произ­

вольной системы неравенств, можно выделить последовательность

приемов для анализа

системы

(3.1)

с учетом соотношения (3 .5 ):

 

 

 

гп

 

 

 

 

 

 

 

 

 

 

Iяi

 

 

 

 

 

 

 

 

 

 

'(tff.i-yfc'l-yht;

1 ^ ff = р ;

р=Н).

 

 

 

 

3;,

Найти все

линейно независимые строки матрицы

(.оаФфпдаентов (без свободных членов).

 

 

 

 

 

 

3,

-Выделить все подматрицы размера

 

 

:

 

 

 

h i i L

Qhiiz '

 

 

 

 

 

 

 

п

_

ClНг i 1

П 1 •

‘ ‘ Oftuoy-г

 

 

\

 

!' -

 

 

 

 

 

 

 

G flfiz ■ '

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