Электронные цифровые программно-управляемые машин появились в 40-х годах XX века как средство сверхбыстры вычислений. Потребность в этих машинах назрела в связ с необходимостью решения ряда сложных и трудоемки: задач, выдвинутых техникой и естествознанием. Изучена программно-управляемых машин показало, что возможност! их далеко выходят за рамки математических вычислений (так, с их помощью можно осуществлять автоматический перевод текстов с одного языка на другой, управление объектами, например станками, получение следствий из посылок, выбор сведений из хранилища информации, например подбор литературы, в которой освещается тот или иной вопрос, и др.). Можно сказать, что цифровые программно-управляемые машины являются средством механизации умственного труда и автоматизации производственных процессов.
Одновременно с появлением цифровых программно-управляемых машин возникла новая область прикладной математики — программирование (целью которого является составление «программ действий» машины для решения различных задач). Сперва программирование представлялось скорее искусством, чем наукой. Составление программ производилось вручную и было подобно решению сложных комбинированных задач (таких, например, как шахматные). Первым этапом в развитии программирования было накопление различных практических приемов, облегчавших составление программ. Постепенно выявлялись внутренние проблемы программирования. Был разработан ряд методов программирования. Появление операторного метода программирования, предложенного в 1953 г. А. А. Ляпуновым, позволило по-настоящему поставить вопрос об автоматизации программи-
ст АВТОРОВ 11
рования. Сущность операторного метода заключается в том, что алгорифм решения задачи представляется в виде так называемой логической схемы программы, элементами которой являются операторы. Логические схемы позволяют расчленить громоздкий процесс составления программы и допускают «механическое» (выполнимое по формальным правилам) составление частей программы, отвечающих операторам, и объединение их в одно целое. На идеях операторного метода основываются программирующие программы. В настоящее время работы в области автоматизации программирования ведутся в направлении создания алгорифмических языков. Описание на алгорифмическом языке методов решения задач допускает их формальную переработку в программы. В основе этих языков лежит операторный метод. От универсальных программирующих программ намечается переход к библиотекам специализированных программирующих программ, позволяющим более полно автоматизировать процесс программирования.
Постановка все более сложных задач приводит к появлению весьма сложных программ, требующих огромного времени для выполнения даже на самых быстродействующих машинах; в связи с этим возникла потребность исследования возможности равносильных преобразований программ с целью их «улучшения». В настоящее время ведутся работы по равносильным преобразованиям логических схем, с помощью которых преобразование программ может быть произведено еще до программирования.
Наконец, ведущиеся в настоящее время исследования самой сущности процессов программирования и выполнения программ машинами, а также исследование принципов действия машин приводят к выводу, что программирование является прикладной ветвью теории алгорифмов. Программы представляют собой определенное семейство алгорифмов, а электронные цифровые программно-управляемые машины являются автоматами для выполнения этих алгорифмов.
В настоящей книге авторы делают попытку изложить сущность программирования, исходя из современных идей, и по возможности осветить современный уровень этой области. В отличие от других книг, программирование здесь излагается без привязки к какой-либо из существующих или выдуманных программно-управляемых машин.
СОДЕРЖАНИЕ От авторов.......•
ЧАСТЬ ПЕРВАЯ
ПРОГРАММИРОВАНИЕ ДЛЯ ПРОГРАММНО-УПРАВЛЯЕМЫХ
МАШИН
Глава I. Основы теории программно-управляемых машин... ]3
§ 1. Некоторые общие сведения о программно-управляемых
цифровых машинах.................13
1. Общая структурная схема цифровой программно-управляемой машины ()3). 2, Принцип действия программно-управляемой машины (15)....................
§ 2. Системы счисления .................16
1. Позиционные системы счисления (17), 2. Перевод чисел из одной системы счисления в другую (27). 3. Формы представления чисел в машинах (30)...........
§ 3. Элементы математической логики ..........34
1. Двоичные функции и алгебрологические операции (34).
2. Понятие логических связей, значения истинности и высказывания (36). 3. Основные свойства алгебрологических операций и логических связей (38). 4. Полные системы алгебрологических операций и логических связей (41). 5. Понятие предиката (43).
§ 4. Элементы теории алгорифмов ............4G
1. Буквы и алфазиты (46). 2. Слова (47). 3. Композиция и расчленение слов (48). 4. Равнозначные алфавиты (50). 5. Предметное тождество слов (50). 6. Операции над словами (51). 7. Транспонирование операций (52). 8- Понятие алгорифма (53). 9. Уточнение понятия алго-Р"Фма- Алгорифм выполнения. Абстрактная машина (56). it n тРактные машины с размеченной памятью (59). П. Реальные программно-управляемые машины как физические модели абстрактных машин с размеченной памятью (62).
Глава 2. Система операций и система команд программно-управляемой машины..................66
§ 1. Система операций программно-управляемой машины и
их классификация..................66
1. Классификация запоминающих устройств машины (66).
2. Классификация операций .машины (67).
§ 2. Кодирование чисел для их изображения в устройствах машины ......................68
1. Прямой код (69). 2. Сумматоры (70). 3. Обратный код (72). 4. Дополнительный код (74). 5. Кодирование чисел в машинах (76).
§ 3. Основные операции машины.............80
1. Арифметические операции (80), 2. Неарифметические операции над кодами и переносы (84). 3. Логические операции (87). 4. Операции, изменяющие содержимое регистра команд (89). 5. Операции перехода (90). 6. Операции, изменяющие содержимое индексного регистра (91). § 4. Система команд программно-управляемой машины . . 92 1. Система команд. Общий вид команды (92). 2. Условная структура общего вида команды (94).
Глава 3. Особенности решения задач на цифровых программно-управляемых машинах.............95
§ 1. Порядок решения задач на машине.........95
1. Основные этапы работы (95). 2. Краткая характеристика основных этапов (95).
§ 2. Разработка решающего алгорифма. Задание функций 96
1. Учет особенностей электронной цифровой машины (96).
2. Учет стоимости решения и расхода времени (98).
3. Способы задания функций (98). 4. Масштабирование (99).
§ 3. Методы программного контроля. Отладка программы
на машине.....................103
1. Программный контроль (103). 2. Отладка программы (104).
§ 4. Организация программ ...............106
1. Понятие организации программы (106). 2. Схема организации (106).
Глава 4. Операторный метод программирования......Ю8
§ 1. Простейшее программирование ...........108
1. Связь между распределением памяти и составлением команд (108). 2. Символические адреса (108).
СОДЕРЖАНИЕ 7
§ 2. Операторный метод программирования........ИЗ
1. Схема решающего алгорифма (113). 2. Некоторые термины и обозначения (119). 3. Элементарные операторы программы (120). 4. Стандартные операторы. Логическая схема программы (123).
Глава 5. Равносильные преобразования логических схем . . 13[
§ 1. Комплексы и их эквивалентные преобразования ... 131
1. Некоторые общие термины и условные обозначения (131).
2. Память. Операторы (133). 3. Операторы специального вида (134). 4. Комплексы (135). 5. Эквивалент комплекса (138). 6. Эквивалентность комплексов (139). 7. Основные эквивалентные преобразования (143). 8. Сложение комплексов (149). 9. Умножение комплексов (151). 10. Единичные и обратные комплексы (152). 11. Пакеты комплексов. Эквивалентность пакетов (153).
§ 2. Формальное определение логической схемы. Равносильность логических схем................153
1. Основные типы операторов (153). 2. Понятие логической схемы (157). 3. Реализация схемы. Равносильность схем. Выражения. Равносильность выражений (159).
§ 3. Основные равносильные преобразования логических
схем........................161
1, Равносильные преобразования, не связанные с внутренними свойствами операторов (161). 2. Основные преобразования логических операторов (167). 3. Равносильные преобразования нелогических операторов (169). 4. Перестановки операторов (171). 5. Подчиненность оператора предикату (172).
Глава 6. Некоторые приемы программирования......175
§ 1. Операторы, зависящие от параметров, их переадресация
и восстановление..................175
1. Операторы, зависящее от параметров, и операторы переадресации (175). 2. Операторы восстановления (178).
§ 2. Циклы.......................379
I. Элементарный итерационный цикл (179). 2. Элементарный цикл с переадресацией (180). 3. Элементарный цикл с переадресацней и восстановлением (181). 4. Сложные циклы (183). 5. Счетчик выполнений цикла (184). § 3. Приемы, связанные с применением стандартных ячеек. 187 I. Вынесение величин в стандартные ячейки (187). 2. Циркуляция величин в стандартных ячейках (183).
§ 4. Логические шкалы. Операторы формирования .... [90 1ф Л?,Гд^еские шкалы (190). 2. Операторы формирова-§ 5. Выделение подпрограммы .............. 196
I. Понятие подсхемы и подпрограммы. Выделение подпрограммы (196). 2. Построение обращений к выделенной подпрограмме (197).
Глава 7. Автоматизация программирования ........ 201
§ 1. Автоматизация отдельных работ при программировании вручную ......................
1. Автоматизация присвоения истинных адресов (201).
2. Автоматизация исправления некоторых ошибок (202).
3. Автоматизация отладки программ (203).
§ 2. Автоматизация составления программ ........
1. Сущность автоматизации программирования (205).
2. Способы автоматического программирования (205).
3. Компиляция и интерпретация (207).
§ 3. Метод библиотеки стандартных подпрограмм ..... 208 1. Коды, применяемые в подпрограммах (208). 2 Две разновидности метода библиотеки подпрограмм (209). § 4. Компилирующая система БСП-1 ........... 211
1. Условия, налагаемые на стандартные подпрограммы (211).
2. Кодирование подпрограмм (214). 3. Постоянная информация о стандартной подпрограмме (216), 4. Переменная информация о стандартной подпрограмме (217). 5. Включение стандартной подпрограммы в составляемую программу (218).
§ 5. Компилирующая система ССП-2 , .......... 219
I. Условия, налагаемые на стандартные подпрограммы (219). 2. Кодирование подпрограмм (221). 3. Информация о стандартной подпрограмме (222). 4. Объединение стандартных подпрограмм и частей составляемой программы (223). § 6. Интерпретирующая система ИС-2 .......... 225
1. Условия, налагаемые на стандартные подпрограммы (226). 2. Организация интерпретирующей системы ИС-2 (226).
§ 7. Метод программирующих программ ......... 227
1. Появление программирующих программ (227). 2. Стандартные и нестандартные операторы при методе ПП (22S).
3. Блочное строение программирующих программ (229).
4. Программирование методом ПП (231). 5. Входные языки (231).
§ 8. Перспективы развития метода программирующих про-
грамм ....................... 238
1. Униаерсальньге ПП (238). 2. Метод библиотеки специализированных ПП (239).
ЧАСТЬ ВТОРАЯ
ОПИСАНИЯ НЕКОТОРЫХ ПРОГРАММНО-УПРАВЛЯЕМЫХ МАШИН
Вводные замечания ..................241
Глава 8. Программно-управляемая машина Урал-1 .... 243 Основные характеристики машины Урал-1 (243). Краткие сведения об основных устройствах машины (244). Представление чисел и команд (246). Система операций и команд (248). Пульт управления (248), Подготовка данных (261). Глава 9. Программно-управляемая машина Урал-2 .... 263 Основные характеристики машины Урал-2 (263). Краткие сведения об основных устройствах машины (264). Представление чисел и команд (267). Система операций и команд (268). Пульт управления (269). Подготовка данных (282). Глава 10. Программно-управляемая машина «Сетунь» . . 286 Основные характеристики машины «Сетунь» (286). Краткие сведения об основных устройствах машины (287). Представление чисел и команд (290). Система операций и команд (291). Пульт управления (291). Подготовка данных (301). Дополнение (303).
Глава И. Программно-управляемая машина М-3.....305
Основные характеристики машины М-3 (305). Краткие сведения об основных устройствах машины (306). Представление чисел и команд (309). Система команд (310). Пульт управления (311) Подготовка данных (314).
Глава 12. Программно-управляемая машина М-2......315
Основные характеристики машины М-2 (316). Краткие сведения об основных устройствах машины (317). Представление чисел и команд (320). Система операций и команд (322). Пульт управления (322). Подготовка данных (331).
Глава 13. Программно-управляемая машина БЭСМ-2 . . . 333 Основные характеристики машины БЭСМ-2 (333) Краткие сведения об основных устройствах машины (334). Представление чисел и команд (336). Система операций и команд (338). Пульт управления (338). Подготовка данных (351).
Глава 14 Программно-управляемая машина «Стрела» . . . 355
Основные характеристики машины «Стрела» (355). Краткие сведения ©б основных устройствах машины (356). Представление чисел и команд (359). Система операций и команд (359). Пульт управления (372) Подготовка данных (373)
Ьиблиография........... .......376
Алфавитный указатель ..'.','"'.' . ........ 379
