Б 29 Информатика. Вводный курс: В 2-х ч. 4.1. Пер. с нем.— М.: Мир, 1990.— 336 с., ил.
ISBN 5-03-002099-3
Учебный курс, представляющий собой перевод с 3-го, полностью переработанного и расширенного издания, написанного известными специалистами (ФРГ). (Второе немецкое издание было переведено на русский (М.: Мир, 1976).) Изложение отличается глубокой методической проработанностью материала и применением концептуального подхода к преподаванию основ информатики. Фундаментальные понятия программирования вводятся в книге как исходные, получают затем формализацию и раскрываются в виде конструкций языков программирования разного уровня. Много содержательных и изящных примеров решения конкретных задач с использованием алгола-68 и паскаля.
В ч. 1 входят предисловия и гл. 1—4.
Для студентов, изучающих программирование, научных работников различных специальностей, использующих ЭВМ в своей работе.
Предисловие к русскому изданию
Это второе издание „Информатики" представляет собой перевод уже третьего немецкого издания, практически полностью переработанного профессором Ф. Л. Бауэром с учётом прогресса, достигнутого в программировании за последние годы.
Учебник Ф. Л. Бауэра и Г. Гооза пользуется большой популярностью в странах, говорящих по-немецки. Первое русское издание книги (М.: Мир, 1976) получило признание и у советского читателя. Успех учебника объясняется, по-видимому, тем, что авторы одними из первых удачно применили концептуальный подход в преподавании основ программирования. Фундаментальные понятия информатики вводятся в книге как исходные, а не как производные тех функций, которые реализуются теми или иными вычислительными устройствами. Другая принципиальная особенность курса, отличающая его от традиционных учебников по программированию, тесно связана с пропагандируемым авторами трансформационным стилем программирования.
Сегодня уже многие сознают, что преподавание основ программирования не должно ограничиваться только тем, чтобы обучать синтаксису и семантике одного или нескольких языков программирования. Вместе с освоением языковых конструкций обучаемый должен получить первые навыки разработки программ, которую авторы с полным на то основанием трактуют как процесс систематического и вполне познаваемого перехода от неалгоритмической постановки задачи к эффективной программе для её решения. Методология такого систематического перехода излагается в третьей главе нового издания.
Много внимания в новом издании уделено технике рекурсивного программирования, вовсе не затрагивавшейся в предыдущих изданиях. Во второй главе изложены основные .принципы функционального стиля программирования, получившего в последние годы широкое распространение; здесь же на содержательных примерах демонстрируются изящные рекурсивные формулировки для решения конкретных задач.
Удачной методической находкой следует считать описанную во второй главе ,,машину обработки формуляров", представляющую собой весьма поостую абстрактную модель исполнителя рекурсивных программ. Формуляр — это обобщение понятия
о Предисловие к русскому изданию
формулы, имеющее наглядное графическое представление, так что понятия, связанные с разными способами выполнения рекурсивных программ, оказываются представленными на страницах книги в „живых" картинках — при помощи таких наглядных процессов, как копирование картинок, их соединение друг с другом, заполнение граф в формулярах.
Среди других новых понятий, появившихся и подробно обсуждаемых в новом издании, особо следует отметить понятие вычислительной структуры, представляющее собой по сути дела конкретизацию понятия абстрактного типа данных. Как работает это относительно новое для практики программирования понятие, показано в книге на многочисленных примерах конкретных вычислительных структур, а также при описании способов конструирования сложных вычислительных структур из более простых.
В отличие от первого русского издания во втором была использована авторская версия языка алгол-68, без перевода служебных слов с английского на русский. Такое решение было< принято с целью избежать разнобоя: в новом издании примеры программ приводится не только на алголе-68, но и на паскале, для которого русской версии вообще нет; кроме того, русская версия алгола-68 (см. [05]) не получила, к сожалению, широкого распространения.
Важно, что книга хорошо стыкуется с введённым сейчас в нашей средней школе курсом основ информатики и вычислительной техники. Поэтому хочется надеяться, что переиздание „Информатики" будет способствовать наметившимся положительным сдвигам в перестройке нашей системы образования, в какой-то степени поможет решить задачу повышения качества подготовки специалистов по применению вычислительной техники.
* * *
Каждое из трёх немецких изданий выходило в двух частях, с небольшим временным разрывом между первой и второй и с отдельными предисловиями к каждой части. Это издание готовилось в одном томе. Поэтому мы собрали все предисловия вместе в начале книги. Однако по техническим причинам на стадии корректуры нам всё-таки пришлось тоже разбить книгу на две части. Отсюда сплошная нумерация страниц в частях.
Перевод предисловий, приложений и глав 1, 3, 5 выполнен В. К. Сабельфельдом, глав 2, 4 и 6 — В. Г. Кербелем, глав 7 и 8 — М. К. Валиевым.
| А. П. Ершов В. К. Сабельфельд
От переводчиков
Инициатором обоих русских изданий был академик А. П. Ершов. Второе издание стало возможным во многом благодаря именно его усилиям. Учёный с мировым именем, А. П. Ершов внёс значительный и определяющий вклад в становление информатики в СССР. Недавняя смерть А. П. Ершова глубоко поразила нас. Мы посвящаем наш перевод его памяти.
М. Валиев
В. Кербель
В. Сабельфельд
Оглавление
Предисловие к русскому изданию................ 5
От переводчиков...................... 7
Из предисловия к первому изданию части 1........... 8
Из предисловия к первому изданию части 2........... 9
Предисловие ко второму изданию части 1............ 9
Предисловие ко второму изданию части 2............ 10
предисловие к третьему изданию части 1............ 10
Предисловие к третьему изданию части 2............ 13
Вступление........................ 16
Глава 1. Информация и сообщение •.......... 18
1.1. Сообщение и информация............. 18
1.1.1. Языковые сообщения.............21
1.1.2. Письмо.................. 23
1.2. Органы чувств................. 24
1.2.1. Работа органов чувств, проведение возбуждения . . 24
1.2.2. Обработка раздражения в мозге ........ 28
1.2.3. Значение информационных представлений . ... 35
1.3. Устройства связи................ 36
1.3.1. Типы устройств связи............ 36
1.3.2. Сигналы и параметры сигналов........ 39
1.4. Дискретные сообщения.............. 40
1.4.1. Знаки, наборы знаков, алфавиты........ 40
1.4.2. Коды и кодирования . . . ........ 51
1.4.3. Последовательная и параллельная передача ... 60
1.4.4. Символы................. 62
1.5. Обработка сообщений и обработка информации .... 62
1.5.1. Обработка сообщений как кодирование..... 62
1.5.2. Интерпретация обработки сообщений...... 64
1.6. Алгоритмы.................. 66
1.6.1. Характеристические свойства алгоритмов..... 67
1.6.2. Примеры алгоритмов............ 68
1.6.3. Рекурсия и итерация............ 71
1.6.4. Специальные формы описания алгоритмов .... 72
1.6.4.1. Пример: алгоритмы Маркова...... 73
1.6.4.2. Рекурсивные алгоритмы по Маккарти ... 75
Тлава 2, Основные понятия программирования...... 77
2.1. Основные вычислительные структуры........ 79
2.1.1. Объекты................. 79
Оглавление V
2.1.1.1. Сорта объектов........ . . . 791
2.1.1.2. Стандартные обозначения объектов .... 82
2.1.2. Операции............... 84
2.1.3. Вычислительные структуры......... 86<
2.1.3.1. Вычислительная структура Z целых чисел 87
2.1.3.2. Вычислительная структура N натуральных чисел................ 90'
2.1.3.3. Вычислительные структуры для вычислений с рациональными, вещественными и комплексными числами.......... 91
2.1.3.4. Вычислительные структуры для нечисловых вычислений: последовательности знаков . . 93
2.1.3.5. Вычислительные структуры для нечисловых вычислений: размеченные бинарные деревья 96
2.1.3.6. Вычислительная структура (Вз значений истинности .............. 99'
2.1.3.7. Переходы между сортами........ 101
2.1.3.8. Составные объекты.......... 103
2.2. Формулы................... 103
2.2.1. Обозначения параметров........... 103
2.2.2. Формулы и формуляры........... 105
2.2.2.1. Построение формул.......... 105
2.2.2.2. Формуляры............,109
2.2.2.3. Строгость операций.......... 114
2.2.2.4. Преобразование формул........ 115
2.2.3. Условные формулы............. 117
2.2.3.1. Альтернатива и последовательный разбор случаев...... ....... 117
2.2.3.2. Охраняемый разбор случаев....... 120
2.2.3.3. Проведение вычислений на формулярах
с разбором случаев .......... 122
2.2.3.4. Нестрогий характер разбора случаев . . .124
2.3. Подпрограммы................. 125
2.3.1. Описание подпрограмм........... 125
2.3.1.1. Нотация.............. 125
2.3.1.2. Системы подпрограмм......... 127
2.3.1.3. Предохранители . ......... 128
2.3.1.4. Связанные обозначения........ 129
2.3.2. Рекурсия................ 129
2.3.3. Рекурсивная машина обработки формуляров . . . 138 2.4 О технике рекурсивного программирования...... 144
2.4.1. Как приходят к рекурсивным подпрограммам? . . 144
2.4.1.1. Органически рекурсивные определения . .144
2.4.1.2. Извлечение рекурсии из постановки задачи 144
2.4.1.3. Вложение.............. 145
2.4.1.4. Метод родственных задач...... . 148
2.4.1.5. Использование характеристических свойств . 149 '2.4.1.6 Обращение............. 151
2.4.2 Как доказывать свойства алгоритмов? . . . 153 2.43 Некоторые замечания об окончании и о роли предохранителей и стражей.......... 155
2.4.3.1................... 155
2.4.3.2.................. 155
2.4.3.3................... 156
24.34................... 15&
2.4.3.5................... 157
2.5. Подчинение подпрограмм............. (57
2.5.1. Подчинённые подпрограммы......... 157
2.5.2. Подавленные параметры........... 159
2.5.2.1. Глобальные и нелокальные параметры . . . 159
2.5.2.2. Экранирование........... . 161
2.5.2.3. Неподвижные параметры....... 162
2.5.3. Подпрограммы, свободные от параметров . . . . 163
2.6. Подпрограммы в качестве параметров и в качестве результатов................... 164
2.6.1. Подпрограммы в качестве параметров...... 164
2.6.2. Задержанные вычисления, осуществляемые посредством использования подпрограмм, свободных от параметров, в качестве параметра...... 166
2.6.3. Подпрограммы в качестве результата...... 168
Глава 3. Машинно-ориентированные алгоритмические языки 170
3.1. Предложения общего вида............171
3.1.1. Описания промежуточных результатов.....171
3.1.1.1. Упрощённая нотация.........173
3.1.1.2. Обозначения промежуточных результатов
в рекурсивных подпрограммах ..... 176
3.1.1.3. Линеаризация хода вычислений..... 180
3.1.1.4. Замечание относительно паскаля.....
3.1.2. Групповые описания промежуточных результатов , 180
3.2. Программирование с переменными......., 182
3.2.1. Повторно используемые обозначения промежуточных результатов..............182
3.2.2. Описания и присваивания ..........183
3.2.3. Неизменные переменные...........184
3.2.4. Операторы................185
3.2.5. Примеры.................186
3.2.6. Групповые описания переменных и групповые присваивания.................187
3.3. Итеративное программирование..........188
3.3.1. Повторительные программы с точки зрения итерации 188
3.3.2. Повторение................192
3.3.2.1. Итеративные программы........ 194
3.3.2.2. Иерархические повторительные системы и вложенные циклы...........197
3.3.2.3. Диаграммы Насси — Шнейдермана .... 199
3.3.3. Решение задач с помощью итеративных форм . . . 200
3.3.3.1...................201
3.3.3.2...................201
3333 ..............202
3.3.3.4...................203
3.3.4. Линеаризация..............204
3.3.5. Условные операторы . . ..........206
3.3.5.1. Операторы альтернативы........207
3.3.5.2. Последовательные условные операторы . . 209
3.3.5.3. Охраняемые операторы ........ . 211
3.3.6. Пустой оператор............. 212
3.4. Операторы перехода............. 214
3.4.1. Гладкие вызовы и операторы перехода .... 214
3.4.2. Реализация повторения при помощи переходов . . 218
3.4.2.1...................218
3.4.2.2...................218
3.4.2.3...................219
3.4.3. Блок-схемы программ............220i
3.4.3.1...................220
3.4.3.2...................223
3.4.3.3...................227
3.5. Процедуры..................227
3.5.1. Параметры-переменные...........228
3.5.2. Описания процедур.............229
3.5.3. Вызовы процедур............. 231
3.5.3.1...................232
3.5.3.2..................232
3.5.4. Транзитные параметры и параметры-результаты . . 233
3.5.5. Входные параметры.............235
3.5.6. Подавляемые параметры .... .....236
3.5.7. Процедуры как средство структурирования .... 237
3.5.8. Рекурсивное определение повторения......239
3.5.8.1. Переход как гладкий вызов процедуры без параметров.............239i
3.5.8.2. Рекурсивное определение условного повторения ...............239
3.5.8.3. Рекурсивное определение повторения с пересчётом ..............2401
3.6, Массивы...................242
3.6.1. Индексированные переменные.........243
3.6.1.1................... 244
3.6.1.2...................245
3.6.2. Многомерные массивы...........249>
3.6.2.1...................249-
3.6.2.2..................250
3.6.2.3..................251
3.6.3. Сведение многомерных массивов к одномерным . . 251
3.6.4. Статическое распределение памяти.......253
3.6.4.1...................253
3.6.4.2...................254
3.6.4.3...................255-
3.7 Декомпозиция формул..............255-
3.7.1. Декомпозиция по принципу магазина......25&
3.7.2. Использование магазина промежуточных результатов..................259-
3.7.3. Перевод в трёхадресную форму........260
3.7.4. Перевод в одноадресную форму........263;
3.7.5. Границы применимости принципа магазина . . . 266.
3.7.6. Обработка разбора случаев.........266-
3.7.7. Исключение логических операций........269'
Глава 4. Двоичные комбинационные и переключательные
схемы . . •............... 271
4.1. Булева алгебра.................271
4.1.1. Абстрактное определение булевой алгебры ... 271
4. .1.1................... 271
4. .1.2......... ....... 272-
4. .1.3................... 273
4. .1.4................. 274
4. .1.5................... 275
4.1.2. Теорема о булевой нормальной форме...... 276>
4.1.3. Отношение порядка в булевой алгебре. Импликация 279 4.1.3.1. Отношение „сильнее"..........279'
4.1.3.2. Отношение „сильнее" на булевых функциях 280
4.1.3.3. Отношение порядка между булевыми выражениями ..............281
4.1.3.4. Приложения к высказываниям и предикатам 281
4.1.4. Таблицы решений..............284
4.1.4.1. Совместные таблицы решений......284
4.1.4.2. Последовательные таблицы решений .... 287
4.1.5. Переключательные функции..........289
4.1.5.1. Символические изображения переключательных функций.............290
4.1.5.2. Соединение символических изображений . . 291
4.1.5.3. Пример: полусумматор, полный сумматор . 292
4.1.5.4. Пример: перекодировщики.......293
4.1.6. Техническая реализация комбинационных схем . . 294
4.2. Двоичное кодирование..............295
4.2.1. Двоичное сравнение.............296
4.2.2. Двоичная арифметика............297
4.2.2.1. Двоичный счётчик...........297
4.2.2.2. Сложение и вычитание.........299
4.2.2.3. Умножение.............301
4.2.2.4. Операции с двоично представленными последовательностями знаков и размеченными деревьями .......... .... 302
4.2.3. Арифметика с ограниченным числом разрядов . . 303
4.3. Переключательные схемы.............306
4.3.1. Переменные памяти для двоичных слов.....307
4.3.1.1. Пример: сложение...........307
4.3.1.2. Двоичные регистры и элементы задержки . . 309
4.3.1.3. Присоединение элементов задержки к логическим элементам...........310
4.3.2. Построение переключательных схем......311
4.3.2.1. Последовательный и параллельный сумматоры ................311
4.3.2.2. Переключательная схема сдвига.....314
4.3.3. Триггеры.................315
4.3.4. Триггерные переключательные схемы......317
4.3.4.1. Триггерные переключательные схемы для арифметики.............318
4.3.4.2. Триггерные переключательные схемы для неарифметических операций ........ 320
4.3.5. Техническая реализация переключательных схем . 321
4.4. Успехи и предельные возможности технологии.....322
Содержание части 2.................... I
Цена: 250руб.
