Бауэр Ф.Л., Гооз Г. Информатика. Том 1

Подождите немного. Документ загружается.

Информатика

HEIDELBERGER TASCHENBOCHER

SAMMLUNG INFORMATIK

Herausgegeben von F. L. Bauer, G. Goos und M Pajl

Band 80 | Band 91

•

INFORMATIK

Eine einfiihrende Cbersicht

FRIEDRICH L. BAUER

ord. Professor der Mathematik und Informatik

an der Technischen Universitat Miinchen

GERHARD GOOS

ord. Professor der Informatik

an der Universitat Karlsruhe (TH) ,

Erster Teil

Kapitel 1—4

Zweiter Teil

Kapitel 5—8

Dritte Auflage

vollig neu bearbeitet und erweitert

von F. L. Bauer

Springer-Verlag

Berlin Heidelberg New York Tokyo

1982 I 1984

Ф.

Л. Бауэр, Г. Гооз

вводный курс

Второе,

полностью переработанное

расширенное издание

двух

частях

Часть 1

Перевод с немецкого

М. К. Валиева, В. Г. Кербеля

В. К. Сабельфельда

под редакцией

| А. П. Ершова

Москва

«Мир» 1990

ББК

22.19 +

32.97

Б 29

УДК

681.142.2

Бауэр Ф. Л., Гооз Г.

Б 29 Информатика. Вводный курс: В 2-х ч. 4.1. Пер. с нем.—

М.: Мир,

1990.—

336 с, ил.

ISBN

5-03-002099-3

Учебный курс, представляющий собой перевод с 3 го, полностью

переработанного и расширенного издания написанного известными спе-

циалистами (ФРГ) (Второе немецкое издание бьпо переведено на рус-

ский

(М Мир, 1976) ) Изложение отличается глубокой методической

проработанностью материала и применением концептуального подхода

преподаванию основ информатики Фундаментальные понятия про-

граммирования вводятся в книге как исходные, получают затем форма-

лизацию и раскрываются в виде конструкций языков программирова-

ния

разного уровня Много содержательных и изящных примеров

решения

конкретных задач с использованием алгола-68 и Паскаля

В ч 1 входят предисловия и гл. I—4.

Для студентов, изучающих программирование, научных работников

различных специальностей, использующих ЭВМ в своей работе.

ББК 22.,9+32.97

Редакция

литературы

по

математическим

наукам

ISBN

5-03-002099-3

1, . ©by

Spnnger-Verlag

Berbn Heidelberg

ISBN

5-03-000298-7

]*РУ

сск

1971, 1973, 1974, 1982 1984

ISBN

3-540-11722-9

1, , All Rights

Reserved

ISBN

3-540-13121-3

HeM

Authorized translation from German

language

edition published by Spr.n-

ger-Verlag

Berlin Heidelberg New

York

Tokyo

бельфельд М К Вачиев, В Г. Кер-

бель, 1990

Предисловие

русскому

изданию

Это второе издание „Информатики" представляет собой пе-

ревод уже третьего немецкого издания, практически полностью

переработанного профессором Ф. Л. Бауэром с

учётом

прогрес-

са, достигнутого в программировании за последние годы.

Учебник Ф. Л. Бауэра и Г. Гооза пользуется большой по-

пулярностью в странах, говорящих по-немецки. Первое русское

издание книги (М.: Мир, 1976) получило признание и у совет-

ского читателя.

Успех

учебника объясняется, по-видимому, тем,

что авторы одними из первых удачно применили концептуаль-

ный

подход

в преподавании основ программирования. Фунда-

ментальные понятия информатики вводятся в книге как исход-

ные,

а не как производные тех функций, которые реализуются

теми или иными вычислительными устройствами. Другая

прин-

ципиальная

особенность курса, отличающая его от традицион-

ных учебников по программированию, тесно связана с пропа-

гандируемым авторами трансформационным стилем программи-

рования.

Сегодня уже многие сознают, что преподавание основ про-

граммирования не должно ограничиваться только тем, чтобы

обучать

синтаксису и семантике одного или нескольких языков

программирования.

Вместе с освоением языковых конструкций

обучаемый должен получить первые навыки разработки про-

грамм, которую авторы с полным на то основанием

трактуют

как

процесс систематического и вполне познаваемого перехода

от неалгоритмической постановки задачи к эффективной про-

грамме для её решения Методология такого систематического

перехода излагается в третьей главе нового издания.

Много

внимания в новом издании уделено технике рекурсив-

ного программирования, вовсе не затрагивавшейся в предыду-

щих изданиях. Во второй главе изложены основные принципы

функционального

стиля программирования, получившего в по-

следние годы широкое распространение; здесь же на содержа-

тельных примерах демонстрируются изящные рекурсивные фор-

мулировки для решения конкретных задач.

Удачной методической находкой

следует

считать описанную

во второй главе „машину обработки формуляров", представ-

ляющую собой весьма ппостую абстрактную модель исполните-

ля

рекурсивных программ Формуляр — это обобщение понятия

6 Предисловие к русскому изданию

формулы, имеющее наглядное графическое представление, так

что понятия, связанные с разными способами выполнения ре-

курсивных программ, оказываются представленными на стра-

ницах книги в „живых" картинках — при помощи таких нагляд-

ных процессов, как копирование картинок, их соединение

друг

с другом, заполнение граф в формулярах.

Среди

других

новых понятий, появившихся и подробно об-

суждаемых

в новом издании, особо

следует

отметить понятие

вычислительной структуры, представляющее собой по сути дела

конкретизацию

понятия абстрактного типа данных. Как ра-

ботает это относительно новое для практики программирования

понятие,

показано в книге на многочисленных примерах кон-

кретных вычислительных структур, а также при описании спо-

собов конструирования сложных вычислительных

структур

и»

более простых.

В отличие от первого русского издания во втором была ис-

пользована авторская версия языка алгол-68, без перевода слу-

жебных слов с английского на русский. Такое решение было

принято

с целью избежать разнобоя: в новом издании примеры

программ приводится не только на алголе-68, но и на паскале,

для которого русской версии вообще нет; кроме того, русская

версия

алгола-68

(см. [05]) не получила, к сожалению, широкого

распространения.

Важно, что книга хорошо стыкуется с введённым сейчас в

нашей

средней школе курсом основ информатики и вычисли-

тельной техники. Поэтому хочется надеяться, что переиздание

„Информатики"

будет

способствовать наметившимся положи-

тельным сдвигам в перестройке нашей системы образования, в-

какой-то

степени поможет решить

задачу

повышения качества

подготовки специалистов по применению вычислительной тех-

ники.

* * *

Каждое из

трёх

немецких изданий выходило в

двух

частях,

с небольшим временным разрывом

между

первой и второй и с

отдельными предисловиями к каждой части. Это издание гото-

вилось в одном томе. Поэтому мы собрали все предисловия вме-

сте в начале книги. Однако по техническим причинам на стадии

корректуры нам всё-таки пришлось тоже разбить книгу на две

части. Отсюда сплошная нумерация страниц в частях.

Перевод предисловий, приложений и глав 1, 3, 5 выполнен

В К Сабельфельдом, глав 2, 4 и 6 — В. Г. Кербелем, глав 7

8 — М. К- Валиевым.

\ А. П.

Ершов

В. К.

Сабельфельд

От переводчиков

Инициатором

обоих русских изданий

был

академик

А.

П.

Ершов.

Второе

издание стало возможным

во

многом

бла-

годаря именно

его

усилиям. Учёный

мировым именем,

А.

П.

Ершов внёс значительный

определяющий вклад

в ста-

новление информатики

СССР.

Недавняя смерть

А. П.

Ершова

глубоко

поразила

нас. Мы

посвящаем

наш

перевод

его

памяти.

М.

Валиев

В.

Кербель

В.

Сабельфельд

Из

предисловия к первому изданию

части

Informatik

— это

немецкое название

для

computer science

—

области

знания,

которая сложилась

самостоятельную науч-

ную дисциплину

шестидесятые годы, прежде всего

в США,

а также

Великобритании.

последнее время изучение

инфор-

матики

в ФРГ

находится

на

быстром подъёме, чему

немалой

степени способствует Федеральное министерство образования

науки.

Данная книга представляет собой вводный курс

инфор-

матики,

который согласуется

рекомендациями обществ GAMM

NTG

. Она

может служить

качестве пособия

для

началь-

ного годового курса лекций.

Она и

возникла

из

таких лекций,

которые читались

на

отделении математики Мюнхенского

тех-

нического университета

с 1967

года

связи

введением

в уни-

верситете регулярного изучения информатики.

Изложение

построено

по

принципу

от

общего

частному.

Фундаментальные понятия программирования

мы

вводим

в ка-

честве исходных, вместо того чтобы,

как это

часто делают,

вы-

водить

их из

специальных функций машины. Преимущество

та-

кого способа изложения, освобождённого

от

случайностей

тех-

нического развития

и тем

самым позволяющего получать более

„жизнестойкие"

утверждения, нельзя считать незначительным;

ещё

большей степени,

как нам

кажется, этот способ оправда»

тем,

что мы

заставляем начинающего задумываться, вместо

того чтобы подавать

ему

готовые решения. Этот способ изло-

жения

недавно получил распространение

и в США (под

назва-

нием

top-down-teaching

), в

частности благодаря усилиям Элана

Перлиса.

Наконец, развитие языков программирования

в сто-

рону формализации семантики также нацелено

на то,

чтобы

шаг

за

шагом сводить сложное

простому.

Наряду

общим обзором информатики

книге вскры-

ваются связи

между

её

отдельными специальными разде-

лами.

В написание этой книги внесли конструктивный вклад наши

коллеги

К.

Замельзон,

П.

Пауль

и Ф

Пайшль. Первый вариант

рукописи подготовила

1967/68

учебном

году

г-жа Д.

Майзон.

При

разработке упражнений

лекциям, особенно

при

составле-

нии

задач,

нам

помогали

Р.

Гнац

и X.

Вальтер, последний

из

которых отредактировал также второй вариант курса

(1968/69

учебный

год).

Замельзон читал этот вводный курс

1969/70

учебном

году,

и мы

получили

от

него ценную критику. Кроме

того, полезные замечания

по

отдельным главам сделали

кол-

Буквально: компьютерная наука

(англ

) —

Прим

перев.

QAMM

—

общество прикладной математики

механики;

NTG—

обще-

ство техники связи.

—

Прим

перев

Обучение

сверху

вниз (англ.).

—

Прим.

перев.

Из

предисловия

первому изданию части

2 9

леги

И.

Айкель,

П.

Дойсен,

В. Хан и г-жа У.

Хилл. Первую

главу

просмотрели также коллеги

В.

Кайдель (Эрланген)

X. Цеманек (Вена).

Мы от

души благодарим

всех,

кто

сотруд-

ничал

нами,

у нас

просто

нет

возможности назвать

всех

по-

имённо.

Это

относится

не

только

секретаршам

сотрудникам,

помогавшим

нам при

чтении корректур.

Особо должны

мы

упомянуть

Вёснера, который проверил

алгольные примеры

на

синтаксическую правильность.

За

период,

когда старший

из

авторов'

был

председателем терминологиче-

ской

комиссии специального комитета

по

стандартизации обра-

ботки информации,

он

многое вынес

из

проводившихся

там дис-

куссий,

и ему

хочется выразить свою благодарность участникам

этих дискуссий.

В тяжёлые послевоенные годы

у нас, к

счастью, нашлись

три человека, обладавшие мужеством верить

возрождение

научной работы

новой

и до 1955

года

весьма ограниченно

раз-

вивавшейся области вычислительного дела.

Это —

Альвин Валь-

тер, Ганс Пилоти

Роберт Зауэр.

Им,

подготовившим появле-

ние

информатики

нашей стране, посвящена первая часть этой

книги.

Мюнхен, лето

1970 г. Ф. Л.

Бауэр,

Г. Гооз

Из

предисловия к первому изданию части 2

Эта вторая часть „Информатики" завершает

наш

ввод-

ный

курс.

Она

посвящена памяти Хайнца Рутисхаузера

(30.01.1918—10.11.1970).

Рутисхаузер

был

одним

из

первых,

кто осознал

использовал возможности цифровых вычислитель-

ных машин, выходящие

за

рамки числовых вычислений,

и тем

способствовал становлению информатики.

Мюнхен

Карлсруэ, весна

1971 г. Ф. Л.

Бауэр,

Г. Гооз

Предисловие

ко второму изданию части 1

В настоящем издании улучшены многие детали изложения.

Мы

получили многочисленные замечания относительно первого

издания

хотим выразить признательность всем

их

авторам.

Особая наша благодарность

— г-же д-ру X.

Фогг

за

неутомимую

помощь

при

переработке текста.

Мюнхен

Карлсруэ, весна

1973 г. Ф. Л.

Бауэр,

Г. Гооз

Ф. Л.

Бауэр.

—

Прим.

перев.

10 Предисловие

третьему

изданию части

Предисловие

ко второму изданию части 2

Во втором издании удалось улучшить многие детали изло-

жения.

связи

этим

мы

благодарим

всех,

высказавших

нам

свои отзывы

первом издании. Раздел

6.2 об

управлении

дан-

ными

изложен полностью заново,

включением

него мате-

риала прежнего раздела

6.1.3.

За

многочисленные критические

замечания,

касающиеся этого нового варианта изложения,

мы

признательны целому ряду коллег, особенно

П.

Локкеманну.

Наконец,

добавлены раздел

языке программирования паскаль

приложение

об

устройствах ввода/вывода данных.

Мюнхен

Карлсруэ, весна

1974 г. Ф. Л.

Бауэр,

Г.

Г003

Предисловие

к третьему изданию части 1

Ввиду

того взлёта достижений, который наблюдался

в ин-

форматике

за

двенадцать

лет,

прошедшие

момента

выход»

первого издания этой книги,

при

подготовке настоящего,,

третьего

её

издания

(31-я — 34-я

тысячи экземпляров) потре-

бовалась полная переработка текста.

Чисто внешне читателю, по-видимому, больше всего

бро-

сится

глаза

то

обстоятельство,

что

примеры программ запи-

саны

теперь

в два

столбца,

на

алголе-68

и на

паскале.

пользу

привлечения

языка паскаль говорило

не

только

его

широкое

распространение начиная

с 1975

года,

но и

прежде всего

то, что

он

удачно компенсирует некоторые недостатки алгола-68,

ска-

жем

части, касающейся

структур

данных;

другой

стороны,

спроектированный

не

зависящим

от

процесса перевода

алгол-68

некоторых местах имеет более прозрачную нотацию

—

хотя

из-за

своей явной вычурности

ряде областей

он

просто

не-

смог утвердиться.

Как уже

было

первом издании

алголом-68,.

так

здесь

паскалем

—

правда,

гораздо более скромных

масштабах

—

пришлось обрезать дикие заросли языковых укра-

шательств. Добавлять

же

пришлось,

по

существу,

только

неко-

торые конструкции

для

совместного исполнения.

В мирном сосуществовании

алгола-68

паскаля отражается,.

главным образом, перемена, происшедшая

семидесятых

годах

состоящая

формировании общего

абстрактного,

не

завися-

щего

от

используемой нотации базиса понятий

для

управляю-

щих

структур

и (с

некоторым отставанием)

для

структур

дан-

ных.

семантической точки зрения, исходя

из

этого базиса^

легко получить

как

алгол-68,

так и

паскаль

(и не

только

их),,

причём

при

таком

подходе

для

алгола-68

неизбежными оказы-

ваются некоторые нововведения (скажем, вычёркивание описа-