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

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

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

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

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

Добавлен: 24.10.2024

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

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

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

- 86 -

Обозначим

Q. пр.о — С 0 ,

Qnp.i “ Со +ci,

&чр.л =* Сй + с х +С*.

 

 

0-прг4

= Со

+Са + С з ,

 

 

( Х и р 4 ~ Co +Ct +Сг + Сл + С*.

i

 

 

 

 

; Тогда

Ц[п1тох **■ fG-npiJ max.

!

 

Если вычисление ^[и ] проводить по схеме

|

у

[и ] - а

0^ Г и ] -

r« - i3 + a 4x [« - i] - & » i|['n - 2 ] +

 

 

•+

------- Ь п ^ [ п - К \ + О п Х [ п - Н ] >

то максимальное промежуточное число, получаемое в сумматоре УВС, не может быть больше величины

2 м j Bjmax [Q„p] maxt+|aifnax&maxj( .(3 ,24)

Это значение И м и необходимо взять в качестве масштабного коэффициента из условия переполнения разрядной оетки машины

 

 

 

 

м

-

^

Ь

,

-

 

 

 

 

На рио.3.3 - 3.6 приведены графики изменения Х М

и

а tn-»

, вычисляемые по приведенной схеме, а

5Г£НЗ - машин­

ное и

Zfn] -

расчетное получены из выражения (3.24).

 

 

 

На рио.

 

3.3 расчет произведен для случая Qi ^6l°0,5 ;

на рио.

3.4 -

для случая

Оо=, о ,5}

01=43,5:

Ог =* 0,5;

05

* -0 ,5 ;

 

0,5;

 

6t = -0 ,5 ;

5

* = 0 ,5 ;

 

05

» -0,5;

6^ = 0,5; на рис. 3L5 -

для случая

0с =1;

0 1 =

0 , 6 ;

 

0*= 0 , 2 ;

0 j = 0 ,0 6 ;

<74=0,02;

«

0,8 /

- 87 -

I

Ьз, = 0 , 4 ;

&з = 0 , 2 ;

 

= 0 ;

 

 

 

 

на рис. 3,6 - для

случая Оо *

X;

- 0 , 6 ;

Gk = о , 2 ;

 

 

 

Цз = >Ч),06;

С^= 0 ,0 2 ;

 

бх = -0»8;

6г=

0 , 4 ; бз *=

- 0 ,3 ;

 

6 а -

0 ,1 .

 

 

 

 

 

 

 

>

 

Как видно из графиков,

2

Г,[Т] меньше расчетных, но

одного

о ними порядка, т . е .

является

оптимальным о точки зрения

полу-*

чения повышенной точности вычислений и отсутствия переполи©-

:

ния разрядной сетки УВС.

 

 

 

 

 

 

 

Оценим’величины ошибок, которые получаются при принятом

опоообе масштабирования, учитывая, что при применении масшта­

 

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

а о их изображе­

 

ниями

 

 

 

oCl •

 

 

 

1

 

 

 

. X i - 2

 

 

•

j

 

Оценим ошибку при умножении, так как эта операция яв­

j

 

 

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

( 3 ,7 ),

и выведем

з а - ,

 

виоимооть этой ошибки от масштабу, в котором изображаются пе­

 

ременные

X и

у

. Можно записать,

что

 

 

 

 

6 ь —

 

 

Д

 

=

rtCа

 

 

 

c fi 2~c oCi

2

 

 

d i X n -

 

d i ,ОС

 

рде

АV /» -.- максимальная

ошибка

умножения числа <2*. на

числа

ОСп-1•

 

 

 

 

 

 

 

 

Максимальная относительная ошибка одного просчета по

формуле (3 .7 ), если

считать,

что

погрешность сложения равна

нулю и не учитывать

ошибку представления чисел в матине, так

Жак она постоянна и

от принятого

масштаба не зависит,

будет

равна

к+г

 

 

 

 

 

 

 

 

 

2

 

 

 

 

 

 

а максимальная относительная ошибка при определении

^ [« J

а , - £ « * . .

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)

- первое такое ребро, и пусть

 

<Ф(А, В) “

цепь графа

, соединяющая вершины Д

и

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