Авторы книги в самом начале своего предисловия расшифровывают содержание понятия
„Informatik", взятого ими для названия их труда (см. также начало исторического очерка в конце книги). И хотя переводчик и редактор согласны с авторами в выборе названия, сохранение его в русском переводе требует некоторого пояснения.Отправляясь от содержания книги, мы могли бы с определенностью сказать, что перед нами учебник по программированию задач обработки информации для ЭВМ с помощью алгоритмических языков. При такой характеристике содержания казалось бы естественным озаглавить русский перевод
„Введение в программирование". Однако это дезориентировало бы читателя, ибо данный учебник по содержанию гораздо шире существующих на русском языке книг с аналогичными заголовками. Кроме того такая, чересчур прагматическая, подмена названия игнорировала бы стремление авторов внедрить в сознание читателей получающий все большее распространение термин, который объединяет самые разные стороны программирования и использования ЭВМ, а также методов их конструирования и разработки программного обеспечения.Можно было бы и не тратить слов на объяснение перевода названия, если бы не
„перехват" термина, осуществленный лет десять назад специалистами по документалистике и информационно-поисковым системам. Редактор имеет в виду книгу А. И. Михайлова и А. И. Черного „Основы информатики" („Наука", М., 1968), в которой описываются методы существенно более узкой области применения ЭВМ. Впрочем, хотя указанная книга и получила довольно широкое распространение, в последующих работах употребление слова „информатика" в этом, более узком смысле, было не столь частым. В связи с этим переводчик и редактор сочли более полезным последовать существующей традиции сохранять при переводе научные термины, основанные на латинских словах, ограничиваясь их транслитерацией в алфавит национального языка.Итак, перед нами вводный курс информатики. Это, по-видимому, первый в нашей литературе пример учебника
„второго поколения", заметно отличающегося от известных у нас книг, таких, как, напри-меР' „Курс программирования" Е. А. Жоголева и Н. П. Трифонова („Наука", М., 1971), „Программирование и использование цифровых вычислительных машин" Р. Ледли („Мир", М., 1966).Отличительной особенностью
„Информатики" является в целом Удавшаяся попытка авторов преподавать основы программирования и обработки информации как курс, излагающий сложившиеся концепции и понятия (прежде всего связанные с современными алгррит-мическими языками), которые затем, с одной стороны, формализуются в некотором математическом аппарате и, с другой стороны, раскрываются в виде конструкций некоторого обобщенного машинного языка. Это очень серьезное методологическое новшество, полностью отвечающее насущной потребности ^самоопределения" информатики и идентификации ее основных понятий. Авторы книги с присущей им скромностью ссылаются на некоторых специалистов, провозгласивших концептуальный подход в преподавании информатики, однако справедливости ради следует отметить, что, пожалуй, именно в
„Информатике" указанный подход получил свое наиболее достоверное и успешное развитие. За четыре года этот учебник выдержал в ФРГ два издания и несколько перепечаток и стал основным вводным курсом по информатике в ряде стран. [И первое, и второе немецкое издание, с которого делался перевод, выходили в двух частях (в каждой части по четыре главы), с отдельными предисловиями и посвящениями. В настоящем издании было сочтено целесообразным объединить обе части в одной книге. Специально для русского издания авторы подготовили общее единое предисловие к книге.]На первый взгляд, особенно при чтении начальных глав, изложение может показаться несколько калейдоскопичным. Мы надеемся, однако, что это не смутит любознательного читателя, поскольку крепко сбитая общая организация книги позволит ему не потерять ориентировки, а разнообразие материала является, попросту говоря, отражением реального богатства и многообразия идей и понятий информатики.
Язык оригинала
„Информатики" возрождает давно сложившиеся традиции добротной немецкой научной прозы. Стиль авторов в значительной степени сохранен в отличном переводе В. К. Сабель-фельда. Редактору показалось полезным предупредить об этом читателя, поскольку в нашей переводной литературе по вычислительному делу до последнего времени доминировала американо-английская стилистика, во многом отличающаяся от европейских традиций.При переводе книг учебного характера часто появляется искушение
„подправить" текст, с тем чтобы улучшить изложение или адаптировать его, главным образом в части ссылок или комментирующих сносок. После некоторых колебаний переводчик и редактор решили сознательно умерить свою активность и ограничиться терминологическими примечаниями, постаравшись представить читателю максимально аутентичный перевод, в надежде, что этот в высшей степени интересный учебник сыграет свою побудительную роль в подготовке оригинальных отечественных учебников по основам программирования и обработки информации, формирующих современный уровень и тенденции развития информатики.Новосибирск, Академгородок Д f] Ершов
апрель 1976 г.
ОГЛАВЛЕНИЕ
Предисловие редактора перевода . . ................. 5
Предисловие............. ................ 7
Глава 1. Информация и сообщение.................. 11
1.1. Сообщение и информация................ 11
1.1.1 Языковые сообщения ............... 14
1.1.2. Письмо..................... 15
1.2. Органы чувств...................... 16
1.2.1. Работа органов чувств, проведение возбуждения . . 18
1.2.2. Обработка раздражения в мозге......... 21
1.2.3. Значение информационных представлений..... 26
1.3. Устройства связи.................... 26
1.3.1. Сигналы и параметры сигналов.......... 30
1.4. Дискретные сообщения . ............... . 31
1.4.1. Знаки, наборы знаков, алфавиты......... 31
1.4.2. Коды и кодирования .............. 41
1.4.3. Символы..................... 48
1.5. Дискретизация..................... 49
1.5.1. Развертка.................... 49
1.5.2. Квантование................... 53
1.6. Теория информации Шеннона.............. 53
1.6.1. Шенноновские сообщения............. 53
1.6.2. Количество информации............. 55
1.6.3. Пропускная способность канала......... 64
1.6.4. Надежность кода................. 66
1.7. Обработка сообщений и обработка информации...... 67
1.7.1. Обработка сообщений как кодирование...... 67
1.7.2. Интерпретация обработки сообщений....... 68
1.7.3. Конструктивное описание дискретного процесса обработки ..................... 71
Глава 2. Основные понятия программирования............ 74
2.1. Конструирование алгоритмического языка........ 74
2.2. Объекты ... ..................... 75
2.2.1. Обозначение и значение.............. 76
2.2.2. Произвольно выбираемые обозначения ...... 80
2.2.3. Имена...................... 81
2.2.4. Генерируемые имена............... 83
2.2.5. Переменная................... 85
2.3. Формулы....................... 87
2.3.1. Формулы с примитивными объектами в качестве операндов ..................... 88
2.3.2. Обобщения вида................. 93
2.3.3. Операция разыменования............. 94
2.3.4. Отношение тождества для имен.......... 97
2.3.5. Условные формулы................ 97
2.3.6. Выбирающая формула................ 99
2.4. Подпрограммы..................... JQQ
2.4.1. Подпрограмма без параметров.......... Ю1
2.4.2. Подпрограммы с параметрами.......... ЮЗ
2.4.3. Подпрограммы в качестве параметров....... 107
2.4.4. Подпрограммы в качестве результата....... ПО
2.4.5. Стандартные описания элементарных функций ... по
2.5. Предложения..................... Ц2
2.5.1. Предложения как формулы............ 112
2.5.2. Предложения без результата........... 115
2.5.3. Процедуры без результата............ Пб
2.5.4. Стандартные описания для ввода/вывода..... пд
2.5.5. Совместное и последовательное исполнение .... 120
2.6. Составные объекты................... 123
2.6.1. Структуры.................... 123
2.6.2. Сцепления структур............... 127
2.6.3. Массивы.................... 132
2.7. Операторы цикла.................... 134
2.7.1. Оператор цикла типа арифметической прогрессии . . 134
2.7.2. Оператор цикла типа
„пока"........... 1372.7.3. Оператор цикла общего .вида........... 138
2.8. Управление в программе................ 140
2.8.1. Помеченные точки программы и операторы перехода 140
2.8.2. Блок-схемы программ............... 143
2.8.3. Программная документация........... . 147
2.9. Примеры........................ 149
2.9.1. Квадратный корень из комплексного числа..... 149
2.9.2. Возведение в степень............... 150
2.9.3. Простые числа ................. 151
2.9.4. Ханойские башни ................ 152
2.9.5. Проблема ферзей................ . 154
2.9.6. Поиск и сортировка по дереву......... . 156
2.9.7. Внутренняя сортировка.............. 158
Глава 3. Машинно-ориентированные алгоритмические языки . . . . . . 162ч
••4
3.1.
Декомпозиция формул................. 163ч3.1.1. Перевод в
„трехадресную форму"......... 163^3.1.2. Перевод в
„одноадресную форму"......... 166^3.1.3. Условные переходы................ 171 Г,
3.1.4. Декомпозиция логических формул с помощью опера- >/ торов перехода .................. 174^
3.1.5. Декомпозиция подпрограмм............ 178
«3.2.
Адреса и ячейки.................... 18§Г3.2.1. Декомпозиция многомерных массивов....... IBS'*
3.2.2. Индекс-регистры................. 184f(
3.2.3. Адреса..................... 1
№3.2.3.1.
Представление примитивных объектов . . . 18»"3.2.3.2.
Представление имен............ 8^3.2.3.3. Представление массивов......... 9(1.
3.2.3.4. Представление структур.......... MR
3.2.4. Устранение описаний тождества.......... 9 И
3.2.4.1. Описание тождества для переменной ... SB Я
3.2.4.2. Описание тождества для константы .... 91И
3.2.5. Динамические аспекты адресации.......... 9Ш
3.2.6. Вопросы двоичного кодирования.......... НШ
3.3. Система команд . . , , .......,,.,.,.,,, (ЯН
3.3.1. Ассортимент команд............... 196
3.3.1.1. Арифметические команды......... 196
3.3.1.2. Команды индексной арифметики...... 197
3.3.1.3. Команды передачи управления...... 198
3.3.2. Ячейки-команды.................. 198
3.3.3. Структура вычислительной машины и ход процессов 199
Глава 4. Переключательные сети и переключательные схемы...... 203
4.1. Переключательные переменные и переключательные функции ........................... 203
4.1.1. Теорема Буля о нормальной форме........ 204
4.1.2. Алгебра переключательных функций ........ 207
4.1.3. Переключательные сети.............. 209
4.1.4. Техническая реализация переключательных сетей . . 213
4.2. Переключательные схемы................ 214
4.2.1. Задержки..................... 215
4.2.2. Обратная связь с задержкой, переключательные схемы с задержками................. 216
4.2.3. Триггеры.................... 220
4.2.4. Переключательные схемы на триггерах . ...... 221
4.2.5. Техническая реализация переключательных схем . . 223
4.3. Основные составные части цифровых вычислительных машин 224
4.3.1. Исполнительные устройства............. 224
4.3.2. Управляющие устройства............. 227
4.3.3. (Оперативное) запоминающее устройство..... 231
4.3.4. Технологические границы............. 231
Глава 5. Динамическое распределение памяти............. 235
5.1. Блоки и распределение памяти.............. 235
5.1.1. Магазинное распределение памяти......... 238
5.1.2. Область существования имен как объектов..... 241
5.1.3. Операторы перехода и блочная структура..... 242
5.1.4. Декомпозиция операторов цикла......... 243
5.1.5. Массивы с динамически устанавливаемыми индексными границами................. 243
5.1.5.1. Недостатки ранее введенных описаний массивов.................... 243
5.1.5.2. Динамическое описание массива...... 244
5.1.6. Относительная адресация............. 246
5.1.7. Относительная адресация массивов........ 248
5.1.8. Один пример распределения памяти........ 250
5.2. Процедуры и блочная структура............ 256
5.2.1. Отказ от наивной концепции копирования и вставки 257
5.2.2. Рекурсивные процедуры.............. 259
5.2.3. Распределение памяти с учетом процедур..... 261
5.2.4. Динамические и статические цепочки ссылок .... 264
5.2.5. Механизм вызова процедур ............ 267
5.3. Распределение памяти в куче.............. 271
5.3.1. Распределение памяти для переменных-структур . . 271
5.3.2. Распределение памяти для объектов, имеющих лишь генерируемые имена (анонимных объектов) .... 272
5.3.3. Сборка мусора.................. 276
i лава о. внешняя память и связь с внешним миром, основные системные
программы......................... 271
6.1. Внешняя память, устройства ввода/вывода и каналы . . . 27J
6.1.1. Технические характеристики устройств...... 27?
6.1.1.1. Память с прямым доступом........ 27J
6.1.1.2. Память с непрямым доступом....... 27?
6.1.1.3. Единицы передачи и обмена........ 284
6.1.2. Взаимодействие периферийных устройств и центрального блока обработки ............... 284
6.1.2.1. Машинные конфигурации......... 285
6.1.2.2. Процессоры ввода/вывода и каналы .... 285
6.1.2.3. Привилегированные команды и программные прерывания................... 289
6.2. Организация данных и функциональный ввод/вывод . . . 292
6.2.1. Организация данных............... 293
6.2.1.1. Составные объекты и селекторы...... 293
6.2.1.2. Типы структур данных . .........
6.2.1.3. Реализация структур данных в однородной памяти ................. 298
6.2.1.4. Каталоги фондов............. 302
6.2.1.5. Права доступа.............. 303
6.2.2. Организация данных в памяти с непрямым доступом 304
6.2.2.1. Фонды во внешней памяти........ 304
6.2.2.2. Доступ к фондам во внешней памяти .... 305
6.2.2.3. Фонды на медленных устройствах ввода/вывода ................... 306
6.2.3. Функциональный ввод/вывод........... 307
6.2.3.1. Доступ к записям............. 308
6.2.3.2. Доступ к фондам............. 311
6.2.3.3. Наглядный ввод/вывод . . ..."..... 312
6.3. Операционные системы............; . . . 314
6.3.1. Последовательные процессы и мультипрограммный
режим...................... 316
6.3.1.1. Связь процессов между собой и синхронизация
процессов ................ 318
6.3.2. Управление ресурсами.............. 321
6.3.2.1. Распределение процессорного времени . . . 322
6.3.2.2. Обмен.................. 322
6.3.2.3. Управление оперативной памятью..... 323
6.3.2.4. Управление внешней памятью....... 328
6.3.3. Режимы эксплуатации системы и системные цели . . 330
6.3.4. Управление системой и командные языки систем . . . 332 6.4. Транслятор и другие служебные программы....... 334
Глава 7. Автоматы и формальные языки............... 337
7.1. Автоматы....................... 337
7.1.1. Автоматы и полугруппы.............. 337
7.1.2. Полугруппа, индуцированная автоматом...... 339
7.1.3. Свойства автоматов и некоторые простые теоремы . . 342
7.1.4. Автоматы с выходом............... 344
7.1.5. Язык, допускаемый автоматом.......... 345
7.2. Формальные языки................... 348
7.2.1. Формальные системы............... 348
7.2.2. Полутуэвские языки............... 352
7.2.3. Языки Хомского................. 355,
7.2.4. Неоднозначность................. 5fn^
7.2.5. Дерево разбора в линейном представлении..... 362^
7.3. Проблема грамматического разбора........., . 364
7.3.1. Беступиковые грамматики и определяемые ими последовательные алгоритмы грамматического разбора . . 364
7.3.2. Обеспечение беступиковости при помощи контекстных условий................... 369
7.3.3. Регулярные грамматики............. 370
7.3.4. Автоматы с магазинной памятью......... 372
7.3.5. Операторные грамматики и грамматики старшинства 374
7.4. Подстановки...................... 377
7.5. Описание автоматов и формальных языков....... 378
7.5.1. Формальное описание (автоматов и) формальных языков ....................... 379
7.5.2. Одна коллекция возможностей описания . . . . i 379
7.5.2.1. Словесное описание............ 379
7.5.2.2. Описание при помощи грамматики Хомского 380
7.5.2.3. Описание при помощи таблицы переходов автоматов................ 380
7.5.2.4. Описание при помощи диаграммы переходов автомата................. 380
7.5.2.5. Описание при помощи переключательной схемы ................... 380
7.5.2.6. Описание при помощи
„регулярного выражения" ................... 3817.5.2.7. Описание при помощи дерева разбора . . . 381
7.5.2.8. Описание при помощи бесскобочного регулярного выражения ............. 382
7.5.2.9. Описание при помощи дерева Канторовича 282
7.5.2.10. Описание при помощи программы .... 382
7.5.2.11. Описание при помощи блок-схемы программы 383
7.5.2.12. Описание при помощи алгоритма Маркова 383
Глава 8. Синтаксис и семантика алгоритмических языков...... 385
8.1. Синтаксис алгоритмических языков........... 386
8.1.1. Формы синтаксического описания......... 386
8.1.2. Синтаксическая классификация.......... 387
8.2. Семантика....................... 390
8.2.1. Требование смысловой однозначности синтаксиса . . 390
8.2.2. Операционная семантика............. 391
8.2.3. Семантика по Маккарти.............. 392
8.2.4. Семантика по Флойду и Хоару.......... 395
8.2.5. Перспективы................... 398
8.3. Трансляция алгоритмических языков в машинные языки . . 399
8.3.1. Структура транслятора.............. 399
8.3.2. Автоматизация разработки трансляторов . ..... 401
8.4. Языки программирования............... 402
8.4.1. Границы между синтаксисом, семантикой и прагматикой . . .................... 403
8.4.2. Оценка языков программирования, проектные критерии...................... 403
8.4.3. Характеристика некоторых распространенных языков программирования................ 405
8.4.3.1. Алгол 68................ 405
8.4.3.2. Алгол 60................. 407
8.4.3.3. Паскаль................. 411
8.4.3.4. Симула................. 414
Приложение А. Системы счисления................. 418
А.1. Позиционные системы счисления и перевод целых чисел из одной системы счисления в другую.............. 418
А.2. Представление отрицательных чисел............ 420
А.З. Четыре основные арифметические операции........ 421
А.4. Числа с плавающей запятой............... 423
А.5. Операции над числами с плавающей запятой........ 423
Приложение В. Устройства ввода/вывода данных.......... 425
8.1. Требования и возможности................ 425
8.2. Вывод.......................... 426
8.2.1. Устройства посимвольной печати........... 426
8.2.2. Устройства построчной печати............ 427
8.2.3. Графические устройства............... 429
8.2.4. Экранные устройства................ 430
8.2.5. Речевой вывод................... 431
8.3. Ввод........................... 432
8.3.1. Клавиатуры.................... 432
8.3.2. Точечный ввод с дисплея............. 433
8.3.3. Перфокарты и перфоленты, устройства считывания маркировок ...................... 434
8.3.4. Устройства считывания со стандартных формуляров . . 434
Приложение С. К истории информатики .............. 437
С.1. Введение......................... 437
С.1.1. Лейбниц...................... 438
С. 1.2. Корни информатики................. 439
С.2. История цифровых и символьных, вычислений........ 440
С.2.1. Цифровые вычисления................ 440
С.2.1.1. Механизация вычислений.......... 440
С.2.1.2. Вычисления в двоичной системе счисления . . 442
С.2.1.3. Вычисления над числами с плавающей запятой 443
С.2.2. Символьные вычисления............... 444
С.2.2.1. Криптография................ 445
С.2.2.2.
„Искусственный интеллект"......... 447С.2.2.3. Логическое исчисление............ 449
С.З. История связи...................... 450
С.3.1. Передача сообщений................. 450
С.3.2. Принцип двоичного кодирования.......... 451
С.3.3. Теория кодирования и теория информации, теория экстраполяции.................... 452
С.3.4. Регулирование................... 453
С.4. Автоматы и алгоритмы................... 454
С.4.1. Принцип автомата................. 454
С.4.2. Программное управление.............. 455
С.4.3. Алгоритмы..................... 456
С.4.4. Алгоритмические языки............... 457
С.4.5. Рекурсивность.................... 458
Список литературы......................... 460
Указатель ...,...,.....,............... 464
