Сохранность книги — хорошая

INFORMATIK
Eine einführende Übersicht

FRIEDRICH L. BAUER
ord. Professor der Mathematik und Informatik
an der Technischen Universität München

GERHARD GOOS
ord. Professor der Informatik
an der Universität Karlsruhe (TH)

Springer-Verlag
1973, 1974

Пер. с нем. В. К. Сабельфельда под редакцией А. П. Ершова

Формат 60x90 1/16. Бумага типографская №2

Книга представляет собой вводный курс по методам программирования на ЭВМ. В ней вскрываются связи между информатикой и смежными дисциплинами, а также между её отдельными разделами. Исходя из фундаментальных понятий программирования, которые вводятся на основе языка Алгол 68, излагается широкий круг вопросов, связанных с трансляцией, функциональной структурой ЭВМ, операционными системами, синтаксисом и семантикой языков программирования.

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

Авторы книги в самом начале своего предисловия расшифровывают содержание понятия Informatik, взятого ими для названия их труда… И хотя переводчик и редактор согласны с авторами в выборе названия, сохранение его в русском переводе требует некоторого пояснения.

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

Можно было бы и не тратить слов на объяснение перевода названия, если бы не «перехват» термина, осуществлённый лет десять назад специалистами по документалистике и информационно-поисковым системам. Редактор имеет в виду книгу А. И. Михайлова и А. И. Черного «Основы информатики» (Наука, М., 1968), в которой описываются методы существенно более узкой области применения ЭВМ. Впрочем, хотя указанная книга и получила довольно широкое распространение, в последующих работах употребление слова «информатика» в этом, более узком смысле, было не столь частым. В связи с этим переводчик и редактор сочли более полезным последовать существующей традиции сохранять при переводе научные термины, основанные на латинских словах, ограничиваясь их транслитерацией в алфавит национального языка.

Итак, перед нами вводный курс информатики. Это, по-видимому, первый в нашей литературе пример учебника «второго поколения», заметно отличающегося от известных у нас книг, таких, как, например, «Курс программирования» Е. А. Жоголева и Н. П. Трифонова (Наука, М., 1971), «Программирование и использование цифровых вычислительных машин» Р. Ледли (Мир, М., 1966).

Отличительной особенностью «Информатики» является в целом удавшаяся попытка авторов преподавать основы программирования и обработки информации как курс, излагающий сложившиеся концепции и понятия (прежде всего связанные с современными алгоритмическими языками), которые затем, с одной стороны, формализуются в некотором математическом аппарате и, с другой стороны, раскрываются в виде конструкций некоторого обобщённого машинного языка. Это очень серьёзное методологическое новшество, полностью отвечающее насущной потребности «самоопределения» информатики и идентификации её основных понятий. Авторы книги с присущей им скромностью ссылаются на некоторых специалистов, провозгласивших концептуальный подход в преподавании информатики, однако справедливости ради следует отметить, что, пожалуй, именно в «Информатике» указанный подход получил своё наиболее достоверное и успешное развитие. За четыре года этот учебник выдержал в ФРГ два издания и несколько перепечаток и стал основным вводным курсом по информатике в ряде стран. [И первое, и второе немецкое издание, с которого делался перевод, выходили в двух частях (в каждой части по четыре главы), с отдельными предисловиями и посвящениями. В настоящем издании было сочтено целесообразным объединить обе части в одной книге. Специально для русского издания авторы подготовили общее единое предисловие к книге.]

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

Язык оригинала «Информатики» возрождает давно сложившиеся традиции добротной немецкой научной прозы. Стиль авторов в значительной степени сохранён в отличном переводе В. К. Сабельфельда. Редактору показалось полезным предупредить об этом читателя, поскольку в нашей переводной литературе по вычислительному делу до последнего времени доминировала американо-английская стилистика, во многом отличающаяся от европейских традиций.

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

ПРЕДИСЛОВИЕ РЕДАКТОРА ПЕРЕВОДА
А. П. Ершов
Новосибирск, Академгородок
апрель 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. Подпрограммы	100
2.4.1. Подпрограмма без параметров	101
2.4.2. Подпрограммы с параметрами	103
2.4.3. Подпрограммы в качестве параметров	107
2.4.4. Подпрограммы в качестве результата	110
2.4.5. Стандартные описания элементарных функций	110
2.5. Предложения	112
2.5.1. Предложения как формулы	112
2.5.2. Предложения без результата	115
2.5.3. Процедуры без результата	116
2.5.4. Стандартные описания для ввода/вывода	119
2.5.5. Совместное и последовательное исполнение	120
2.6. Составные объекты	123
2.6.1. Структуры	123
2.6.2. Сцепления структур	127
2.6.3. Массивы	132
2.7. Операторы цикла
2.7.1. Оператор цикла типа арифметической прогрессии	134
2.7.2. Оператор цикла типа «пока»	137
2.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

3.1. Декомпозиция формул	163
3.1.1. Перевод в «трёхадресную форму»	163
3.1.2. Перевод в «одноадресную форму»	166
3.1.3. Условные переходы	171
3.1.4. Декомпозиция логических формул с помощью операторов
перехода	174
3.1.5. Декомпозиция подпрограмм	175
3.2. Адреса и ячейки	183
3.2.1. Декомпозиция многомерных массивов	183
3.2.2. Индекс-регистры	184
3.2.3. Адреса	186
3.2.3.1. Представление примитивных объектов	188
3.2.3.2. Представление имен	189
3.2.3.3. Представление массивов	190
3.2.3.4. Представление структур	190
3.2.4. Устранение описаний тождества	191
3.2.4.1. Описание тождества для переменной	191
3.2.4.2. Описание тождества для константы	192
3.2.5. Динамические аспекты адресации	192
3.2.6. Вопросы двоичного кодирования	194
3.3. Система команд	196
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

Глава 6. Внешняя память и связь с внешним миром,
основные системные программы	278

6.1. Внешняя память, устройства ввода/вывода и каналы	279
6.1.1. Технические характеристики устройств	279
6.1.1.1. Память с прямым доступом	279
6.1.1.2. Память с непрямым доступом	279
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. Типы структур данных	296
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. Неоднозначность	359
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. Одна коллекция возможностей описания	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. Описание при помощи «регулярного выражения»	381
7.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

Книги на ту же тему

Структурное программирование, Дал У., Дейкстра Э., Хоор К., 1975
Введение в теоретическое программирование (беседы о методе), Ершов А. П., 1977
История информатики в России: учёные и их школы, Захаров В. Н., Подловченко Р. И., Фет Я. И., сост., 2003
Сравнительное изучение языков программирования, Хигман Б., 1974
Определение языков программирования интерпретирующими автоматами, Оллонгрен А., 1977
Трансляция языков программирования, Вайнгартен Ф., 1977
Моделирование семантики в базах данных, Цаленко М. Ш., 1989
Математическая логика в программировании: Сборник статей 1980—1988 гг., Захарьящев М. В., Янов Ю. И., ред., 1991
Универсальные языки программирования. Семантический подход, Калинин А. Г., Мацкевич И. В., 1991
Алгебра. Языки программирования. — 2-е изд., перераб., Глушков В. М., Цейтлин Г. Е., Ющенко Е. Л., 1978
Языки программирования. Концепции и принципы, Кауфман B. Ш., 1993
Системное программирование: Учебное пособие для втузов, Дьяконов В. Ю., Китов В. А., Калинчев И. А., 1990
Сборник задач по программированию. — 2-е изд., перераб., Бухтияров А. М., Зикевская Л. М., Фролов Г. Д., 1970
Сравнительный курс языка PL/1 (на основе алгола-60), Безбородов Ю. М., 1980
Проблемы прикладной математики и информатики, Белоцерковский О. М., ред., 1987
Элементы программирования, Гнеденко Б. В., Королюк В. С., Ющенко Е. Л., 1961
Программирование и алгоритмические языки, Криницкий Н. А., Миронов Г. А., Фролов Г. Д., 1975
Введение в программирование в содержательных обозначениях, Брудно А. Л., 1965
Элементы программирования, Абрамов С. А., 1982

elapsed time 0.023 sec

/ИТ-книги

ОГЛАВЛЕНИЕ

Книги на ту же тему