Методы программирования: В 2-х томах. Т.1. Пер. с фран Ю.А. Первина. Под ред. и с предисловием А. П. Ершова.- № Мир, 1982
356 с.
Монография французски ученых, в которой систематически излагаются основные понятия инф матики, обсуждаются трудные проблемы методологии программирования, дается сравнение извести языков программирования: ФОРТРАН*, АЛГОЛа W, ПЛ/1 в др. Изложение сопровождается упраж ниями (с решениями).
В русском переводе книга разбита на два тома. В первый том (гл. I-V) наряду с общи сведениями о программировании рассмотрены основные свойства базовых языков программировал и управляющие структуры, а также обсуждаются подпрограммы и структуры данных.
Квита рассчитана на профессиональных программистов, желающих овладеть современными мето; ми программирования. Может служить учебным пособием по языкам программирования и алгоритм!
РЕДИСЛОВИЕ РЕДАКТОРА ПЕРЕВОДА
Разрыв- между последними достижениями информатики и пов-едневной практикой программирования, между трудностью задачи [рограммирования и примитивностью доступного арсенала средств, 1ежду головокружительным прогрессом оборудования и инерт-юстью программного обеспечения, по-видимому, нарастает с каж-(ым годом. Именно это положение вещей обсуждалось во вре-1Я дискуссии, посвященной проблеме подготовки квалифицирован-[ых программистов 80-х годов, которая стала одним из наибо-iee ярких событий недавно прошедшего в Японии и Австралии {семирного конгресса ИФИП-80. Признавая кризисное состояние фактики программирования и демонстрируя широкий спектр мне-[ий по поводу актуальной проблематики, участники дискуссии бы-[и, однако, единодушны в своей уверенности в «светлом будущем [рограммирования»; они пришли к заключению, что достичь его ложно лишь путем тщательно подготовленного всеобщего и интен-явного курса обучения, не только охватывающего сумму техни-[еских приемов, но в определенном смысле формирующего саму шчность программиста.
Естественно, что этот тезис родился не вчера. Уже в тече-[ие нескольких лет преподаватели программирования настойчиво [щут лучшие формы построения такого курса, охватывающего овременные методологические положения информатики. В этой сети хотя еще и не окончательных, но в целом идущих в. нужном вправлении попыток достойное место занимает предлагаемая вни-1анию читателей монография Б. Мейера и К. Бодуэна. Она опи-»ается на уже вошедшие в практику преподавания концепции мно-оязыкового или, правильнее сказать, надъязыкового подхода к обу-!ению программированию. Используя в качестве своего рода язы-:а спецификаций неформально описанные языковые конструкции -'высокого уровня», авторы весьма подробно показывают, как эти инструкции реализуются в распространенных алгоритмических языках, выбрав из них типичные представители: ФОРТРАН, ПЛ/1 и ^ЛГОЛ W. Авторы сумели, не выходя из контекста реального (зыка, внушить читателю оптимизм в его стремлении научиться юрошо составлять программы, не дожидаясь создания «идеальных» (зыков программирования.
Центральными главами учебника являются гл. III-VI, в кото->ых авторы излагают основные управляющие структуры, струк-:Уры данных и правила процедурной декомпозиции алгоритмов,
ОГЛАВЛЕНИЕ
Предисловие редактора перевода................. 5 -
Предисловие................... ........ 1
Глава I. Общие сведения о программировании............ IS
1.1. Введение....................... 16
1.2. Что такое информатика?................. 16
1.3. Что такое информация?................. 17
1.4. Что такое вычислительная машина?............ 19
1.4.1. Общие положения.................. 19
1.4.2. Подробнее о памяти................ 23
1.4.3. Ввод-вывод.................... 24
1.4.4. Оперативная память, внешняя память.......... 26
1.4.5. Порядок некоторых величин............. 27
1.5. Что может делать вычислительная машина?......... 29
L6. Что такое программирование?............... 31
1.7. Несколько ключевых слов................ 34'
1.8. Краткая история информатики............... 35
1.8.1. Прединформатика..................' 35
1.8.2. Протоинформатика................. 36
1.8.3. Информатика................... 37
Библиография...................• • 38
Задача........................ 39
Глава П. Введение в языки программирования ФОРТРАН, АЛГОЛ W, ПЛ/1 40
П.1. Основные характеристики................. 40
П.1.1. Значения и типы................. 41
П.1.1.1. Литеры.................. 41
П.1.1.2. Строки.................. 41
Н.1.1.3. Логические значения............. 41 -
П.1.1А Целые числа................ 42
П.1.1.5. Дробные числа («вещественные») . .,...... 42 ;
П. 1.1.6. Комплексные числа......... . . - - 44,-
П.1.2. Основные объекты: константы, переменные, массивы, выра- ч
жения...................... '
П.1.2.1. Константы................. ;**
П.1.2.2. Переменные........'........
П.1.2.3. Массивы.................
П. 1.2.4. Выражения.................
II. 1.3. Программы, операторы..............•
II.2. Алгоритмическая нотация.................
П.З. Введение в ФОРТРАН..................
П.3.1. История.....................
П.3.2. Значения и типы.................
П.3.3. Основные объекты языка.............. 54
П.3.3.1. Константы................. 54
Н.3.3.2. Переменные. Символические константы...... 55
Н.3.3.3. Массивы . . . . ;............ 57
И.3.3.4. Выражения................. 57
П.3.3.5. Обработка строк в ФОРТРАНе......... 60
П.3.4. Программы, операторы............... 61
П.3.4.1. «Работа» ФОРТРАНа и «программные модули» . . . 61
П.3.4.2. Физическая форма программы......... 62
Н.3.4.3. Некоторые операторы............ 63
П.4. Введение в АЛГОЛ W.................. 65
П.4.1. История..................... 65
П.4.2. Значения и типы.................. 67
П.4.3. Основные объекты языка.............. 67
11.4.3.1. Константы................. 67
И.4.3.2. Переменные................ 68
П.4.3.3. Массивы................. 69
11.4.3.4. Выражения................. 69
П.4.4. Программы, операторы............... 73
Н.4.4.1. Физическая форма программы......... 73
Н.4.4.2. Некоторые операторы........... 74
II.5. ПЛ/1........................ 75
Н.5.1. История..................... 75
Н.5.2. Значения и типы................. 76
II.5.3. Основные объекты языка.............. 77
П.5.3.1. Константы.................. 77
И.5.3.2. Переменные................ 79
И.5.3.3. Массивы................. 82
П.5.3.4. Выражения................. 83
П.5.4. Программы, операторы............... 89
П.5.4.1. Физическая форма программы........ . 89
П.5.4.2. Некоторые операторы.....-....... 89
Библиография....................... 91
Упражнения....................... 93
Глава III. Управляющие структуры................ 94
111.1. Введение.....Г................. 94
111.2. Обозначения..................... 95
111.2.1. Состояние программы............... 95
111.2.2. Блок-схемы................... 97
JII.3. Базовые структуры................... 100
Ш.3.1. Циклы..................... 100
Ш.3.1.1. Бесконечный цикл............. 100
Ш.3.1.2. Циклы, управляемые условиями (типы пока и ДО) 101
Ш.3.1.3. Цикл с параметром............ 103
111.3.2. Ветвления................... 104
Ш.3.2.1. Альтернатива............... 104
Ш.3.2.2. Многозначное ветвление........... 105
111.3.3. Цепочка.................... 107
IIL3.4. Подпрограммы................•. Ю8
111.3.5. Композиции базовых структур........... ПО
111.3.6. Управление с помощью таблиц........... П1
III.4. Свойства базовых структур: введение в формальную обработку
программ...................... 115
III.4.1. Введение и обозначения.............. 115
Ш.4.2. Свойства цепочки................. 117
Ш.4.3. Свойства альтернативы............. . Ц7
III.414. Свойства цикла................. 118
III.4.S. Заключение................... 121
Ш.5. Представление управляющих структур в ФОРТРАНе, АЛГОЛе W,
ПЛ/1.......................... ,21
111.5.1. Цепочка..................... 122
111.5.2. Циклы..................... 126
IH.5.2.1. Бесконечный цикл............. 126
Ш.5.2.2. Циклы пока и до............. 127
Ш.5.2.3. Цикл со счетчиком............. 129
111.5.3. Ветвления '................... 135
Ш.5.3.1. Альтернатива............... 135
Ш.5.3.2. Многозначные ветвления. Таблицы переходов . . . 139
III.6. Обсуждение: управляющие структуры и систематическое программирование .....'................. 143
Библиография....................... 146
Упражнения....................... 146
Глава ГУ. Подпрограммы.................... 156
IV.1. Введение....................... 156
IV.2. Определения и проблемы обозначений........... 157
IV.2.1. Определения.................. 157
IV.2.2. Определение и вызов; формальные параметры, фактические
параметры................... 158
IV.2.3. Проблемы обозначений; подпрограммы «операторы» и «выражения».................... 160
IV.2.4. Тип подпрограммы................ 163
IV.3. Введение в использование подпрограмм в ФОРТРАНе, АЛГОЛе W,
ПЛ/1........................ 164
IV.3.1. Подпрограммы в ФОРТРАНе............ 165
IV.3.1.1. Подпрограммы-«выражения»........ . 165
IV.3.1.2. Подпрограммы-«операторы»......... 166
IV.3.1.3. Замечания о подпрограммах ФОРТРАНа . . . . 168
IV.3.2. Подпрограммы в АЛГОЛе W............ 169
IV.3.3. Подпрограммы в ПЛ/1.............. 173
IV.4. Способы передачи информации между программными модулями 175
IV.4.1. Проблема................... 175
IV.4.2. Чистое чтение: передача значением.......... 177
IV.4.3. Чистая запись, передача результата . .* . . .•..... 181
IV.4.4. Чтение и запись: значение-результат, адрес, имя..... 183
IV.4.5. Передача массивов................ 194.
IV.4.6. Передача подпрограмм.............• 202
IV.4.7. Резюме.................... 204
IV.5. Обобществление данных................. 206
IV.5.1. Определение.................. 206
IV.5.2. Языки блочной структуры............. 206
IV.5.3. Методы ФОРТРАНа: понятие общей области ...... 207
IV.5.4. Обсуждение: обобществление или передача?...... 210
IV.6. Подпрограммы и управление памятью........... 212
IV.6.1. Свободные переменные; массивы с фиксированными при
выполнении границами.............. 212
IV.6.2. Статическое и динамическое распределения....... 213
IV.6.3. ФОРТРАН................... 215
IV.6.4. АЛГОЛ W................... 216
v IV.6.5. ПЛ/1..................... 218
IV.6.6. Реентерабельность. Многократное использование. Побочный
эффект..................... 220
IV.7. Расширения понятия подпрограммы............ %221
IV. 7.1. Иерархическая структура вызовов подпрограмм..... 221
IV.7.2. Пример использования сопрограмм........... 222
IV.7.3. Обсуждение и заключение............. 227
Упражнения..................... 228
Глава V. Структуры данных................... 230
V.I. Описание структур данных...............• 231
V.I.I. Уровни описания................. 231
V.I.2. Функциональная спецификация............ 233
V.I.3. Логическое описание; смежность; разделение случаев; перечисление..................... ^"
V.I.4. Физическое представление. Понятие указателя...... 244
V. 1.4.1. Разделение вариантов, перечисление....... . . 245
V.I.4.2. Соединение................. 245
V.I.5. Обсуждение. Проблемы............... 250
V.2. Структуры данных и языки программирования........ 252
V.2.I. Записи и ссылки в АЛГОЛе W.......... 253
V.2.2. Структуры и указатели в ПЛ/1............ 259
V.2.3. Сравнение АЛГОЛа W и ПЛ/1 ............ 266
V.2.4. Методы ФОРТРАНа................
V.3. Множества. Введение в систематику структур данных...... 271
V.4. Стеки......................... 274
V.4.I. Введение. Применения.................274
V.4.2. Функциональная спецификация............ 276
V.4.3. Логическое описание................ 278
V.4.4. Физическое представление.............. 279
V.4.4.I. Сплошное представление........... 279
V.4.4.2. Цепное представление............. 282
V.4.4.3. Конкретное представление стеков в ПЛ/1 ..... 285
V.4.5. Расширение понятия стека.............. 286
V.5. Файлы........................ 286
V.5.I. Введение. Применения................ 286
V.5.2. Функциональная спецификация............ 287
V.5.3. Логическое описание................ 290
V.5.4. Физическое представление............- . 291
V.5.4.I. Цепное представление............. 291
V.5.4.2. Сплошное представление........... 293
V.5.5. Обобщение: файл с двойным доступом ......... 297
V.6. Линейные списки.................... 298
V.6.I. Введение. Применения............... 298
V.6.2. Функциональная спецификация............ 298
V.6.3. Логическое описание................ 299
V.6.4. Физические представления.............. 300
V.7. Деревья, двоичные деревья . ............... 307
V.7.I. Деревья: определение и применения.......... 307
V.7.2. Введение в двоичные деревья............ 310
V.7.3. Преобразование дерева в двоичное дерево....... 311
V.7.4. Функциональная спецификация........... . 312
V.7.5. Логическое описание................ 313
V.7.6. Физическое представление.............. 315
V.7.6.I. Цепное представление............. 315
V.7.6.2. Сплошное представление........... 317
V.8. Списки........................ 317
V.8.I. Введение. Применения............... 317
V.8.2. Функциональная спецификация............ 320
V.8.3. Логическое описание................ 321
V.8.4. Списки, деревья, двоичные деревья........... 324
V.8.5. Физическое представление.............. 326
V.8.6. Три примера................... 329
V.9. Массивы........^.............. 332
V.9.I. Функциональная спецификация............ 332
V.9.2. Логическое описание................ 334
V.9.3. Физическое представление.............. 334
V.9.4. Представление разреженных массивов......... 335
V.9.5. Массивы и языки: дополнения............ 340
V.10. Графы....................... 344
V.10.1. Определения. Графические представления ........ 344
V.10.2. Физическое представление конечных графов ...... 346
Библиография....................... 349
Задачи.......................... 349
Цена: 150руб.
