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

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

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

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

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

Добавлен: 24.10.2024

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

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

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

- 92

 

Ь ♦

Если ребро

 

Gi

добавить к

^

,

то граф

c£ + 6i.

 

 

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

,

а

так как

О ,

не

 

 

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

 

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

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

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

О .

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

61

 

[,

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

 

 

 

 

 

 

 

 

 

 

 

 

i

|

 

 

 

 

 

E ' - i C + e i - e i

 

 

 

 

 

 

|

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

что и

X

,

 

причем его

тру-

 

!

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

 

 

 

 

 

 

 

 

 

 

 

 

 

j

!

 

>

 

 

 

 

W

 

+ H c O - i ( « S ) .

 

 

 

j

Так как

&

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

то

'

;

 

 

 

Ь ( бс )

2*

i

 

*>)•.

 

 

 

 

 

 

 

 

Но

S i

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

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

 

 

которого

к

6 i ,

£г

 

S i

Gl-i

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

i

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

к

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

 

,

никакого

цикла,

то

 

 

 

 

Ь ( € [ )

 

 

 

 

 

 

 

 

 

 

 

 

 

 

( 6 i )

=

 

 

 

 

 

 

 

 

и,

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

X '

 

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

 

;

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

:

 

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

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

X

минимальной

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

 

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

|

больше, чем

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(f*v)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)

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