F.L. Bauer

herrschen. Bedeutsam ist auch die Abgrenzung der dritten Ebene, der Ebene der verselb- standigten Variablen und Zeiger. Der vergleichsweise geringe Umfang von Kap. 7 bedeutet einerseits, dass die Beschreibung sich auf Grundsatzliches beschrankt, dem sich viele aus der Literatur der Systemprogrammierung bekannte Einzelheiten unterordnen, beispiels- weise aus D. E. Knuth's, The Art of Computer Programming' oder G. Seegmullers, Ein- fuhrung in die Systemprogrammierung', andererseits aber auch, dass die Vervollstandi- gung der theoretischen Grundlagen noch aussteht. Zu den einzelnen Abschnitten dieses Buches gibt es einen Hintergrund unterschiedlich weit entwickelter mathematischer Theorien. Wichtige Grundbegriffe sind verbandstheore- tischer Natur. Die fundamentalen Arbeiten von D. Scott haben das eindrucksvoll bewie- sen. Bei den Rechenstrukturen des 3. Kapitels steht die moderne Theorie der universellen Algebra im Hintergrund, insbesondere Arbeiten von Birkhoff und Tarski sind hier von Be- deutung. Da wir kein mathematisches Lehrbuch vorlegen, mussen wir uns meistens mit Andeutungen und Hinweisen begnugen. Das Buch hat sich aus Vorlesungen und begleitenden UEbungen entwickelt, die in den letz- ten Jahren an der Technischen Universitat Munchen gehalten wurden. Es entstand in enger Wechselwirkung mit dem Projekt CIP ("Computer-aided Intuition-guided Programming") und dem Teilprojekt "Breitbandsprache und Programmtransformation" im Sonderfor- schungsbereich 49, Programmiertechnik, an der Technischen Universitat Munchen. Bei dem Versuch, fur ein einigermassen abgerundetes, geschlossenes Lehrgebaude der Programmie- rung die Fundamente zu legen, musste vieles fragmentarisch bleiben. In manchen Punkten war es notwendig, Positionen zu beziehen, die auf den ersten Blick unkonventionell erschei- nen moegen, um Erstarrungen zu loesen und einseitige Doktrinen zu korrigieren.

The title of this book contains the words ALGORITHMIC LANGUAGE, in the singular. This is meant to convey the idea that it deals not so much with the diversity of program­ ming languages, but rather with their commonalities. The task of formal program develop­ It allows classifying ment proved to be the ideal frame for demonstrating this unity. concepts and distinguishing fundamental notions from notational features; and it leads immediately to a systematic disposition. This approach is supported by didactic, practical, and theoretical considerations. The clarity of the structure of a programming language de­ signed according to the principles of program transformation is remarkable. Of course there are various notations for such a language. The notation used in this book is mainly oriented towards ALGOL 68, but is also strongly influenced by PASCAL - it could equally well have been the other way round. In the appendices there are occa­ sional references to the styles used in ALGOL, PASCAL, LISP, and elsewhere.

Konrad Zuse is one of the great pioneers of the computer age. He created thefirst fully automated, program controlled, freely programmable computer using binary floating-point calculation. It was operational in 1941. He built his first machines in Berlin during the Second World War, with bombs falling all around, and after the war he built up a company that was taken over by Siemens in 1967. Zuse was an inventor in the traditional style, full of phantastic ideas, but also gifted with a powerful analytical mind. Single-handedly, he developed one of the first programming languages, the Plan Calculus, including features copied only decades later in other languages. He wrote numerousbooks and articles and won many honors and awards. This is his autobiography, written in an engagingly lively and pleasant style, full of anecdotes, reminiscences, and philosophical asides. It traces his life from his childhood in East Prussia, through tense wartime experiences and hard times building up his business after the war, to a ripe old age andwell-earned celebrity.

Konrad Zuse is one of the great pioneers of the computer age. He created thefirst fully automated, program controlled, freely programmable computer using binary floating-point calculation. It was operational in 1941. He built his first machines in Berlin during the Second World War, with bombs falling all around, and after the war he built up a company that was taken over by Siemens in 1967. Zuse was an inventor in the traditional style, full of phantastic ideas, but also gifted with a powerful analytical mind. Single-handedly, he developed one of the first programming languages, the Plan Calculus, including features copied only decades later in other languages. He wrote numerousbooks and articles and won many honors and awards. This is his autobiography, written in an engagingly lively and pleasant style, full of anecdotes, reminiscences, and philosophical asides. It traces his life from his childhood in East Prussia, through tense wartime experiences and hard times building up his business after the war, to a ripe old age andwell-earned celebrity.

The title of this book contains the words ALGORITHMIC LANGUAGE, in the singular. This is meant to convey the idea that it deals not so much with the diversity of program­ ming languages, but rather with their commonalities. The task of formal program develop­ It allows classifying ment proved to be the ideal frame for demonstrating this unity. concepts and distinguishing fundamental notions from notational features; and it leads immediately to a systematic disposition. This approach is supported by didactic, practical, and theoretical considerations. The clarity of the structure of a programming language de­ signed according to the principles of program transformation is remarkable. Of course there are various notations for such a language. The notation used in this book is mainly oriented towards ALGOL 68, but is also strongly influenced by PASCAL - it could equally well have been the other way round. In the appendices there are occa­ sional references to the styles used in ALGOL, PASCAL, LISP, and elsewhere.

Neben das theoretische Studium der Informatik muB praktische Obung treten, fUr den Anfanger eine Praxis des Programmierens, die an den Besuch der EinfUhrungs vorlesung anschlieBt. Auch hierfiir solI eine Grundlage gelegt werden. Durch die Ver wendung von ALGOL 68, einer begriftlich ebenso reichhaltigen wie differenzierten Sprache mit iibersichtlichem Aufbau, ist der Obergang zu anderen Programrnierspra chen sehr leicht gemacht. Bei der im Text gewlihlten Anordnung ist nachteilig, daB man zu Beginn wenig Material fUr die Ubungen hat. Dem kann abgeholfen werden, indem man die Ab schnitte 1. 1, 1. 4,4. 1 und 4. 2 vorwegnimmt und damit rasch zu Ubungen iiber Codes und Schaltungen kommt. AnschlieBend konnen die Abschnitte 1. 2, 1. 3, 1. 5, 1. 6 zu sammengefaBt werden; auch kann 4. 3 an das dritte Kapitel angehlingt werden. Beim Aufbau dieser Vorlesung konnten wir uns auf konstruktive Beitrlige unserer Herren Kollegen K. SAMELSON, M. PAUL, F. PEISCHL stiitzen. Eine erste Ausarbeitung fertigte im Studienjahr 1967/68 Frau D. MAISON an. Bei den Ubungen zur Vorlesung, insbesondere der Zusammenstellung von Aufgaben, hatten wir die Hilfe von Herrn R. GNATZ und Herrn H. J. WALTHER, welch letzterer auch eine zweite Ausarbeitung im Studienjahr 1968/69 redigierte. Herr Kollege SAMELSON, der die EinfUhrungsvor lesung im Studienjahr 1969/70 las, hat uns wertvolle Kritik geliefert, daneben hatten wir zu einzelnen Kapiteln niitzliche Hinweise von den Herren Kollegen J. EICKEL, P. DEUSSEN, W. HAHN und Frl. U. HILL."

Fiir den hiennit vorgelegten zweiten Teil und den Anhang "Methodik des Programmie rens" gilt das bereits im Vorwort zum ersten Teil Gesagte. Herrn Dr. H. WOSSNER, der sich weit iiber Beratung hinaus an der Erarbeitung von Aufgaben und Losungen beteiligte, mochten wir besonders danken. Oem Verlag und der Druckerei danken wir fUr die bewiesene groBe Geduld und fUr die ErfUllung unserer Wiinsche beziig lich des manchmal schwierigen Formelsatzes. Miinchen, im Herbst 1975 F. L. BAUER. R. GNATZ . U. HILL Inhaltsverzeichnis* 5. Kapitel Dynamische Speicherverteilung Kellerspeicher 5. 1. 1 Giiltigkeitsbereich und Lebensdauer . . . 3 39 5. 1. 2 Blockstruktur, Organisation des Kellerspeichers 5 40 5. 1. 3 Lebensdauer von Variablen . . 6 41 5. 1. 4 Felddeskriptor. . . . . . . . 6 41 5. 1. 5 Felddeskriptor, Dreiecksmatrix 7 43 5. 1. 6 Speicherverteilung flir Felder 7 45 5. 1. 7 Leitzellentechnik. . . . . . . 8 48 Prozeduren 5. 2. 1 Ackermann-Hermes-Funktion. . . 10 50 5. 2. 2 Struktur rekursiver Prozeduraufrufe 10 52 5. 2. 3 Dynamische Verweisketten . . . . 11 52 5. 2. 4 Dynamische und statische Verweisketten 12 54 5. 2. 5 Prozeduraufrufe. . . . . . . . . . . 13 55 Allgemeine Speicherverteilung 5. 3. 1 Anonyme Objekte . . . . . . . . . . 14 57 5. 3. 2 Speicherverteilung flir anonyme Objekte. 14 58 * Die kursiv gedruckten Seitenzahlen beziehen sich auf die Losung der Aufgabe. VIII Inhaltsverzeichnis 5. 3. 3 Speichern von Verbunden, Organisation der Halde und Speich- bereinigung. . . . . . . 15 59 5. 3. 4 Beispiel aus der Linguistik. 15 61 5. 3. 5 Speicherverteilung fUr Zeichenreihen 16 64 5. 3. 6 Streu-Speicherung. . . . . . . . 17 68 6."

Die hier vorgelegte Sammlung von Aufgaben und Lösungen ergänzt das Lehrbuch ,Informatik. Eine einführende Übersicht' von F. L. BAUER und G. Goos, Heidelberger Taschenbücher Bd. 80, 91. Die Anordnung entspricht kapitelweise der Anordnung im Lehrbuch, die· weitere Unterteilung ist hauptsächlich durch didaktische Gesichts­ punkte bestimmt. Die Aufgaben sind großenteils an der TU München in Tutor­ übungen behandelt worden. Sie dienen in der Regel dazu, die in der Vorlesung ein­ geführten Begriffsstrukturen auszufüllen und zu festigen; dies gilt insbesondere für die Programmierungsaufgaben, bei denen der banale Nebenzweck, die Gewöhnung an eine formale Notation, nicht in den Vordergrund treten soll. Häufig bringen die Aufgaben auch Ergänzungen und Vertiefungen des Stoffes. Im Charakter der Auf­ gaben haben wir uns bemüht, Abwechslung zu zeigen. Wenig Raum haben wir dabei dem Typ von Aufgaben gegeben, der so fatalerweise an ,programmiertes Lernen' er­ innert: Aufgaben, bei denen man mit Ja oder Nein antworten kann; oder Aufgaben, bei denen etwa von fünf vorgelegten Programmfassungen herauszufinden ist, welche Fassungen, wenn überhaupt, richtig sind. Solche Aufgaben regen den Geist nicht an, von intelligenten Studenten werden sie leicht als Quälerei aufgefaßt. Sie mögen ge­ eignet sein, um im Selbststudium oder im Tutorunterricht mechanisch zu überprüfen, ,ob man mitkommt', und deshalb ihren Platz haben in einer modemen Didaktik des Massenstudiums. Sie sind unschwer zu konstruieren, und die wenigen Beispiele, die wir bringen, mögen als Anhaltspunkte dienen. Dies gilt übrigens für alle Aufgaben: Sie sollen auch zu abgewandelten und neuen AufgabensteIlungen anregen.

Sammlung Informatik