Криницкий Н. А., Миронов Г. А., Фролов Г. Д. Программирование и алгоритмические языки/Под ред. А. А. Дородницына.— 2-е изд., испр. и доп.— М.: Наука. Главная редакция физико-математической литературы, 1979.
Книга представляет собой справочное пособие по программированию и алгоритмическим языкам. Она состоит из двух частей. Первая часть содержит общие вопросы программирования на вычислительных системах: теоретические основы программирования, некоторые вопросы теории алгоритмов, равносильные преобразования логических схем, строгое определение математического обеспечения ЭВМ и др. Вторая часть содержит описание алгоритмических языков: языка ассемблера, алгола-60, фортрана, кобола, ПЛ/1, которые получили широкое применение на современных вычислительных машинах и системах.
Книга предназначена для научных сотрудников, инженеров, аспирантов и студентов различных вузов.
Предыдущее издание выходило в 1975 г.
ОГЛАВЛЕНИЕ
Предисловие ко второму изданию.................... 11
Глава 1. Основы теории программирования............ 13
§ 1.1. Основные понятия ...................... 13
1.1.1. Буквы, связи, оболочки, конструкции (13). 1.1.2. Слова, алфавиты, классификация конструкций (16). 1.1.3. Общая структурная схема цифровой программно-управляемой машины (23). 1.1.4. Принципы действия программно-управляемой машины (26).
§ 1.2. Элементы теории формальных языков ............. 29
1.2.1. Синтаксис формального языка (31). 1.2.2. Семантика формального языка (36).
§ 1.3. Системы счисления...................... 37
1.3.1. Позиционные системы счисления (38). 1.3.2. Перевод чисел из одной системы счисления в другую (45). 1.3.3. Формы представления чисел в машинах (48).
§ 1.4. Элементы математической логики .............. 51
1.4.1. Понятие логических связей, логического значения и высказывания (51). 1.4.2. Двоичные функции и алгебро-логические операции (54). 1.4.3. Основные свойства алгебро-логических операций и логических связей (57). 1.4.4. Полные системы алгебро-логических операций и логических связей (60). 1.4.5. Понятие предиката (62).
§ 1.5. Элементы теории алгоритмов................. 63'
1.5.1. Понятие алгоритма (63). 1.5.2. Первичные алгоритмы (66). 1.5.3. Понятие операции (69). 1.5.4. Натуральные алгоритмы (72). 1.5.5. Полное определение алгоритма (74). 1.5.6. Локальные операции над конструкциями (76). 1.5.7. Локальные первичные алгоритмы. Коллектив алгоритмов (79). 1.5.8. ЭВМ как физическая реализация алгоритма выполнения программ (82).
Глава 2. Язык логических схем и машинные языки....... 87
§ 2.1. Язык логических схем (ЯЛС)................ 87
2.1.1. Алфавит ЯЛС (87). 2.1.2. Первичные структуры языка логических схем (88). 2.1.3. Язык операндов, связанный с ЯЛС (92). 2.1.4. Элементарные операторы (93). 2.1.5. Операторы; их классы, применяемые в ЯЛС' (94). 2.1.6. Знаки операторов и операторов, зависящих от;
5 ОГЛАВЛЕНИЕ
параметров (95). 2.1.7. Запись алгоритма на ЯЛС. Логическая схема и расшифровка операторов (96). 2.1.8. Правило выполнения алгоритма, заданного на ЯЛС (98). 2.1.9. Выражения. Замыкания операторов. Обобщенные операторы (100). 2.1.10. Соглашения, упрощающие запись алгоритмов (101). 2.1.11. Совмещение алгоритмов (103).
§ 2.2. Машинные языки операндов ................ 103
2.2.1. Язык чисел с фиксированной запятой (103). 2.2.2. Сумматоры (104). 2.2.3. Прямой код (106). 2.2.4. Обратный код (107). 2.2.5. Дополнительный код (109). 2.2.6. Кодирование чисел с фиксированной запятой в машинах (ПО). 2.2.7. Язык чисел с плавающей запятой. Представление чисел в ЭВМ (112). 2.2.8. Кодирование цифро-буквенной информации (113).
§ 2.3. Машинные алгоритмические языки ............. 115
2.3.1. Элементарные машинные операции (115). 2.3.2. Арифметические операции (117). 2.3.3. Поразрядные операции над машинными словами и переносы (120). 2.3.4. Логические операции (122). 2.3.5. Операции, изменяющие содержимое регистра команд (123). 2.3.6. Операции перехода (124). 2.3.7. Операции, изменяющие содержимое индексного или базового регистра (125). 2.3.8. Операции над буквенной информацией (126). 2.3.9. Машинные алгоритмические языки. Системы команд (126).
Глава 3. Программирование.................... 13-2
§ 3.1. Основные этапы процесса решения задачи на ЭВМ....... 132
3.1.1. Математическая формулировка задачи (132). 3.1.2. Разработка методики решения задачи (133). 3.1.3. Разработка алгоритма решения задачи (133). 3.1.4. Программирование (135). 3.1.5. Отладка программы (136). 3.1.6. Подготовка исходных данных. Решение задачи на ЭВМ (137).
§ 3.2. Языки программирования .................. 139
3.2.1. Формальные алгоритмические языки (139). 3.2.2. Неалгоритмические формальные языки программирования (141). 3.2.3. Не вполне формализованные знаковые системы (141).
§ 3.3. Программирование на языке ЭВМ.............. 142
3.3.1. Связь между распределением памяти и составлением команд (142).
3.3.2. Символические адреса (142).
§ 3.4. Операторный метод программирования............. 145
3.4.1. Сущность операторного метода программирования (145). 3.4.2. Организация программ (149).
§ 3.5. Некоторые приемы программирования............. 151
3.5.1. Операторы, зависящиеотпараметров. Индексация (151). 3.5.2. Программирование в относительных адресах. Базирование (155). 3.5.3. Построение циклов (158). 3.5.4. Логические шкалы (162). 3.5.5. Выделение подпрограммы (164).
Глава 4. Равносильные преобразования алгоритмов........ 168
§ 4.1. Понятие равносильности алгоритмов. Комплексы. Равносильные
преобразования....................... 168
§ 4.2. Однородный комплекс. Эквивалент однородного комплекса . . 170 § 4.3. Распознавание равносильности однородных комплексов с помощью
их эквивалентов ........................ 173
ОГЛАВЛЕНИЕ '7
§ 4.4. Полная система равносильных преобразований однородных комплексов ............................ 176
§ 4.5. Действия над однородными комплексами. Пакеты однородных комплексов ............................ 181
4.5.1. Сложение однородных комплексов (181). 4.5.2. Умножение однородных комплексов (182). 4.5.3. Единичные' и обратные комплексы (183). 4.5.4. Пакеты однородных комплексов. Равносильность пакетов (184).
§ 4.6. Основные равносильные преобразования алгоритмов, заданных на
ЯЛС............................. 184
§ 4.7. Равносильные преобразования, не связанные с внутренними свойствами операторов....................... 186
§ 4.8. Основные преобразования логических операторов........ 190
§ 4.9. Равносильные преобразования нелогических операторов..... 192
§ 4.10. Перестановки операторов .................. 194
§ 4.11. Подчиненность оператора предикату............. 195
§ 4.12. Вопрос о полноте системы основных равносильных преобразований
алгоритмов. Область их применений............... 197
Глава 5. Математическое обеспечение ЭВМ........... 198
§ 5.1. Уточнение понятия математического обеспечения ЭВМ .... 200 § 5.2. Классификация программ, входящих в систему математического
обеспечения ЭВМ....................... 202
5.2.1. Операционная система (203). 5.2.2. Система средств программирования (212). 5.2.3. Ввод и вывод информации. Понятие файла (217).
5.2.4. Система средств поддержки математического обеспечения (219).
5.2.5. Система управления данными (220). 5.2.6. Комплексы прикладных программ (приложения) (220).
§ 5.3. Математическое обеспечение ЭВМ как интерпретация ряда понятий
теории алгоритмов ....................... 221
§ 5.4. Системное программирование.................. 225
§ 5.5. Дополнительные сведения о формальных языках....... 228
5.5.1. Формальные грамматики (228). 5.5.2. Формальные языки, порождаемые индуктивными грамматиками (229). 5.5.3. Формальные языки, порождаемые дедуктивными грамматиками (231). 5.5.4. Связь между индуктивными и дедуктивными грамматиками (233). 5.5.5. Формальная семантика формального языка (235). 5.5.6. Сущность трансляции (237).
Глава 6. Символическое программирование............. 238
6.1. Понятие автокода или языка символического программирования (языка ассемблера).......................... 238
6.2. Алфавит языка символического программирования....... 241
6.3. Первичные структуры языка символического программирования . . 242
6.4. Символические адреса...................... 244
6.5. Язык операндов, связанный с языком символического программирования ............................... 248
б ОГЛАВЛЕНИЕ
6.6. Операторы языка символического программирования....... 255
6.6.1. Одиночные действующие операторы (255). 6.6.2. Макрооператоры (261). 6.6.3. Операторы описания конструкций из операторов и распределения памяти (263). 6.6.4. Операторы описания и распределения памяти (266). 6.6.5. Операторы — отладочные средства (268).
6.7. Выполнение записей на языке символического программирования . 269
6.8. Общая характеристика языка символического программирования системы 1ВМ-360........................ 270
Глава 7. Введение в алгоритмический язык алгол-60...... 272
§ 7.1. Алфавит алгоритмического языка алгол........... 273
§ 7.2. Первичные структуры в алголе................ 274
§ 7.3. Переменные. Массивы. Описания типа............. 276
§ 7.4. Язык операндов, связанный с алголом ........... 277
§ 7.5. Указатели функций...................... 279
§ 7.6. Выражения в алголе..................... 280
7.6.1. Логические выражения (280). 7.6.2. Арифметические выражения (281). 7.6.3. Именующие выражения (282). 7.6.4. Вычисление выражений (282).
§ 7.7. Операторы.......................... 284
7.7.1. Составной оператор (285). 7.7.2. Блок (285). 7.7.3. Оператор присваивания (286). 7.7.4. Оператор перехода (287). 7.7.5. Описание переключателя (287). 7.7.6. Оператор процедуры (288). 7.7.7. Описание процедуры (289). 7.7.8. Вычисление значения функции (291). 7.7.9. Процедуры-коды. Процедуры ввода и выдачи (292). 7.7.10. Побочный эффект (294). 7.7.11. Пустой оператор (295). 7.7.12. Оператор цикла (295). 7.7.13. Оператор «если» (297). 7.7.14. Альтернативный оператор (297).
§ 7.8. Алгол-программа. Примечания в ней.............. 298
§ 7.9. Алгоритм выполнения алгол-программы........... 299
§ 7.10. Заключительные замечания.................. 304
Глава 8. Введение в алгоритмический язык фортран....... 307
§ 8.1. Алфавит алгоритмического языка фортран......... 307
§ 8.2. Первичные структуры в фортране............. 308
§ 8.3. Переменные. Массивы..................... 311
§ 8.4. Указатели функций...................... 313
§ 8.5. Выражения.......................... 313
8.5.1. Логическое выражение (313). 8.5.2. Арифметическое выражение (314).
§ 8.6. Операторы.......................... 317
8.6.1. Метка (317). 8.6.2. Операторы присваивания (317). 8.6.3. Операторы безусловного перехода (319). 8.6.4. Операторы условного перехода (320). 8.6.5. Оператор продолжения (321). 8.6.6. Оператор останова (321). 8.6.7. Оператор цикла (321). 8.6.8. Оператор процедуры (323). 8.6.9. Оператор возврата (324). 8.6.10. Операторы обмена (324). 8.6.11. Оператор подвода файла (327). 8.6.12. Оператор задания конца
файла (327). 8.6.13. Оператор возврата записи файла (327). 8.6.14. Оператор поиска записи файла (327). 8.6.15. Неявный оператор задания типа (327). 8.6.16. Явный оператор задания типа (328). 8.6.17. Оператор задания размеров массивов (330). 8.6.18. Оператор задания общих областей (330). 8.6.19. Оператор эквивалентности (331). 8.6.20. Оператор формата (332). 8.6.21. Оператор описания файлов (345). 8.6.22. Оператор определения внешних подпрограмм (346).
§ 8.7. Подпрограммы...................•..... 346
8.7.1. Оператор-функция (346). 8.7.2. Внешняя функция (347). 8.7.3. Процедура (349). 8.7.4. Подпрограмма задания начальных данных (352).
§ 8.8. Фортран-программа....................... 352
Глава 9. Введение в алгоритмический язык кобол........ 355
§ 9.1. Алфавит алгоритмического языка кобол.......... 356
§ 9.2. Первичные конструкции языка кобол........... 357
9.2.1. Зарезервированные слова (357). 9.2.2. Слова пользователя (358).
§ 9.3. Структура кобол-программы.................. 361
§ 9.4. Раздел идентификации.................... 362
§ 9.5. Раздел оборудования...................... 363
9.5.1. Секция конфигурации (363). 9.5.2. Секция ввода-вывода (364).
§ 9.6. Раздел данных......................... 365
9.6.1. Сущность описания данных (388). 9.6.2. Описание данных (369).
9.6.3. Секция массивов (376). 9.6.4. Секция рабочей памяти (377).
9.6.5. Секция связи (378).
§ 9.7. Язык операндов, соответствующий языку кобол....... 378
§ 9.8. Выражения, используемые в коболе............ 380
9.8.1. Арифметическое выражение (380). 9.8.2. Логическое выражение
(381).
§ 9.9. Раздел процедур кобол-программы............... 386
9.9.1. Структура раздела процедур (386). 9^9.2. Типы операторов кобола (387).
§ 9.10. Арифметические операторы ................. 388
9.10.1. Повелительные арифметические операторы (388). 9.10.2. Условные арифметические операторы (390).
§ 9.11. Операторы управления порядком выполнения процедур . . . 390
9.11.1. Операторы ПЕРЕЙТИ. ИЗМЕНИТЬ и ОСТАНОВИТЬ (390).
9.11.2. Операторы ВЫПОЛНИТЬ и ВЫЙТИ (391).
§ 9.12. Операторы ввода — вывода.................. 395
9.12.1. Операторы ОТКРЫТЬ и ЗАКРЫТЬ] (395). 9.12.2. Операторы ЧИТАТЬ и ПИСАТЬ (396). 9.12.3. Операторы ПРИНЯТЬ и ВЫДАТЬ (396).
§ 9.13. Операторы переноса . ..................... 397
9.13.1. Операторы ПОМЕСТИТЬ и ПРОСМОТРЕТЬ (397). 9.13.2. Оператор СОРТИРОВАТЬ (399).
§ 9.14. Операторы связи с программами................ 399
9:14.1. Операторы ВЫЗВАТЬ, ВЫЙТИ-ИЗ-ПРОГРАММЫ и ОСВОБОДИТЬ (399). 9.14.2. Оператор ВОЙТИ (400).
§ 9.15. Оператор ЕСЛИ....................... 400
§ 9.16. Семантика кобола....................... 401
9.16.1. Особенности языка кобол (401). 9.16.2. Алгоритм выполнения кобол-программ (403).
Глава 10. Введение в алгоритмический язык ПЛ/1....... 406
§ 10.1. Алфавиты алгоритмического языка ПЛ/1 .......... 406
§ 10.2. Первичные структуры в ПЛ/1............... 408
§ 10.3. Переменные. Массивы. Структуры .............. 412
§ 10.4. Указатели функций...................... 420
§ 10.5. Выражения.......................... 420
10.5.1. Скалярное выражение (421). 10.5.2. Арифметические операции (421). 10.5.3. Операция сцепления (424). 10.5.4. Логические операции (427). 10.5.5. Операции сравнения (428). 10.5.6. Выражение над массивами (429). 10.5.7. Выражения над структурами и массивами структур (429).
§ 10.6. Описание данных....................... 430
10.6.1. Описатели данных (430). 10.6.2. Описатели имени входа (434). 10.6.3. Описатели размещения данных в памяти (436). 10.6.4. Описатели массивов и старших структур (439). 10.6.5. Описатели эквивалентности (439). 10.6.6. Описатели начальных данных (442). 10.6.7. Описатель отождествления структур (443). 10.6.8. Описатели файлов (443).
§ 10.7. Операторы.......................... 445
10.7.1. Блок (446). 10.7.2. Оператор присваивания (447). 10.7.3. Оператор перехода (450). 10.7.4. Оператор «если» (450). 10.7.5. Оператор никла (451). 10.7.6. Пустой оператор (453). 10.7.7. Оператор останова (454). 10.7.8. Описание процедуры (454). 10.7.9. Оператор процедуры ПЛ-программа (454). 10.7.10. Оператор входа в процедуру (457). 10.7.11. Оператор обращения к процедуре (457). 10.7.12. Оператор возврата (458). 10.7.13. Оператор конца (459). 10.7.14. Оператор размещения данных (459). 10.7.15. Оператор освобождения памяти (461). 10.7.16. Оператор ожидания (461). 10.7.17. Оператор описания данных (462). 10.7.18. Операторы ввода-вывода (462).
§ 10.8. Средства прерывания .................... 479
10.8.1. Ситуации прерывания (479). 10.8.2. Оператор задания реакции на прерывание (482). 10.8.3. Оператор отмены реакции на прерывание (483). 10.8.4. Оператор, имитирующий ситуацию прерывания (484).
§ 10.9. Встроенные функции.................... 484
Глава 11. Структура данных и организация программ ...... 492
§ 11.1. Структурное программирование ............... 492
§ 11.2. Структура данных и структура программ на ЯЛС...... 493
§ 11.3. Алгол-программа и организация данных........... 494
§ 11.4. Фортран-программа и структура данных .......... 496
§ 11.5. К обол-программ а и структура данных............ 497
§ 11.6. ПЛ/1-программа и структура данных............ 498
Литература ............................ 501
Предметный указатель....................... 504
ПРЕДИСЛОВИЕ КО ВТОРОМУ ИЗДАНИЮ
Эту книгу авторы старались построить в соответствии с особенностями нового этапа развития теории программирования. В книге сначала излагаются основы теории программирования: элементы математической логики, теории формальных языков и теории алгоритмов. На этом фундаменте построены все остальные части книги. Машины трактуются как физические реализации алгоритмов выполнения программ; сами программы — как особые классы алгоритмов; системы команд ЭВМ — как алгоритмические языки, получившие название машинных. Важная по своему месту в книге, хотя и небольшая глава посвящена понятию математического обеспечения ЭВМ. Основную часть книги составляет описание алгоритмических языков, среди которых ЯЛС (язык логических схем) важен потому, что удобен для равносильных преобразований алгоритмов и служит хорошим промежуточным языком в работах по автоматизации процессов и при программировании на языке ассемблера. Язык ассемблера и языки алгол-60, фортран-4, ПЛ/1 и кобол являются современными входными языками программирования. Первым описан ЯЛС, поскольку он используется в книге для описания машинных языков и равносильных преобразований алгоритмов; остальные языки описаны в том порядке, в котором они перечислены выше. Авторы сознательно нарушили естественный в смысле хронологии и развития идей порядок «фортран — алгол — кобол — ПЛ/1» и вынесли в начало алгол по следующей причине. Алгол лучше знаком советским программистам, так как привлек в себе внимание раньше других языков этого ряда, и потому другие языки будут, естественно, сопоставляться с алголом. Кобол в этой книге представлен своей русской версией, так как его международная версия для программистов, слабо знающих английский язык, теряет свои мнемонические возможности и достоинства.
В книге сохранены некоторые сведения о программировании на языках ЭВМ. Это обусловлено, во-первых, необходимостью для каждого программиста понимать принципы работы ЭВМ, которые без сведений о программировании не могут быть в полной мере усвоены. Во-втооых. указанные сведения необходимы для так на-
Цена: 150руб.
