Добавил:

ivanov666 Опубликованный материал нарушает ваши авторские права? Сообщите нам.

Вуз:

Башкирский Государственный Аграрный Университет

Предмет:

[НЕСОРТИРОВАННОЕ]

Файл:

книги из ГПНТБ / Основы теории алгоритмов учеб. пособие

.pdf

Скачиваний:

Добавлен:

19.10.2023

Размер:

6.6 Mб

Скачать

☆

<<< < Предыдущая 1 2 3 4 5 67 / 177 8 9 10 11 12 13 14 15 16 17 > Следующая >>>

- 60 -

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

Для учета динамики этих операций в алгоритме управления

составим матрицу-строку

(

1 {

, ( j ~ 1 , 2 , . . . , р ) ,

где

чиоло

участков

]-й операции в

программе;

число

обращений к

j -й

операции в

программе.

Перевод исходных матриц (2.12) в оконечные производит

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

£ ji

на

i d

, a

Cji

- н а

T i

«Эле

менты матриц

1 Д

I K

остаются без

изменения и соот

ветствуют

элементам конечных матриц

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

I d

в оконечную

Элементы матрицы

cli.1

dl 2i

•

d (р1

d u

с(гг

• ■ ' d f

d m

d z m •••

рт

получаются в результате следующих преобразований.

Для совместимых операций, признаком которых являет

ся d^L

I , компонента

c j j t =

d j i .

Для программно-

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

величина

d j t

зависит

от величины dji-

и ряда других

приз

наков. Определим их.

Условно разобьем долговременную память машины на прог раммное и подпрограммяое поле. На программном поле будем на

бирать основную программу вычислений и программы р					вхо
да в подпрограмму. На подпрограммное! поле набираются только
подпрограммы			р	вычисления некоторых операций и програм
ма	CJ,	- выхода из		подпрограммы.
	При этом если			j -я операция L-й машины имеет длину
программы		d j t	и набирается на программном поле		раз,
jTo	загрузка памяти машины этой операцией определяется из

	-	61	-
	d j u ^ t	j i	■
								(2.13)
В	случае выполнения	д -й	операции в				виде программы
необходимо учесть, кроме показателей					д		и	V	основной
программы операции, еще показатели				<Эр		и	Хр		- программы
входа в подпрограмму - и показатели <Э<р						Vq,			- программы
Q	выхода из подпрограммы.
Показатели программ		р	и	CJ,	зависят			от	типа машины

и числа походных и оконечных результатов. В основном система команд машины содержит операции о одним входом по числу исход


ных данных и одним выходом по числу результатов. В			связи	о
этим можно считать, что показатели dp ,		, d<j,	, ТТ^,	для
различных операций одной а	той же машины имеют соответственно
равные значения и не зависят от типа операвдй.
Таким образом, если	J -я операция выполнена в виде

подпрограммы, то загрузка этой операцией памяти машины опре делится из

	d it* *■ diL + d p i			liL + dai, .		(2.14)
	•	*	Г '	*		(2.14)
	Из условия'	экономии памяти j -ю операцию будем наби
рать на программам поле,			если выполняется неравенство
		d j a ^ d i u .				(2 Л5)
При невыполнении (2.15)			\|~ я	операция должна		быть выполнена
в виде	подпрограммы.
	Подставив в (2.15) правые части из (2.13) и (2.14), по
лучим,	что		-		V
	d	O pi Cji +
	; i	^	t j i	■	•	. (2 .i6 )
	i		t j i	-	1
	Таким образом, воли j -я операция имеет					d j't > i	и
она не совместима,		то признаком програмшо-оовмеотимооти будет

			-	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 . Для совместимых операций

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 -

Рис. 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 ■ '

<<< < Предыдущая 1 2 3 4 5 67 / 177 8 9 10 11 12 13 14 15 16 17 > Следующая >>>

Соседние файлы в папке книги из ГПНТБ