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

~ 150

-

Таблица 5 .1 .

р

Интервал [0

I]

Интервал

[0 ,5

1 l]

0

Stfl

Cos

CXp

и

Y ~

У с

I

0,84175

2,7183

. 2

0,707

4

I

0,84175

I

2,7183

4 '

0,707

16

2

I

0,84175

2,7183

Г6

2,12

96

3

0,84175

I

2,7183

96

10,6

7680

4

I

0,84175

2,7183

768

74,24

5

0,84175

I

2,7184

7680

6

I

0,84175

2,7183

Для заданного интервала

[ А , 6 ]

и допуотдаой ошиб­

ки

доп

при различных

Д и выбранных из

таблиц 5.1

соот­

ветствующих значениях М

П , CA.-S1 можно найти такое

К ,

при котором

D - K ( p + 0

будет удовлетворять условию

Представил графическое решение выражения (5 .3 6 ). Для

этого

примем, что

[А ; Й

, тогда получим нормирован-

ЙГ”

g L ,

.

(

М

Г

-

1

а :

( p . t ) ! 2 * " К р*' .

Определим $Ц*н

для наиболее часто встречающихся ин­

тервалов:

Со

* i ]

и

[о,5

*■.i ] .

Примем,

что

К -

2 *

,

тогда

3

1

(P+1) I

2 г 1>*1* к (Р+0

•

(5.37)

Выражение для расчета

0 дои

приведено к виду

С 2 х,

где С < 1

и г

для различных

р

и К

выбираются из таб­

лицы 5 .2 .

Коэффициент

С

от

К

не зависит.

-

151 -

Таблица 5,2

П о р я д о к п 0 Л Е Н 0 м а

( Р )

О

I

2

3

4

5

•6

7

Я

I

-г

0,66

0,66

0,53

0,71

0,82

0,82

X

I

I

4

7

I I

15

20

25

30

2

2'

6

10

15

20

26

32

38

4

3

е

13

19

25

32

39

46

8

.4

. ю

.16

23

30

38

46

54

16

5

12

19

27

35

44

53

62

32

6

14

22

31

40

50

60

70

64

7

16

25

35

45

56

67

78

128

8

13

28

39

50

62

74

86

256

9

' 20

31

43

55

68

81

94

512

10

22

34

-

47

60

74

88

102

Значение

•,

i ]

определяется из

Графики

l ]

и ()g«i

[о,5 ; i]

представлены на рио.5 .1.

Истинное значение ошибки

s - s ; . .

,

где значения M jm(U [A ; ft}

вабираютоя из таблица 5 .1,

5 ,4 .

Сравнительные or

Сравним некоторые показатели эффективности логической

охены 65, 66

и логических охай, реализующих выражения 15.28)

(5.30), (5.32).

Для сравнения выберем следующие покаэатеии:

/

Ь

-

время реализации логической схемы}

/

-

объем долговременной памяти, отводимый под про­

грамму логической схемы (количество команд).

/

Определим данные показатели как функцию от чиоАа подия-

тервалов

К

. Объел долговремеююй миляга ( D

) , отводи­

мый под константы полиномов, ясхоючнм,

т .х , для различных ме­

тодов при одинаковом

К величину 3)

а первом приближении

можно считать равнозначной.

Из

[65,

бб]

следует, что i

, при этом для

функции о границами подлитервалеи.

одного сравнения по­

требуются команды:

1 .

Посылка Л

м

] [

,

2 . Вычитание из #

гррпшм

3 . Проверка знака результат*

являются короткими.

Для вычислительных машин

Примем, что враля выполн

f to , тогда время р

i ,

-

5 ( « | , К

К - I) блоков сравнения/

Так как логическая схема содержат (

в каждом из которых содержится 3

то

cfi

~ 5 ( К - 0

Для реализации выражений (5*28) я (5.30) ( * > 0) требуется

5 команд (

fife = 5):

*

1. Посылка Об на

j£

•

2 . Умножение $

ш

£

3 . Сдвиг вправо на (

)

разрядов.

4 .

Сложение с (

NA

>* ♦

154 -

Ддя реализации (5V30) ( #<0)

я (5,32)

дополнительно вводится

жомафда выделения, тогда d*

» 6.

машин операция умноже­

Для большинства вычислительна!

ния есть длинная операция. Примем, что

4*мн =«5t« . Остальные

операции программа ееть короткие { (4#

).

*

* 4 С е) >

|

4 *

« 4 io (4 N * )-

Графики зависимостей 4

(К ) д d » f ( X )

показаны на рис.

5,2

я 5 ,3 . На графиков видно, что для К> 4

дра 5 а 2 ^ я

{

К > 10 пра Ь^З^Цвдевообразиев применять метод полиномо-

w ith

an application

to Sn t^ h olcfan gs -

proHe-m, Proc. Land.

Mailt. See. Cs)

t . 4 2 ,

4<?36.

числит. математ. и математ. фазах*,

1961.

23

. Мартын» В ,» . Об экономном распределена* памяти. Журя, вы­

числит. математ. и математ, физюш, Й8,

1962.

24

. Мартын» В,В. О некоторых метедйж анализа «аераторннх схем.

Дйсо. канд. фва.-«№ . наук, йад-во Ю г,

1963.

25

. Карп Р.Ц. Заметка а щшяокеюю тю р я графов к программи­

рованию для цифровых вмчиолатешшх мамя. "Кибернетичес­

кий сборник", М , 1982.

boolean

26 . прооаер р

. P roт sse.r * .Т )£. AppUeaUe* of

т а tn% € *

f© Й * anahsu

щ

£ | W

d io fta rn s,

ProI, leilcm. $ m t 'GMfqUi-bmfy

ffff.

27. Кулик B.T. Принцам алгоритмизации я гоотроевия ущмяяя-

кзцих м в ш . К^Гоотзяяадат УСОР,

1963.

'ЦВМ. М,, "Сов. радио", 1972,

Г'.. Кузьмин И,В.

Оценка эффективности я

оптимизации АСКУ.

М.,

"Сов. радио", 1971.

43.

Поспелов Д.А,

Введение в теорию вычислительны* систем,

М.,

"Со е. радио",

197 £,

41.

Голуб(зН1ови*паря

Ю.С. Многомашинные комплексы вычислитель­

ных средств.

М.,

"Сов радио", 1967,

,