Справочника программиста том1-Я.С.Дымарский Москва 1963 стр.628 В первом томе «Справочника программиста» изложены численные методы решения некоторых задач, основные характеристики и системы операций ряда отечественных электронных вычислительных машин («БЭСМ», «Стрела», «Урал-1», «Урал-2», «Урал-4», «Минск» и др.). рекомендации по программированию на ЭВМ БЭСМ, «Стрела» и «Урал-Ь. Справочник предназначен для программистов, имеющих опыт работы на электронных вычислительных машинах, и начинающих специалистов. Вместе с тем он может быть полезен для специалистов, работающих в области электронной вычислительной техники, а также студентов, изучающих основы программирования.

ОГЛАВЛЕНИЕ

Предисловие ...................... Ц

Список принятых сокращений ............... 14

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

Глава 1. Краткие сведения из теории погрешностей 17

§ 1. Образование погрешностей ............ —

Приближенный характер вычислений ....... —

Источники погрешностей............. —

Классификация погрешностей............ —

Округление чисел ......'.......... 18

Верные и значащие цифры............. —

§ 2. Оценка погрешностей .............. 19

Способы оценки ................. —

Абсолютная и относительная погрешности ..... —

Оценка по остаточному члену ........... 20

Статистические оценки .............. —

§ 3. Погрешности элементарных действий........ —

Приближенные числа и псевдооперации ....... —

Зависимость погрешности от последовательности действий .................... —

Погрешности арифметических действий ....... 21

§ 4. Погрешности функций .............. 22

Глава 2. Интерполирование и приближение функций 25

§ 5. Интерполирование ..............-. . —.

Линейное интерполирование ............ —

Итерационный способ Эйткена.......... 26

Интерполяционный многочлен Лагранжа ..... 27

Интерполяционные формулы Ньютона ...... 30

Интерполяционные формулы с центральными разностями ................... 32

Тригонометрическое интерполирование .-•..... 35

Интерполирование функций двух переменных . . . . 37

Обратное интерполирование........... 38

Вычисление в машине функций, заданных таблично 39

Метод последовательных испытаний (метод «зубчатки») —

Метод сужающихся, интервалов.......... —

Метод деления промежутков пополам....... 40

Метод среднего шага .................. —

1* 3

§ 6. Приближение функций............. 41

Равномерные приближения. Теоремы Вейерштрасса

и Чебышева ......_........... 42

Некоторые оценки порядка наилучшего равномерного

приближения ............-. . . . 44

Примеры многочленов наилучшего приближения . . 45 § 7. Методы приближенного построения алгебраических

многочленов наилучшего приближения ....... 47

Алгоритм последовательного расширения точечного

множества приближения............. _

Алгоритм последовательных чебышевских интерполяций ...................... 49

Глава 3. Системы линейных алгебраических уравнений 52

§ 8. Классификация методов ............ _

§ 9. Замечания о выборе метода............ 53

§ 10. Методы исключения .............. 54

Схема единственного деления ............ —

Метод треугольных множителей........... 56

Метод главных элементов ............. 58

Метод диагональных элементов .......... 59

§ 11. Метод квадратных корней ............ 60

§ 12. Метод ортогонализации ............ 61

§ 13. Методы обращения матриц ............ 63

Метод пополнения................. .™-

Метод итерации . .'................ 64

Метод клеток .................. 65

§ 14. Итерационные методы решения систем уравнений . . 66

Метод последовательных приближений ....... —

Одношаговый циклический процесс......... 67

Метод наискорейшего спуска ........... —

§ 15. Методы ускорений итерационных процессов .... 69

Способ Л. А. Люстерника............. „~

Способ Эйткена.................. 70

§ 16. Способ наименьших, квадратов .......... -~

Глава 4. Собственные значения и собственные векторы матриц 72

§ 17. Основные определения. Классификация методов . . —

§ 18. Методы построения характеристических полиномов .73

Метод А. Н. Крылова............... _

Метод А. М. Данилевского ............ 74

§ 19. Итерационные методы ............. 76

Метод вращения с преградами........... —

Треугольный метод со сдвигом ........... 79

Степенной метод ................. 82

Глава 5. Нелинейные алгебраические и трансцендентные

уравнения 84 -

§ 20. Постановка задачи. Классификация методов ... —

§ 21. Уравнение с одним неизвестным......... 85

Границы расположения корней алгебраического уравнения . ................... —

Отделение корней ' ................ 87

Метод квадратного трехчлена........... —

Метод дифференцирования по параметру ....... —

Метод присоединенной матрицы . . . . г. ...... 89

Метод хорд ................... 90

Метод простой итерации .............. 91

Метод линеаризированной итерации ........ —

Метод квадратных трехчленов............ 94

62 — процесс Эйткена............... 96

§ 22. Система нелинейных алгебраических и трансцендентных уравнений ................ —

Метод дифференцирования по параметру...... 97

Метод простой итерации ............. 98

Метод линеаризированных итераций ........ —

Метод наискорейшего спуска ........... 99

Глава 6. Приближенное вычисление определенных интегралов 102

§ 23. Постановка задачи для однократного интеграла . . —

§ 24. Интерполяционные квадратуры.......... 103

Формула прямоугольников ............ —

Формулы Ньютона — Котеса............ 104

§ 25. Квадратура наивысшей алгебраической степени точности........................ 107

Формула Гаусса ................. —

Формула Чебышева ............... 114

§26. «Большие» квадратурные формулы......... 116

§ 27. Оценка погрешности интегрирования ....... 117

§ 28. Выбор шага и метода интегрирования....... 118

§ 29. Вычисление кратных интегралов.......... 122

§ 30. Интегрирование быстроосциллирующих функций.

Метод Филона.................'. . . 124

Глава 7. Численное решение обыкновенных дифференциальных

уравнений. Численное решение задачи Коши 127

§ 31. Дифференциальные уравнения 1-го порядка .... 128

Разложение в ряд Тейлора............ ~-

Метод Эйлера.................. 129

Метод Рунге — Кутта.............. 130

Метод Адамса..........•....... 132

Метод последовательных приближений ...... 140

§ 32. Системы дифференциальных уравнений 1-го порядка 146

§ 33. Дифференциальные уравнения п-го порядка..... 148

Метод приведения к системе уравнений 1-го порядка 149

Метод Рунге — Кутта............... —

Метод конечных разностей............. 155

§ 34. Линейная краевая задача . . . . •......... 163

Метод сведения к задаче Коши........... —

Метод конечных разностей............. 165

Метод прогонки................. . 167

Метод Ритца................... 169

Метод Б. Г. Галеркина.............. 171

§ 35. Нелинейная краевая задача........... 172

Метод проб с интерполяцией............ —

Метод конечных разностей............. 173

Глава 8. Некоторые специальные функции 175

§ 36. Полиномы Чебышева............. 176

§ 37. Полиномы Лежандра .............. 178

§ 38. Интегральный синус и косинус . ,........ ,179

§ 39. Интегралы Френеля .............. 183

§ 40. Эллиптические интегралы ........... 184

§ 41. Функции Эйлера ГиВ............. 187

§ 42. Цилиндрические функции ........... 189

Свойства цилиндрических функций ......... —

Вычисление ]р (г) и Yр (г) при р = п целом и г > 0 ... 190 Вычисление Jp(z) и Yp(z) в случае, когда р вещественное\parг ;> 0 вещественное .............. 201

§ 43. Цилиндрические функции от чисто мнимого аргумента 203 § 44. Вычисление цилиндрических функций по рекуррентным

формулам ................... 207

§ 45. Интеграл вероятностей ............. 212

Глава 9. Методы статистического моделирования 215 § 46. Получение случайной последовательности чисел на

электронных цифровых вычислительных машинах 216

Случайные числа с равномерным законом распределения —

Способ табличного задания .......... _

Способ генерирования случайных чисел специальным «датчиком» .............. —

Способ программной выработки ....... _

Способ середины квадрата .......... 217

Способ сравнений .............. _

Случайные числа с произвольным распределением . . 219

- Метод Неймана ............... _

Способ обратной функции ........... _

§ 47. Вычисление кратных интегралов ......... 221

§ 48. Решение уравнения Лапласа методом Монте-Карло 224

Глава 10. Численные методы линейного планирования 227

§ 49. Общая задача линейного планирования...... _

Метод последовательного улучшения имеющегося плана 229 Построение оптимального плана методом корректировки

множителей................. 232

Случай вырождения в методе последовательного улучшения .................... 233

Построение исходного допустимого плана...... —

§ 50. Первая частная задача (станковая задача)..... 234

Постановка задачи ............... _

Метод решения................. 235

§ 51. Вторая частная задача (транспортная задача) . . . 239

Постановка задачи ................ _

Метод решения.................. _

§ 52. Третья частная задача (основная задача теории

матричных игр) ................ 242

Постановка задачи................ —

РАЗДЕЛ.ВТОРОЙ

ОСНОВНЫЕ СВЕДЕНИЯ ОБ УНИВЕРСАЛЬНЫХ ЦИФРОВЫХ ВЫЧИСЛИТЕЛЬНЫХ МАШИНАХ

Глава И. Общие сведения об электронных цифровых вычислительных машинах 247

§ 53. Вычислительные цифровые машины........ —

§ 54. Система операций. Программа • ,........ 249

§ 55, фиксированная и плавающая запятая ,,...., 25}

§ 56. Машинное переполнение и машинный нуль .- . . . 2б2

§ 57. Кодирование чисел в машинах.......... 253

Прямой код ................... —

Обратный код .................. 254

Дополнительный код ............... —

Модифицированные коды.............. —

Десятично-двоичный код . . . ,.......... 255

§ 58. Блок-схема и операторная схема......... 256

§ 59. Некоторые термины, употребляемые в программировании ..................... 259

Глава 12. Вычислительная машина БЭСМ-2 262

Глава 13. Вычислительная машина «Стрела» 288

Глава 14. Вычислительные машины «Урал» 326

§ 60. «Урал-1» ................... —

§ 61. «Урал-2» ................... 338

§ 62. «Урал-4» ................... 355

Глава 15. Вычислительная машина «Минск-1» 373

Глава 16. Вычислительная машина «Киев» 397

Глава 17. Вычислительная машина М-2 410

Глава 18. Вычислительная машина «Сетунь» 422

РАЗДЕЛ ТРЕТИЙ РЕКОМЕНДАЦИИ ПО ПРОГРАММИРОВАНИЮ

Глава 19. Рекомендации по программированию для БЭСМ-2 451

§ 63. Некоторые особенности и возможности использования команд .................. —

Арифметические операции ............ —

Логические операции .............. 454

Вспомогательные операции ............ —

Операции с параметром .............. 455

Операции обращения к внешней памяти....... 456

Команды управления .............. —

§ 64. Запись чисел и команд на бланке......... 457

§ 65. Ввод материалов в оперативную память...... 459 ,

Программа начального ввода ........... —

Ввод материала с магнитного барабана ....... 461

§ 66. Организация циклов .............. 463

Способы счетчика . . ............... 464

Первый способ ................ —

Второй способ ................ —

Третий способ ............... —

Четвертый способ .............. 465

Циклы, работающие дважды ........... —

Первый способ ............... —

Второй способ................. —

Третий способ ................ 466

Четвертый способ.............. —

Способы сравнения ............... —

Первый способ ............... 466

Второй способ ................ 466

Итерационный цикл ............. 467

Логическая шкала ............... —

Первый способ................ —

Второй способ................ 468

Циклы в цикле ................. —

§ 67. Модификация команд (чисел) .......... —

Изменение адресов .....,.......... —

Изменение кода операции ............. 469

Первый способ ................. —

Второй способ ...............•. 470

Третий способ ................ _

Формирование команд (чисел)........... —

Восстановление команд ............. 473

Первый способ ............... _

Второй способ ................ _

Третий способ ................ —

§ 68. Использование подпрограмм.......... 474

Вписывание подпрограмм вручную ......... —

Блок подпрограмм .............. —

Компилирующая программа........... 475

Интерпретирующая программа ........ —

§ 69. Программный контроль правильности вычислений . . —

Контроль правильности работы БЭСМ-2...... 476

Первый способ ..................—

Второй способ ................ —

Третий способ ................ 477

Четвертый способ............... 478

Контроль правильности вычислений ........ 479

Контроль по разностям............ —

Способ подстановки ............. —

Способ дополнительных связей ........ —

Способ контрольных точек .......... —

§ 70. Перерывы в решении .............. 480

Первый способ ................ —

Второй способ ................ 481

Третий способ................ 482

§ 71. Вывод результатов............... 484

Рациональное расположение результатов .... — Выдача результатов с фиксированной после заданного .разряда запятой ............ —

Вывод результатов с заданной точностью .... —

§ 72. Программирование в условных адресах...... 486

Первый способ ............... __

Второй способ ............... _

§ 73. Отладка программы .............. 488

Подготовка программы к отладке........ —

Проверка перфокарт (перфоленты)....... 489

Организация отладки.............. 490

Проверка арифметических операторов..... —

Проверка логических условий......... 491

Проверка циклов и вспомогательных операторов 492

Решение контрольных вариантов........ —

Исправление программы '........... _

Глава 20. Рекомендации по программированию

на машине «Стрела» 495

§ 74. Подготовка исходного материала......... —

§ 75. Ввод материала в оперативную память...... 497

Программа «Начального пуска».......... —

Ввод программы и контроль ввода......... —

§ 76. Методы организации циклов ........... 498

Способ «Счетчика» . •.............. 499

Способ «Сравнения» . •............. —

Итерационный цикл ............... 500

Использование операции 27............ 501

Использование групповых операций ........ —

§ 77. Способы модификации команд.......... 502

Переадресация ................. —

Модификация кодов операций........... 503

Формирование команд ............., —

§ 78. Некоторые особенности машины • ,....... —

§ 79. Программный контроль работы машины...... 505

§ 80. Перерывы в решении .............. 508

§ 81. Отладка программы ............... 510

Первый этап. Проверка перфокарт......... —

Второй этап. Проверка арифметических операторов . . —

Третий этап. Проверка логики.......... 511

§ 82. Вывод результатов вычислений ......... 513

Преобразование результатов из полулогарифмической

формы в форму с фиксированной запятой .... —

Округление ................... 515

/Глава 21. 'Рекомендации по программированию

v'">.-~..... для машин «Урал» 517

§ 83. Подготовка исходного материала......... —

Запись на бланках..............- • • • —

Запись команд .................. —

Размещение материала на перфоленте....... 520

§ 84. Ввод материала в оперативную память...... 521

Программа «Начального пуска» .......... —

Ввод двоичных чисел (команд)........... 522

Ввод десятичных чисел...............—

/•^~~vКонтроль ввода ................. —

/ § 83) Особенности организации вычислений в машине . . . 524

Ч__-ХМасштабирование ................ 525

Переменные масштабы .............. 527

Вычисления с «плавающей запятой»........ 530

§ 86. Методы организации циклов........... 534

Способ «Счетчик» ................ —

Способ «Сравнения» ............... 535

Итерационный цикл ..........., . . —

Способ по «Нц» .................. —

Организация цикла в цикле............ 537

§ 87. Способы модификации команд .......... —

Модификация с помощью команды Из (30)..... —

Модификация с помощью арифметических операций . . 538

Модификация с помощью команды Нц (25) . . . 539

§ 88. Использование подпрограмм .......... —

§ 89/ Некоторые особенности машины ......... 540

§ 90. Программный контроль работы машины...... 541

Подпрограмма ввода материала с магнитной ленты (НМЛ) на магнитный барабан (НМБ) с контролем

правильности ввода ............... 542

Подпрограмма записи на магнитную ленту с контролем

правильности записи .............. _

Двойной счет .................. 544

Двои ной-трои ной счет ............. 545

Контроль по смыслу задачи............ 546

§ 91. Перерывы в решении .............. 547

За'пись на магнитную ленту............ _

Метод «Сбойной карты» .............. 549

§ 92. Отладка программы.................. 551

Первый этап. Проверка перфоленты........ _

Второй этап. Проверка арифметических операторов

(блоков) .................... 552

Третий этап. Проверка логики........... 557

Исправление ошибок ............. 559

§ 93. Вывод результатов вычислений. Округление результатов вычислений ................. 560

Преобразование результатов из полулогарифмической

формы в форму с фиксированной запятой..... 562

Печать в одну строку............... —

РАЗДЕЛ ЧЕТВЕРТЫЙ ПРИЛОЖЕНИЕ

Перевод десятичных чисел в восьмеричную систему счисления ................. 567

Таблица 1. О < X < 999; &Х = 1 ...... _

Таблица 2. О < X <999-103; ДХ = 103 .... 570

Таблица 3. О < X < 999-10~3; ДХ = 10-» . 574

Таблица 4. О < X < 999-1Q-6; ДХ = 10-« . 584

Таблица 5. О < X < 999-10-»; АХ = Ю-9 ... 594 Перевод дробных восьмеричных чисел в десятичную систему

счисления . . . . ;...............; gQ4

Таблица 6. 0,001 < X < 0,777; ДХ = 0,001 ... 605

Таблица 7. 0,000001 <X<0,000777; ДХ = 0,000001 609 Таблица 8. 0,000000001 < X < 0,000000777;

ДХ = 0,000000001............ . 613

Таблица 9. 0,000000000001 < X < 0,000000000777;

ДХ = 0,000000000001 ........... 617

Перевод чисел, представленных в машинном коде, в десятичную систему счисления .............. 621

Таблица 10. Машинный код-> десятичное число 622

Таблицы степеней чисел................. 623

Таблица 11. Значения степеней числа 2 .... _

Таблица 12. Значения степеней числа 3 .... 625

Таблица 13. Значения степеней числа 5..... 626

Таблица 14. Значения степеней числа 7 .... _

Таблица 15. Значения степеней числа 11 .... 627

Таблица 16. Некоторые постоянные ...... 628

ПРЕДИСЛОВИЕ

В настоящее время в отечественной литературе отсутствуют справочные пособия по программированию. Предлагаемая книга является первой попыткой восполнить этот пробел.

«Справочник программиста» состоит из двух томов. Первый том содержит основные численные методы решения некоторых классов задач, краткие характеристики отечественных вычислительных машин,, и рекомендации по программированию. Во втором томе приводятся стандартные и типовые программы для наиболее распространенных электронных вычислительных машин (ЭВМ).

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

При подборе рекомендованной литературы предпочтение отдавалось широкоизвестным и общедоступным источникам. Естественно, что библиография не претендует на полноту.

Во втором разделе первого .тома приводятся характеристики и дается система команд ряда отечественных универсальных цифровых ЭВМ.

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

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

В третьем разделе изложены рекомендации по составлению программ для ЭВМ «БЭСМ», «Урал» и «Стрела», получивших наиболее широкое распространение. Объем сообщаемых сведений обеспечивает, по мнению авторов, возможность написания программ для указанных машин. Эти рекомендации могут также оказаться полезными при программировании для других ЭВМ.

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

При составлении Справочника авторы пользовались как известной литературой, так и опытом работы на ЭВМ.

Главы 1, 3—5, 12, 17, 19 написаны А. Т. Макушкиным; главы 2, 13, 16 — Я. С. Дымарским; главы 6, 7, 8, 11 — В Р. Эрглисом; глава