Добавил:

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

Вуз:

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

Предмет:

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

Файл:

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

.pdf

Скачиваний:

Добавлен:

19.10.2023

Размер:

6.6 Mб

Скачать

☆

<<< < Предыдущая 1 2 3 4 5 6 7 8 910 / 1710 11 12 13 14 15 16 17 > Следующая >>>

I		-	90 -
Если выбрать постоянный масштаб для всего процеооа вы
числения у [п]	( п =	1 , 2 , . . . ,		N	), то можно записать,
приняв функцию	*const		(что не вносит			существенных
погрешностей в определение максимальной ошибки), что
	= n 2 l A V ( o c , y ) .
Если для вычисления каждого значения ^						[п1	применять
свой оптимальный масштаб		2 " ^	,	где	tn ^ t	,	то в этом

случае получим меньшее значение ошибки. Например, при вычисле нии зависимости, изображенной на рис. 3.2, во избежание перб<- полнения разрядной сетки УВС необходимо выбрать постоянный мас

штаб t = 2, тогда
	< Ь	- 4 п л у .
Если же при вычислении каждого ^ [я ] выбирать масштаб,
ориентируясь на Z	] ,	то для десяти точек можно зашоать
& о = 1 - 2 *д - Ч ' + ^ . 2 1д М/ + 5 - 2 2д Ч' - 29-Д-Ч'
и , считая функцию Z	ГП1	периодической с периодом 10 точек,
получим
$ п = 2 9 - & У Jo = 2 , 9 A f .
Таким образом,	для уменьшения ошибок вычисления дискрет

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

фициенты перед получением	каждого значения	^ [н]
3 .4 . Приложение	теории графов ттля минимизации
вычислительных алгоритмов

Любой вычислительный алгоритм можно представить графом - деревом, корнями которого являются окончательные результаты, а вершинами - исходные данные алгоритма.' А процесо. реализации этого алгоритма на УВС представляется сворачиванием графа от его вершин к корням.

Докажем‘утв ерждение, что в любом графе имеется эффектив ный путь сворачивания его от вершин к корням, совпадающий с пу тем, определяющим минимальную трудоемкость вычисления алгорит—

- 91 -

ма на УВС.

Пуств имеется несколько операций А , 6 , С через которые мы должны проходить от вершин к корням. Для каж

дой пары операций	А , В известна	трудоемкость их реализации
УВС (количество операций, пересылок		и т . п . ) .
Рассмотрим	общий случай алгоритма без циклов. Граф наи

менее трудоемкой сети должен быть деревом, так как если бы он содержал цикл, можно было бы удалить одно из звеньев этого цикла и операции все еще осталиоь бы соединенными. Следователь

но, для соединения П	операций нужно провести	( 1 - 1 линий.
Покажем, что оптдаальный путь можно провести, пользуясь пра
вилом трудоемкости выполнения операций.
Прежде всего соединяет две операции о наименее трудоем
ким соединяющим звеном	6 i (считаем, что трудоемкость опера

ций вошла в линию, их соединяющую).

На кавдом из следующих шагов добавляем самое наименьшее трудоемкое из звеньев Si , при присоединении которого к уже построенным ребрам не образуется никакого цикла j если имеется несколько звеньев одной и той же трудоемкости, выбирает любое из них. Каждое дерево 0 , построенное таким образом, бу дем нызывать оптимальным деревом. Его трудоемкость равна сумме трудоемкостей отдельных звеньев:

{;(о)	as 4	+ Ь (.Sz)+••*+■'£(би-i) •
Докажем,	что никакое другое дерево % , соединяющее

те же вешоины, не может оказаться менее трудоемким оптималь

ного дерева О		.
	Пусть	.-	наименее трудоемкое дерево, соединяющее
корень	с вершинами,	а	О	- любое оптимальное дерево. Предпо
ложим,	что -рейва St	,	6а.,	6s .........оптимального дерева за

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

строении		О	. Если наименее трудоемкое дерево не совпадает
с	О	, то	О	имеет,	по крайней мере, одно ребро,	не
принадлежащее			&	.
	Пусть		S i -	( А ) S)	- первое такое ребро, и пусть
	<Ф(А, В) “		цепь графа		, соединяющая вершины Д	и

- 92

Ь ♦

Если ребро

добавить к

то граф

c£ + 6i.

'будет оодержать цикл С = б 1 + ф ( А ,5)

так как

О ,

не

(имеет циклов, то цикл С

должен содержать,

по крайней мере,

одно ребро, не принадлежащее

О .

Удалив это ребро

мы получим дерево

E ' - i C + e i - e i

о тем же самым чиолом вершин,

что и

причем его

тру-

доемкооть равна

+ H c O - i ( « S ) .

Так как

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

то

;

Ь ( бс )

*>)•.

Но

S i

было звеном наименьшей трудоемкости,

при добавлении

которого

6 i ,

£г

S i

Gl-i

не получается циклов. Так как

при добавлении ребра

этим ребрам мы тоже не получим

никакого

цикла,

то

Ь ( € [ )

( 6 i )

и,

следовательно,

X '

токе имеет минимальную трудоемкость:

;

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

мы наши другое дерево

минимальной

трудоемкости, имеющее о оптимальным деревом

О одним ребром

больше, чем

Мы можем повторять

эту

операцию до -тех пор,

пока окончательно получим соединяющее дерево минимальной тру-! доемкости, совпадающее о Q . Отовда О а также вое дру

гие оптимальные деревья действительно имеют минимальную тру-	\|
доемкооть их реализации УВС.	j

- ш

Г Л А В А 17

СИНТЕЗ АЛГОРИТМОВ ПОВЫШЕННОЙ ТОЧНОСТИ ВЫЧИСЛЕНИЙ ДЛЯ ПРОСТЫХ ОПЕРАЦИЙ ПРИ ОГРАНИЧЕННОЙ

ДЛИНЕ РАЗРЯДНОЙ СЕТКИ УВМ

4 .1 . Предварительные замечания

Работа управляющей вычислительной машины связана с реа лизацией некоторого набора управляющих алгоритмов. При этом каждый управляющий алгоритм о целью обеспечения необходимой : эффективности ущшвления требует различной разрядности управ ляющей машины. Эяо связано, прежде всего., с получением различ ной требуемой точности вычислений выходной информации. На дли ну разрядности УВМ влияют выбор численного метода решения, объем вычиолений, величины погрешностей, еносимые элементар ными алгоритмами (операциями), составляющими алгоритм управле ния. Кроме того, один и тот же алгоритм на некоторых участках управления может вычисляться о повышенной точностью. Естествен но, что для эффективного управления расчет разрядности УВМ сле дует производить из условия обеспечения максимальной точности для воех алгоритмов на всем этапе управления. Однако этот путь не всегда является прие&ь.змым, т . к , рост разрядной сетки неиз бежно ведет к увеличению экономических и габаритовесовых пока зателей УВМ.

Если роот разрядности приводит к нежелательным экономи ческим, задачам и размерам УВМ, то длина разрядной оетки опреде ляется из условия обеспечения этих требований, а повышенная точность (точность, превышающая разрядность УВМ) реализуется ; программным путем.

При введении алгоритмов, реализующих повышенную точность вычислений, следует учитывать тот факт, что 8ти алгоритмы требу ют для своей реализации значительно большего времени и объема памяти УВМ по сравнению с одинарной точностью. Кроме того, для введения этих алгоритмов необходимо произвести некоторые изме

нения и дополнения в		оиотеме иструктуре команд УВМ.
;	Поэтому задача	оптимизации таких алгоритмов являетоя

одной из важных для обеспечения эффективного управления. Од

- 94 -

нако вопрос оптимизации и согласования структур и характеристик алгоритмов 6 показателями системы управления в большей степе ни относится к первым двум главам, где предполагается возмож ность изменения структур и показателей вычислительник алгорит мов.

Естественно, что чем шире возможность изменения струк тур алгоритмов и их показателей, тем вш е степень оптимиза ции и эффективное управление.

Изложению методов синтеза алгоритмов для проотнх опе раций о различной структурой и показателями, а также методов вычисления некоторых функций о повышенной точностью вычисле ний посвйчены две следующие главы.

4 .2 . Алгоритмы простых арифметических операций

Разработка алгоритмов повышенной точности вычислений, для простых операций являетол одной из важных, т .к , эти ал горитмы представляют собой основу построения более сложных

алгоритмов. От их показателей	существенным образом зависят по
казатели алгоритма управления	и всей	системы управления в целом.
Чиоло многократной точности		1£) '	в машинах о фикси

рованной запятой определено как число, состоэдее из знака чис ла и правильной дроби из "к" пооледовательш " : слов памяти [б 0 |. Если основание системы счисления Cj, = 2, а >аждое слово вычис

лительного устройства включает					И двоичных разрядов, то
			т - s * ,		£ v , 2 - ‘\
где	S v	-	знак числа	¥	(для ¥;>о. Sч’-О,	S<c= l ) }
	’f t	-	целая цифровая		И -разрядная	С-я часть
			чиола (слово).
Если чиоло Sf в целом представлено в						одном из кодов
(прямом,	обратном, дополнительном), то в общем виде его можно
запиоать	так:
		[ f l - s . ,		Е<пгг"

С*1 *

- 95 -

где	- целая цифровая П-разрядная t -я		часть числа
(слово).		(
	Каждое слово ^	хранится в отдельной	ячейке памяти ма
ш ин.	Исследуем некоторые возможные алгоритмы, реализующие

простые операции о повышенной точностью. Для каждого алгорит ма будем оценивать погрешность метода реализации данной опе рации при условии, что ошибка представления исходных данных равна нулю. Таким образом, данный показатель характеризует погрешность,вносимую оамим алгоритмом.

Сложение "длинных" чисел характеризуется тем, что скла дываются последовательно слова, начиная с младших. Если при сложении слов возникла единица переноса, то она прибавляется к младшему разряду суммы соседних старших слов.

Таким образом, при сложении длинных чисел возникает не обходимость в анализе сумм отдельных слов с целью выявления единицы переноса в соседнюю старшую часть суммы или в запо минании значения переноса в специальном разряде о последующим его добавлением к сумме старших частей.

ПУ” Ь		[« f 1 -	S * . ^		Ч«е'
•		[ у ] = S r . £			г Л п .
			i*»		виде итерационной после
Сложение 1~х		олов можно записать в
довательности
		( i=k,		2,i) ;		(4.1)
здесь P i-	значение перенооа от			сложения (		L+ 1)-х слов;
P i- i -	значение переноса от			сложения		L-х слов;
(¥ + ~Чт)*-	значение суммы		i - x	олов

При сложении слов 1= I			возникший		перенос	ре	от
сложения цифровых частей поступает в				знаковые разряды.			При
этом	+	+ро =	2	+	S > 0	£	+ v )
S y

( 4 . 2 )

				- 96	-
где	2	-	значение переноса	от	сложения	i= I слов совместно
со	знаками. Если сложение длинных чисел происходит в обратных
;кодах,		то	Z - значение	циклического		переноса - прибавляет
с я	к младшему разряду полученной суммы длинного числа. Это

можно записать в виде следующей итерационной последовательности

		(4’3)
где для С ~ к имеем	рк = И	.
Если сложение длинных чиоел происходит в дополнительном
коде, то значаще И	не учитывается.
U учетом оказанного,		если длинные числа в памяти маищ-

ны хранятся в прямых или обратных кодах и сложение происходит в обратном коде, то для получения ошибки алгоритма, равной ну лю, необходимо реализоватьитерационные последовательности (4 .1 ), (4 .2 ), (4 .3 ). Кроме того, для чисел, представленных в

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

соответствующим знаку старшего олова (		= I ) . Присвоение зна
ков младшим словам (S(r+v}i-+ SCf-rvJi )		мо:;яо	осуществить	j
совместно о реализацией (4 .3 ).
Таким образом,	если длинные числа	хр чятся в памяти ма
шины в прямых кодах,	а сложение их происходит в		обратных кодаке,
то реализуются последовательности:				j

	[ Я , * ] . + [ S * ,ч*1 +P i - Pi + 0 , ( 4 + y ) i ,
( С			( c - k , k-н,-.-, 2;	p x ~ 0 ) ,	(4.4)
( С	1	-	обратные коды слагаемых).
Для	t =	I	имеем		.' -'	.
			^ ] «+Pi = Z+ S(^Y)i(Y + y)i .		(4,5)

С учетом циклического переноса и присвоения знаков млад шим частям имеал

______ «Sjcip+yji -*■ 8{чч-+)с

г				-	97 -	.	4.6)		(
L S ( 4)t, ( ¥ * * ) & + Pi= p._t+Sm4,k
j m	Lm'1	U	-	k	2; p « - z ; .
C S(fv)i,(tf+1k)r] +ft				SOf+VJi, (tf+’ipji •			(4.7)		> ес
Можно построить алгоритм о вносимой погрешностью * 2								4
ли не учитывать значение циклического						переноса 2	.	Тогда
выражения (4,6)		й (4.7) можно изменить на последовательность
	Scv+V'ji	S c i f ^ ) i			(с= к ,к-V " ) 2 ) ,		(4.8)
	Если сложение длинных чисел проводить в дополнительных
кодах,	то
[ S v i , f J0 +Z<e + [			S 44, % ] o+ Z<t=* рк-i + 0,(tf+):,
	( e « 0,	сслц	S “ 0	и	2 = 2 ^ ,	еслч

[Svi^iJo+ C St^H 'cjo + Pi ^ p c - i + o X y + Y U ,

( £ - k - ! , f c - 2 , . " , 3 , 2 ) ;

[S f^ V ’Jo + f5+ i,V i]0 +pi «		S(v++)t> (V’ +VS'Ji;
	S ( ^ i - * S ( ¥ + v j i	(4 = ic,	-
Без учета	Z-y и 'Z f'возможны наборы алгоритмов		с погрешностью,1
равной	Z + * 2 - 2 " ки ,		I

Для длинных чисел, представленных в ячейках памяти ма шины в обратных кодах, реализуются следующие итерационные по следовательности;

З ъ , *1 + S		+Pi -		p i-1 + о, O f + г ) ?
(	ь^к,	к-1, •••> 2	;	Р к а 0 ) }
S f i ,	+ S *i, Vi' +pi		-	z + S c w f a C v + 't ) ? 1, (4.9)

S(4+*)A—> S(V++)l ,

i, (¥+*)**'+pi = р м + S(w)i, (¥<-?)'i ,

( i - k, k - l , . . . , 2) - pK- 2)i

S(v*+h,('£+'k)?+pi. - S cv+ ty/tf+ yjj ,

Если младшие части слагаемых хранить в памяти мавшны

Л положительный 'знаком, то система (4.9') примет вид

о,ч>1+ о,у-+pt -рм +о,0*+у)?1

Ц=к, к-ц..., 2-		рк=о)-
S v . f i + S ^ p f i ' + p i = 2 •- S f v + ^ i . C t f + ^ r j
0 , ( ^ + r ) r + p i “ p n + o . Cvf+ y) - ,
( i = k ,	2;		(4.10)
pi =		( ' i <• y ) i .
			то получим ал
Если не учитывать циклический перенос,
горитм с погрешностью ^	2	:
0 , v i + О, У / f P i - р ы + 0 , ( * + у ) 1 ,
( t'k , k-i,	2;	рк = 0);	(4.II)
S v t . f i +	+ Pi -	C ^ + y ) i •

Рассмотрим случай, когда в памяти машины хранятся длинные числа, в целом представленные в дополнительных кодах. Сложе ние таких чисел можно реализовать следующей последовательноотью:

О, Ч>1 + 0 ,ri + Pi	=	+ о, ( iffY)l ,
( i - k , k-i, • ••,	2 ;	р к « 0 ) ;	(4 *12)
Svt, 4>L■+ S%, fi f pi = S( t f , c			V l .

Здесь младшие части длинных чисел можно хранить с по ложительным знаком, т.к. это не влияет на процесс сложения. Системы (4 . II ), (4.12) одинаковы, однако для чисел, представ ленных в дополнительных кодах, алгоритм сложения ошибки не

- 99 -

вносит.

Вычитание чисел, превышающих длину разрядной сетки УВМ, через сложение в кодах можно представить как

q > _ Y = М + М - S (*.+}, £ (Ч-ЧгУс 2 ~ *

Составим итерационные последовательности вычитания для длинных чисел, представленных в памяти в прямых кодах. Если' код представления чисел в АУ обратный, то набор алгоритмов можно составлять по итерационным последовательностям:

[Sv, fi]o + Г ~ ^ ,У г ]0 + p L ~ p n + 0, (<£-¥)			(4.13,а)
( i * k ,	2 ; р к ~ 0 ) ;
fSft.V iJo + f-S fa .tiJ, + рА= 2 i S ( w ) L( - У) Г;			4’13 ’6)
S(v-)i —> Sc-*)i
	+ p i « p t -4	+ S (* -* )< ,(^ V ')i,.
(L=k,k-ir .., 2 ;		p * * Z ) }	(4.13 д)

Г $ (« М *,(¥ -^Г ]о +Pi = S(4-*h, ( tf-V 'Ji •

Последовательности (4 .13,а) и (4,13,6)				можно реализовать
так же, как и (4.4)	и (4,5),	если предварительно сформировать
обратные коды слов	вычитаемого
	Y j о )	( I*	k, k - i , »••) 2,1} .
Последовательности	(4 .1 3 ,с)	и (4.13,д) соответствуют (4.6)			я
(4 .7), а поэтому программы их будут совпадать.				<
Заменив в системе (4.13) выражения (4.13,с) и (4,13,д)
на последовательность					j
SCf-'P),	—* S c’f-'pji. I		(	2 ) ,
			о - Ки
получим алгоритм с вносимой погрешностью * ^				,
Если вычитание длинных чисел проводится в дополнитель
ных кодах, то реализуются последовательности
- [ S f l l K ]„ + z * + [ - S n jK ] o + -B-p-l + o l ( & y ) K					!

( Zy - отрицание Z^) •

<<< < Предыдущая 1 2 3 4 5 6 7 8 910 / 1710 11 12 13 14 15 16 17 > Следующая >>>

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