Vorlesungen über Informatik

Info1-4_Clickable
Band 1:
"Grundlagen und funktionales Programmieren"
Band 2:
"Objektorientiertes Programmieren und Algorithmen"
Band 3:
"Berechenbarkeit, formale Sprachen und Spezifikationen"
Band 4:
"Parallelität und nicht-analytische Lösungsverfahren"
(Erschienen im Springer-Verlag)

Band 1:
Grundlagen und funktionales Programmieren

Vorwort

Wir sehen heute die wesentlichen Aufgaben der Informatik in der Analyse, dem Entwurf und der Realisierung komplexer, diskreter Systeme sowie in der Anpassung solcher Systeme an gegebene Einsatzbedingungen.

Dies wurde und wird nicht immer so gesehen. In der Anfangszeit wurde Informatik vor allem als die Kunst oder Technik begriffen, Aufgaben der Informationsverarbeitung mit technischer Unterstützung durch Rechner zu meistern, oder solche Rechner selbst zu entwerfen und zu bauen. Dies prägt die Erwartungshaltung, die die Öffentlichkeit der Informatik und den Informatikern entgegenbringt.

Diese Auffassung ist nicht falsch: Einsicht in komplizierte Sachverhalte zu gewinnen, sich ein Modell von der Struktur der Zusammenhänge zu machen oder komplexe Systemstrukturen selbst zu entwerfen, ist eine Aufgabe der Informationsverarbeitung. Wenn der Mensch Unterstützung für solche Aufgaben sucht, die er letztlich mit seinem Hirn bewältigen muß, verwendet er heute Rechner. Die Informatik soll ihm dabei helfen.

Die Konzentration auf den technischen Umgang mit Rechnern und deren Programmierung verengt das Interesse jedoch auf die unterste Stufe der Informationsverarbeitung, die Frage, wie ein schon gefundenes Verarbeitungsmodell realisiert werden kann. Die Gestaltung und der Entwurf solcher Verarbeitungsmodelle ist die eigentliche, schwierige Aufgabe. Dabei sind heute die meisten Rechner Bestandteil wesentlich größerer Systeme, seien es Autos, Verkehrssteuerungssysteme, Telefone oder andere Kommunikationseinrichtungen.

Im Unterschied zu anderen Wissenschaften befaßt sich die Informatik fast ausschließlich mit diskreten, nicht mit kontinuierlichen Systemen. Dies ist nicht eine Folge der Tatsache, daß heutige Rechner nur digitale Daten verarbeiten können. Vielmehr können wir in endlicher Zeit immer nur endlich viele Beobachtungen der Realität machen und nur endlich viele Anweisungen zur Änderung des Zustands eines realen Systems geben. Aufgrund der Gesetze der Physik erweist sich die Modellierung eines realen Systems durch ein kontinuierliches System als eine Abstraktion, bei der die mikroskopisch diskret auffaßbaren Vorgänge durch ein makroskopisches stetiges Modell ersetzt werden. Kontinuierliche Systeme treten daher auch in der Informatik immer dann auf, wenn makroskopisch von einer großen Zahl von Einzelbeobachtungen abstrahiert wird.

Dementsprechend ist die Aufgabe dieses Buches und seiner Folgebände zu lehren,

Die Hilfsmittel reichen von mathematischen Hilfsmitteln über Spezifikationssprachen verschiedener Abstraktionsstufen bis zu Programmiersprachen. Die allgemeinen Modelle umfassen Relationen, Graphen, Automaten, Petrinetze, Termersetzungssysteme, Algorithmen und Datenstrukturen, Methoden der Algorithmenkonstruktion, Verarbeitungsmodelle der theoretischen Informatik usw.

Abgesehen von statischen Systemen, zu denen z.B. auch Programmtexte zählen, unterscheiden wir grundsätzlich zwei Arten von (dynamischen) Systemen:

Abbildungen
f: A -> B: Sie werden durch Algorithmen realisiert. Sie bilden Werte in Werte ab.
Reaktive Systeme:
Ihre Aufgabe ist es, fortwährend auf Ereignisse und Daten aus ihrer Umwelt zu reagieren. Sie besitzen Zustände und die Reaktion kann vom bisherigen Zustand abhängen. Zustände werden in der Zeit eingenommen; es gibt also einen Zeitbegriff.
Dieser erste Band führt viele mathematische Hilfsmittel ein, die auch für die Behandlung reaktiver Systeme erforderlich sind. Anschließend beschränken wir uns auf Algorithmen und benutzen daher eine funktionale Programmiersprache. Die Behandlung von Systemen mit internen Zuständen ist Aufgabe der Folgebände.

Das Buch entstand aus der Anfängervorlesung, die der Verfasser 1993/94 an der Universität Karlsruhe gehalten hat. Beim Gebrauch in und neben Vorlesungen mögen folgende Hinweise helfen:

Ich habe mich bemüht, Hilfsmittel und Verfahren einzuführen, bevor ich sie benutze. Bevor man beispielsweise Bedingungen in Programmiersprachen gebraucht (und dann umformt, usw.) sollte man wissen, nach welchen Gesetzen solche Bedingungen aufgebaut sind, und nicht nur ein intuitives Verständnis dafür entwickeln. Man benötigt dann allerdings mathematische Grundlagen, bevor man mit der eigentlichen Arbeit beginnen kann.

Das Buch ist nicht nur als Grundlage für Vorlesungen gedacht. Für das Nachlernen des Stoffes habe ich mich bemüht, Themengebiete zusammenhängend abzuhandeln. Beim ersten Durcharbeiten und in einer Vorlesung kann man auf manches verzichten oder Teile des Stoffs auf später verschieben. So benötigt man vom Abschnitt 1.5 zunächst nur kontextfreie Grammatiken, die BNF und Syntaxdiagramme. Alles andere kann auf später verschoben werden. Konfluenz ist unter Halbordnungen im zweiten Kapitel abgehandelt, obwohl man es erst bei der Termersetzung im dritten Kapitel benötigt. Auch sonst sind in einer Vorlesung, allein schon wegen der Fülle des Stoffes, Umstellungen und Kürzungen angemessen. Dies betriftt insbesondere das Kapitel über Logik, aus dem manches erst sehr viel später in der Ausbildung benötigt wird.

Es ist Sache des Vortragenden, dem Studenten den praktischen Nutzen der Begriffsbildungen für die Beschreibung und Modellierung von Systemen zu demonstrieren, damit der Stoff nicht als theoretisches Spielzeug erscheint, als der er nicht gemeint ist. Die Beispiele und Aufgaben des Buches bieten hier aus Platzgründen nur eine unvollkommene Hilfe.

Diskrete Systeme, wie wir sie mit Rechnern realisieren, betreiben eigentlich ein formales Glasperlenspiel. Semantische Bedeutung erhält dieses Spiel durch die Interpretation außerhalb des Rechnerkontexts. Eine voreilige Befassung mit der Bedeutung des Spiels lenkt von der Aufgabe ab, die Gesetze des Glasperlenspiels zu begreifen; stattdessen meint man, es werde schon richtig sein, weil man (vermeintlich) den Vorgang interpretieren kann, ein Rückfall in eine phänomenologische Betrachtungsweise der Rechnerbenutzung.

Der Hauptzweck der Benutzung einer funktionalen Programmiersprache in der Anfängerausbildung besteht darin, sich klarzumachen, daß ein ausführbares Programm und eine Aufgabenspezifikation oftmals ein und dasselbe ist. Im Hinblick auf die Anwendung sollte die Spezifikation, nicht deren Auffassung als Programm im Vordergrund stehen. Die Bedeutung der Sprachelemente hat nichts Geheimnisvolles an sich, das man mit großem Aufwand erlernen müßte, sondern folgt durch konsequente Anwendung mathematischer Gesetzmäßigkeiten aus der Termalgebra und dem Lambda-Kalkül. Auch Korrektheitsüberlegungen ergeben sich in natürlicher Weise aus mathematischen Beweisschemata, wie sie zuvor eingeführt wurden. Zusätzlich liefern Polymorphie, überladen und abstrakte Datentypen, die in funktionalen Sprachen präzise erklärt werden können, eine saubere Fundierung der Vererbung, Polymorphie und des Klassenbegriffs objektorientierter Sprachen, womit wir uns im zweiten Band beschäftigen werden.

Welche funktionale Programmiersprache man benutzt, ist gleichgültig. Die meisten dieser Sprachen sind in ihrem Kern identisch. Unsere Entscheidung für Gofer ist durch die Verfügbarkeit einer PC-Implementierung diktiert, die die Studenten nach Hause nehmen können.

Anhang A wiederholt Kenntnisse, die mit größerer Ausführlichkeit in Mathematikvorlesungen gebracht werden. Anhang B stellt Kenntnisse zusammen, die spätestens neben der Programmiereinführung in Kap. 5 erlernt werden sollten.

Kleingedruckte Hinweise auf Programmiersprachen wie C, Modula oder Pascal sind für das weitere Verständnis nicht erforderlich, sondern sollen die Ausführungen mit etwaigen Vorkenntnissen des Lesers in Zusammenhang bringen.

Die Idee zu diesem Buch entstand aus vielen Diskussionen mit und Vorschlägen von Herrn Thomas Beth, dem ich hierfür recht herzlich danke. Zu großem Dank bin ich meinen Mitarbeitern Andreas Heberle und Martin Trapp sowie Arne Frick, Joachim Weisbrod und Wolf Zimmermann verpflichtet, ohne deren Mithilfe dieses Buch nicht zustandegekommen wäre. Für zahlreiche wertvolle Hinweise, Verbesserungsvorschläge und die Durchsicht von Teilen des Manuskripts danke ich den Studenten meiner Vorlesung sowie den Herren Egon Börger, Peter Lockemann, Peter Schmitt, Wolfgang Thomas, Walter Tichy, Ingo Wegener und Eugen-Georg Woschni. Die Mitarbeiter des Springer-Verlags haben mich nach Kräften bei der Gestaltung des endgültigen Textes unterstützt. Nicht zuletzt möchte ich mich bei meiner Frau für die Durchsicht des Manuskripts und die Nachsicht und Geduld bedanken, mit der sie die Arbeit an diesem Buch ertrug.

Karlsruhe, im Juli 1995 Gerhard Goos

Vorwort zur zweiten Auflage

Die freundliche Aufnahme dieses Buches machte nach kurzer Zeit eine Neuauflage notwendig. In ihr wurden vor allem kleinere Fehler in Text und Abbildungen korrigiert. Dem mehrfach geäußerten Wunsch, Lösungen zu den gestellten Aufgaben anzubieten, konnte ich aus Platzgründen nicht entsprechen. Den Kollegen Stefan Jähnichen, Uwe Kastens und Roland Vollmar sowie zahlreichen Mitarbeitern und Studenten danke ich für Hinweise, die zu Verbesserungen führten. Die Herren Andreas Heberle und Martin Trapp haben mich, wie bei der ersten Auflage, sehr tatkräftig unterstützt.

Karlsruhe, im Juni 1997 Gerhard Goos


Zur Heimatseite

Inhaltsverzeichnis Band 1

1 Grundbegriffe
1.1 Signal, Datum, Information
1.1.1 Wissen
1.1.2 Analoge und digitale Signale
1.1.3 Codierung von Daten
1.1.4 Von der Signal- zur Informationsverarbeitung
1.1.5 Semiotik: Syntax, Semantik und Pragmatik
1.2 Wirklichkeit und Modell
1.2.1 Die Verantwortung des Informatikers
1.3 Systeme
1.3.1 Die Aufgaben von Informatik-Systemen
1.3.2 Konstruktion von Informatik-Systemen
1.4 Algorithmen
1.5 von-Neumann-Rechner
1.6 Semi-Thue-Systeme
1.6.1 Markov-Algorithmen
1.6.2 Formale Systeme
1.6.3 Chomsky-Grammatiken
1.7 Anmerkungen und Verweise
2 Halbgruppen, Relationen
2.1 Halbgruppen und Monoide
2.2 Relationen und Graphen
2.2.1 Gerichtete und ungerichtete Graphen
2.2.2 Repräsentation von Relationen und Graphen
2.3 Ordnungsrelationen, Halbverbände, Verbände
2.3.1 Quasiordnungen
2.3.2 Hasse-Diagramme
2.3.3 Untere und obere Schranken
2.3.4 Normalformen und Konfluenz
2.3.5 Vollständige Halbordnungen
2.3.6 Halbverbände
2.3.7 Dualisierung
2.3.8 Verbände
2.4 Endliche Automaten
2.5 Petrinetze
2.6 Relationale Algebra
2.6.1 Mengenoperationen auf Relationen
2.6.2 Datenbankoperationen
2.6.3 SQL
2.7 Anmerkungen und Verweise
3 Algebren und Termalgebren
3.1 Formeln
3.2 Boolesche Algebra
3.3 Algebraische Strukturen und Algebren
3.4 Abbildungen zwischen Algebren
3.5 Termalgebren
3.5.1 Strukturelle Induktion
3.6 Termalgebren mit Variablen
3.7 Termersetzungssysteme
3.8 Abstrakte Datentypen
3.9 Anmerkungen und Verweise
4 Formale Logik
4.1 Aussagenlogik
4.1.1 Grundbegriffe
4.1.2 Folgerungen und Kalküle
4.1.3 Ein Kalkül für die Aussagenlogik
4.1.4 Normalformen
4.1.5 Hornklauseln und Resolution
4.1.6 Junktoren
4.1.7 Schaltfunktionen
4.1.7.1 Minimierung von Schaltfunktionen
4.1.8 Geordnete binäre Entscheidungsdiagramme
4.1.8.1 Entscheidungstabellen
4.1.9 Schaltwerke
4.1.9.1 Zusammenhang mit endlichen Automaten
4.1.9.2 Flipflops
4.1.9.3 Register und Schieberegister
4.1.9.4 Serienaddierer
4.2 Prädikatenlogik
4.2.1 Syntax und Semantik der Prädikatenlogik
4.2.2 Ein Kalkül für die Prädikatenlogik
4.2.3 Normalformen
4.2.4 Resolution
4.2.4.1 Logisches Programmieren
4.3 Anmerkungen und Verweise
5 Funktionales Programmieren
5.1 Elementarer Lambda-Kalkül
5.1.1 Bedingte Lambda-Ausdrücke
5.1.2 Rekursion
5.1.3 Faule Auswertung
5.1.4 Operationelle Semantik des Lambda-Kalküls
5.1.5 Die Programmiersprache Lisp
5.1.6 Ein Interpretierer für Lisp
5.2 Grundelemente funktionaler Programmiersprachen
5.2.1 Elementare Spracheigenschaften
5.2.2 Bezeichner, Operatoren, Ausdrücke
5.2.2.1 Gültigkeitsbereiche
5.3 Daten und elementare Datentypen
5.3.1 Boolesche Werte
5.3.2 Ganze Zahlen, Gleitpunktzahlen
5.3.3 Zeichen
5.3.4 Listen
5.3.4.1 Sortieren von Listen
5.3.4.2 Listenbeschreibungen und Generatoren
5.3.5 Texte
5.3.6 Tupel
5.3.7 Funktionen als Werte
5.3.8 Muster
5.4 Allgemeines über Datentypen
5.4.1 Typinferenz und Polymorphie
5.4.2 Überladen von Definitionen
5.5 Grundlegende Programmiermethoden
5.5.1 Rekursion
5.5.2 Durchreichen von Zwischenergebnissen
5.5.3 Unbeschränkte Listen
5.5.3.1 Zufallszahlengeneratoren
5.5.4 Hinweise zur Dokumentation von Programmen
5.6 Anmerkungen und Verweise
6 Abstrakte Datentypen
6.1 Die natürlichen Zahlen
6.2 Lineare Datenstrukturen
6.2.1 Listen
6.2.2 Reihungen
6.2.3 Keller
6.2.4 Schlangen
6.2.5 Sequenzen und Dateien
6.3 Binärbäume
6.4 Mengen und Mehrfachmengen
6.5 Anmerkungen und Verweise
7 Algorithmenkonstruktion I
7.1 Aufwand von Algorithmen
7.1.1 Der O-Kalkül
7.1.2 Anwendungen
7.2 Teile und Herrsche
7.2.1 Zeitoptimales sequentielles Sortieren
7.2.1.1 Sortieren durch Zerlegen
7.2.1.2 Sortieren durch Mischen
7.2.2 Einseitiges Teile-und-Herrsche
7.2.3 Matrixmultiplikation nach Strassen
7.3 Gierige Algorithmen
7.3.1 Zeitplanerstellung
7.3.2 Minimale spannende Bäume
7.3.3 Matroide
7.3.4 Zeitplanung mit Endterminen
7.4 Anmerkungen und Verweise Literatur
A Mengen, Relationen, Funktionen, Zahlen
A.1 Mengen
A.2 Relationen und Funktionen
A.3 Natürliche Zahlen
A.4 Mehrfachmengen
A.5 Anmerkungen
B Codierung
B.1 Zeichenvorräte
B.2 Codierung von Zahlen
B.2.1 Binärdarstellung ganzer Zahlen
B.2.2 Darstellung von Gleitpunktzahlen
B.3 Präfixcodes und Shannonsche Informationstheorie
B.3.1 Shannonsche Informationstheorie
B.4 Fehlererkennung und -Korrektur
B.4.1 Zyklische Codes und Schieberegister
B.5 Anmerkungen und Verweise


Zur Heimatseite

Band 2:
Objektorientiertes Programmieren und Algorithmen

Vorwort

Dieser zweite Band der Reihe Vorlesung über Informatik ist eine erweiterte Fassung des zweiten Teils der Anfängervorlesung, die ich im Sommersemester 1994 hielt.

Wir bauen in vielfältiger Weise auf den Ergebnissen des ersten Bandes auf, den wir nur mit Angabe der Abschnittsnummern zitieren. Die grundsätzlichen Bemerkungen aus dem Vorwort des ersten Bande gelten auch hier. Im Vordergrund steht jetzt jedoch die Konstruktion von Systemen, die einen internen Zustand besitzen, und von Algorithmen.

Für die nachprüfbar korrekte Realisierung eines sequentiellen Algorithmus zu vorgegebener Spezifikation stehen uns mit den Zusicherungskalkülen von Hoare und Dijkstra mächtige, mathematisch sauber fundierte Hilfsmittel zur Verfügung. Info2-Cover Diesen ist - nach einem kurzen Abriß der Grundbegriffe imperativen Programmierens - das Kapitel 8 gewidmet. Für die Praxis ist es wichtig, daß sich der Student den Umgang mit Vor- und Nachbedingungen, Schleifeninvarianten usw. so aneignet, daß er diese Denkweise auch bei Aufgaben benutzen kann, die sich mathematisch nicht so einfach spezifizieren lassen wie die Beispiele aus Kap. 8 und der nachfolgenden Kapitel. Der Gebrauch des Prädikatenkalküls darf nicht dazu führen, daß man die Denkweise des Zusicherungskalküls aufgibt, sobald die Begriffe nicht mehr bequem formalisierbar sind oder die Formeln unhandlich werden.

Zielorientierter oder top-down-Entwurf und schrittweise Verfeinerung unter Einsatz von Datenabstraktion sind die natürliche Erweiterung des Zusicherungskalküls auf größere Aufgaben. Diese Entwurfsmethodik behandeln wir in Kap. 9. Als Beispiele dienen Sortieralgorithmen, die jeder Informatiker beherrschen sollte. Zur Datenabstraktion und Datenverfeinerung gehört natürlich nicht nur der Umgang mit Reihungen wie bei den Sortierverfahren, sondern auch der Umgang mit anonymen Objekten auf der Halde und der Modulbegriffe wie man das aus Sprachen wie Modula kennt. Die zugehörigen Begriffe werden im Hinblick auf das nachfolgende Kapitel hier nur kurz behandelt.

Zielorientierter Entwurf geht von einer Spezifikation aus, die er schrittweise in eine ausführbare Fassung bringt. Hingegen versteht objektorientiertes Modellieren ein System als eine Menge kooperierender Objekte. Für die einzelnen Objekte und ihre Methoden ist die Verwendung des Zusicherungskalküls zweckmäßig; die Verfahren der vorigen Kapitel erscheinen jetzt als Methoden zum Programmieren-im-Kleinen.

Die Vorstellung kooperierender Objekte vermittelt jedoch einen anderen Denkansatz zum Programmieren-im-Großen als zielorientierter Entwurf. Nicht die in sich geschlossene Lösung eines vorgegebenen Problems, sondern die Konstruktion eines erweiterbaren, durch Austausch von Bausteinen änderbaren Systems ist das Ziel. Damit einher geht die Konstruktion von Einzelbausteinen, Bibliotheken solcher Bausteine und spezialisierbaren Rahmensystemen, die für diese Art der Systemkonstruktion einsetzbar sind. Der Umgang mit Vererbung, Generizität, Polymorphie und anderen beliebten Schlagworten objektorientierten Programmierens ist Hilfsmittel zum Zweck, aber nicht hauptsächliches Lernziel. Aus diesem Grunde beginnen wir in Kap. 10 nicht auf der Programmierebene, sondern mit objektorientierter Modellierung. Beim Gebrauch in Vorlesungen ist es sinnvoll, das ausführliche Beispiel in 10 in den Mittelpunkt zu stellen und die Methodik in 10 ausgehend von diesem Beispiel zu behandeln.

Objektorientierte Modellierung können wir leider nicht wie den zielorientierten Entwurf mit einem systematischen Kalkül begleiten. Die Modellierung erscheint daher als eine Kunst, für die es zwar Hilfsmittel und methodische Unterstützung gibt; die durchgängige Verifikation kann jedoch erst für den fertiggestellten Entwurf geleistet werden und setzt dort vorher spezifizierte und verifizierte Werkzeuge voraus. Dies ist nicht ein Fehler des objektorientierten Ansatzes, sondern spiegelt den noch nicht ausreichenden Stand der theoretischen Beherrschung erweiterbarer und verteilbarer Systeme wider.

Jedes Objekt eines solchen Systems erscheint nach außen als ein sequentiell arbeitender Baustein. Das Gesamtsystem könnte auch parallel oder verteilt arbeiten. Die Modellierung nimmt auf sequentielle Ausführung keine Rücksicht. Erst die Umsetzung des Modells befaßt sich mit dieser Frage und baut auf sequentiellen Bausteinen und Teilsystemen auf. Die Erörterung sequentieller objektorientierter Strukturen auf der Ebene einer Programmiersprache bildet den zweiten Teil des Kap. 10. Wir üben diese Strukturen am Beispiel der abstrakten Datenstrukturen Menge und Graph und verschiedenen Realisierungen davon. Damit führen wir zugleich die mit den Sortieralgorithmen begonnene Behandlung von Algorithmen und Datenstrukturen weiter.

Das Kap. 11 schließt die Einführung der programmiertechnischen Hilfsmittel mit der Erörterung der Abbildung der elementaren Ablauf- und Datenstrukturen auf den Befehlssatz von von-Neumann-Rechnern und auf den (stückweise) linearen Speicher ab. Fragen der Befehlsanordnung, der Fließbandverarbeitung in superskalaren Prozessoren und vor allem die Ausnutzung der lokalen Speicher von Prozessoren machen es zunehmend schwieriger, von Hand Programme in Maschinensprache zu schreiben, deren Leistung mit automatisch übersetzten Programmen konkurrieren kann. Die Behandlung von Maschinensprachen beschränkt sich daher auf die Vorstellung von Prinzipien und geht nicht mehr auf eine explizite Programmierung auf dieser Abstraktionsebene ein.

Kap. 11 führt auch die RAM-Modelle von Rechnern als Grundlage für eine präzise Aufwandsberechnung ein. Die exakte Definition des Berechenbarkeitsbegriffs auf der Grundlage des RAM-Modells und die Einführung von while- und loop-Sprachen an dieser Stelle mag ungewöhnlich erscheinen. Sie ergibt sich aber in natürlicher Weise und erspart umfangreiche Wiederholungen in Band III.

Im Kap. 12 setzen wir die Einführung in die Algorithmenkonstruktion aus Kap. 7 in Band I fort. Die Betonung liegt hier auf den Techniken zur Algorithmenkonstruktion wie dynamisches Programmieren, zufallsgesteuerte Algorithmen usw. Die systematische Behandlung der wichtigsten Algorithmen gegliedert nach Themengebieten wie Algorithmen auf Graphen, usw. bleibt Vorlesungen im Hauptstudium vorbehalten.

Beim funktionalen Programmieren unterscheiden sich die Programmiersprachen in ihrem Kern nur wenig voneinander. Bei imperativen Programmiersprachen verhält sich dies anders: Zwar kehren die Grundbegriffe wie Variable, Typ und Vereinbarung einer Variablen, Schleife, Prozedur, Prozedurparameter, usw. in allen Sprachen wieder. Die Terminologie, die syntaktische Notation und viele semantische Einzelheiten unterscheiden sich jedoch in subtiler Weise beim übergang von einer Sprache zur anderen. Zudem sind die Sprachen zu unterschiedlichen Zeiten entstanden und reflektieren einen unterschiedlichen Stand der Kenntnis über die Methodik des Programmentwurfs. Bei der Auswahl einer Programmiersprache für ein Lehrbuch steht die Frage nach einer konzisen Notation der Beispiele und nach einer Abdeckung der zur Strukturierung und zum Entwurf von Programmen verwandten Prinzipien im Vordergrund. Unter diesem Gesichtspunkt verwenden wir hier die objektorientierte Sprache Sather , deren Eigenschaften wir in Anhang C zusammengestellt haben.

Wir verwenden Sather bereits für die Formulierung der Grundlagen zustandsorientierten und strukturierten Programmierens. Bis zum Ende von Kap. 9 sind sämtliche Sprachelemente mit Ausnahme von Vererbung, Polymorphie und Strömen eingeführt und benutzt worden. Es kann beim Leser zunächst zu Verwirrung führen, wenn in den beiden ersten Kapiteln die Begriffe imperative und objektorientierte Programmiersprache nicht unterschieden werden. Darin zeigt sich jedoch, wie oben erwähnt, daß das Programmieren-im-Kleinen auch in heutigen objektorientierten Sprachen den Regeln üblichen strukturierten Programmierens folgt. Insbesondere ist die Gleichsetzung des Modulbegriffs mit dem Begriff Klasse in 9 zunächst überraschend; sie wird hier benutzt, um uns die Befassung mit einer anderen Sprache wie Modula oder Ada zu ersparen.

Die Wahl der seit 1990 am International Computer Science Institute in Berkeley entworfenen Sprache Sather, für deren Weiterentwicklung und Implementierung wir uns in Karlsruhe seit 1991 engagierten, hat überwiegend didaktische Gründe. Die aus der Sicht der späteren industriellen Verwendung naheliegende Wahl von C++ könnte nur einen Sprachkern betreffen, der wegen der Komplexitäten dieser Sprache nicht einwandfrei identifizierbar wäre. Die Wahl von Eiffel oder Smalltalk führt zu Programmen, deren Typkonsistenz nicht statisch nachgewiesen werden kann. Dies ist aus der Sicht systematischer Konstruktion bedenklich, wenn die resultierenden Systeme über lange Zeit eingesetzt, modifiziert und erweitert werden sollen. Vor allem aber führt in Sather die einfache Erklärung der Vererbung durch Einkopieren der Oberklasse und die Unterscheidung zwischen der Untertypisierung als Grundlage der Polymorphie und der allgemeineren Wiederverwendung von Code zu einem elementareren Verständnis von Vererbung als man das mit Hinweis auf komplizierte Typtheorien beim Anfänger erreichen kann.

Der Leser unterscheide jedoch die grundlegenden Elemente und Begriffe von ihrer speziellen Ausprägung in Sather. Jede Programmiersprache ist ein Artefakt. Sie könnte durch eine andere Sprache ersetzt werden, ohne daß sich irgendetwas an unseren grundsätzlichen überlegungen ändert. Nach Studium der Grundbegriffe sollte der Leser in der Lage sein, die Beispiele in die Notation seiner Wahl zu übertragen. Man mache sich dabei klar, daß die Grundbegriffe des Entwurfs und der Konstruktion von Programmsystemen unabhängig von der verwandten Terminologie und Programmiersprache sind.

Beim Schreiben dieses Buches haben mich meine Mitarbeiter Andreas Heberle und Martin Trapp sowie Arne Frick, Welf Löwe, Rainer Neumann, Martin Spott, Jürgen Vollmer, Markus Weinhardt, Walter Zimmer und Wolf Zimmermann tatkräftig unterstützt. Die Konzeption des ersten Teils von Kap. 10 geht wesentlich auf Claus Lewerentz, Rainer Neumann und Martin Trapp zurück. Der Anhang C stammt von Martin Trapp. Ihnen allen bin ich zu großem Dank verpflichtet. Den Herren Wilfried Brauer, Jerome Feldman, Stefan Jähnichen, Holger Klawitter und Roland Vollmar danke ich für zahlreiche wertvolle Hinweise, Verbesserungsvorschläge und die Durchsicht von Teilen des Manuskripts. Die Mitarbeiter des Springer-Verlags haben mich nach Kräften bei der Gestaltung des endgültigen Textes unterstützt. Nicht zuletzt möchte ich mich bei meiner Frau für die Durchsicht des Manuskripts und die Nachsicht und Geduld bedanken, mit der sie die Arbeit auch an diesem Buch ertrug.

Karlsruhe, im Februar 1996 Gerhard Goos


Zur Heimatseite

Inhaltsverzeichnis Band 2

8 Zustandsorientiertes Programmieren
8.1 Grundbegriffe
8.1.1 Variable und Konstante
8.1.2 Vereinbarungen, Programme
8.1.3 Gültigkeitsbereich und Lebensdauer
8.1.4 Typen und Operationen
8.1.5 Ausdrücke
8.1.6 Ablaufsteuerung
8.1.6.1 Hintereinanderausführung, Blöcke
8.1.6.2 Bedingte Anweisungen, Fallunterscheidungen
8.1.6.3 Schleifen
8.1.6.4 Prozeduren
8.1.6.5 Ausnahmebehandlung
8.2 Zusicherungskalkül
8.2.1 Axiome des Zusicherungskalküls
8.2.2 Zuweisung
8.2.3 Hintereinanderausführung, Blöcke
8.2.4 Bedingte Anweisungen
8.2.5 Bewachte Anweisungen und die Fallunterscheidung
8.2.6 Schleifen
8.2.7 Prozeduren
8.2.7.1 Rekursives und iteratives Problemlösen
8.2.8 Ausnahmebehandlung
8.3 Anmerkungen und Verweise
9 Strukturiertes Programmieren
9.1 Schrittweise Verfeinerung
9.2 Datenverfeinerung am Beispiel Sortieren
9.2.1 Die Aufgabe
9.2.2 Sortieren durch Auswahl
9.2.3 Sortieren durch Einfügen
9.2.4 Sortieren durch Zerlegen
9.2.5 Baumsortieren
9.2.6 Sortieren durch Mischen
9.2.7 Die minimale Anzahl von Vergleichen
9.2.8 Stellenweises Sortieren
9.2.8.1 Fach-Sortieren
9.2.8.2 Binäres stellenweises Sortieren mit Vertauschen
9.2.8.3 Sortierverfahren im Vergleich
9.3 Programmieren mit Objekten
9.3.1 Zusammengesetzte Objekte
9.3.2 Referenztypen
9.3.3 Anonyme Objekte
9.4 Modularität
9.5 Anmerkungen und Verweise
10 Objektorientiertes Programmieren
10.1 Grundbegriffe
10.1.1 Systeme und Teilsysteme
10.1.2 Objekte und Klassen
10.2 Objektorientiertes Modellieren
10.2.1 Kooperation von Objekten
10.2.2 Objektmodell
10.2.3 Funktionales Modell
10.2.4 Dynamisches Modell
10.2.5 Vererbung und Verallgemeinerung, Polymorphie
10.2.6 Restrukturierung des Entwurfs
10.2.7 Beispiel: Der Scheckkartenautomat
10.3 Vom Modell zum Programm
10.3.1 Umsetzung des Modells in die Programmiersprache
10.3.2 Ströme
10.3.3 Gebundene Methoden
10.3.3.1 Stromobjekte
10.4 Datenstrukturen
10.4.1 Abstrakte Klassen und Polymorphie
10.4.2 Mengen und Mehrfachmengen
10.4.2.1 Implementierungen
10.4.2.2 Reihungen und Listen
10.4.2.3 Bitvektoren
10.4.2.4 Haschtabellen
10.4.2.5 Verkettetes Haschen
10.4.2.6 Offenes Haschen
10.4.2.7 Mengenimplementierung mit Bäumen
10.4.2.8 Binäre Suchbäume
10.4.2.9 AVL-Bäume
10.4.3 Graphen
10.4.3.1 Ausspähen eines Graphen
10.4.3.2 Breitensuche
10.4.3.3 Tiefensuche
10.5 Anmerkungen und Verweise
11 Vom Programm zur Maschine
11.1 Die Sprache Simplicius
11.1.1 Sprünge
11.2 Berechnung von Ausdrücken
11.3 Transformation der Ablaufsteuerung
11.3.1 Bedingte Anweisungen
11.3.1.1 Kurzauswertung boolescher Ausdrücke
11.3.2 Fallunterscheidungen
11.3.3 Schleifen
11.4 Datenrepräsentation, Register, Speicherzugriff
11.4.1 Speicherabbildung
11.4.1.1 Variable
11.4.1.2 Verbunde
11.4.1.3 Reihungen
11.4.1.4 Verweise und Referenzobjekte
11.4.1.5 Der Laufzeitkeller
11.4.2 Unterprogrammaufrufe
11.5 Befehle
11.6 Das RAM-Modell
11.6.1 Berechenbarkeit
11.7 Anmerkungen und Verweise
12 Algorithmenkonstruktion II
12.1 Dynamisches Programmieren
12.1.1 Berechnung von Binomialkoeffizienten
12.1.2 Optimale Klammerung von Matrixprodukten
12.1.3 Zerteilung kontextfreier Sprachen
12.2 Amortisierte Analyse
12.2.1 Datenstrukturen für disjunkte Mengen
12.3 Vorberechnung
12.3.1 Einfache Textsuche
12.3.2 Textsuche nach Knuth, Morris, Pratt
12.3.3 Textsuche nach Boyer und Moore
12.4 Zufallsgesteuerte Algorithmen
12.4.1 Monte Carlo Algorithmen
12.4.2 Las Vegas Algorithmen
12.4.2.1 Allgemeine Las Vegas Algorithmen
12.4.2.2 Macao Algorithmen
12.5 Anmerkungen und Verweise
C Sather im Überblick
C.1 Syntaxdiagramme
C.1.1 Grundsymbole
C.1.2 Klassenvereinbarungen und Typen
C.1.3 Methodenrümpfe
C.1.4 Ausdrücke
C.2 Basisbibliothek


Zur Heimatseite

Band 3
Berechenbarkeit, formale Sprachen und Spezifikationen

Vorwort

Der vorliegende dritte Band der Reihe Vorlesungen über Informatik entstand ursprünglich aus den Vorlesungen des Wintersemesters 1994/95. Sein Thema sind die Grundlagen der theoretischen Informatik und der Spezifikationstechnik.

Wir bauen in vielfältiger Weise auf den Ergebnissen der Vorgängerbände auf, die wir nur mit Angabe der Abschnittsnummern zitieren. Dies gilt insbesondere für die Abschnitte 1.4.1 und 2.4 des ersten Bandes, die einen Teil des Stoffes von Kapitel 15 vorweggenommen haben.

Theoretische Informatik geht in zentralen Ergebnissen auf Arbeiten in der Mathematik und Logik in den 30er Jahren dieses Jahrhunderts zurück und hat von allen Teilgebieten der Informatik Info3-Cover sicher den umfangreichsten Bestand an gesicherten und unverrückbaren Ergebnissen. Dies mag rechtfertigen, die Grundlagen wie vielerorts üblich in eigenständigen Vorlesungen zu behandeln.

Die Integration mit anderen Grundvorlesungen fördert jedoch die Zusammenschau der Themen und Methoden und ermöglicht Anwendungen und Rückkopplungen, die bei strenger Trennung der Gebiete und ihrer Wertmaßstäbe unterbleiben.

Lehrziel des Kap. 13 ist zunächst der Nachweis der Gleichwertigkeit der Berechenbarkeitsbegriffe, die durch while- und goto-Algorithmen, Turingmaschinen, Markov-Algorithmen und Chomsky-0-Sprachen sowie Mü-rekursive Funktionen gegeben sind. Danach befassen wir uns mit Unentscheidbarkeitsaussagen, beginnend mit dem Halteproblem von Turingmaschinen. Das unentscheidbare Postsche Korrespondenzproblem ist Grundlage der Unentscheidbarkeitsaussagen über kontextfreie Sprachen in Kap. 15. Auf die zahlreichen weiteren Implikationen des Korrespondenzproblems für Unentscheidbarkeitsaussagen in speziellen algebraischen Strukturen gehen wir nicht ein.

In Kap. 14 wird die NP-Vollständigkeit der Entscheidung über die Erfüllbarkeit einer aussagenlogischen Formel, also des SAT-Problems, und darauf aufbauend die NP-Vollständigkeit einer Reihe weiterer Entscheidungsprobleme nachgewiesen. Die Problemauswahl ist zum Teil eine Geschmacksfrage. Wesentliche Kriterien sind die Bedeutung des Resultats in der praktischen Anwendung sowie die Auseinandersetzung mit bestimmten Techniken für Reduktionsbeweise. Die Auseinandersetzung mit weiteren Komplexitätsklassen jenseits von P und NP beschränkt sich darauf, den Blick in ein Gebiet der theoretischen Informatik zu eröffnen, in dem es noch zahlreiche ungelöste Probleme gibt.

Bei der Auswahl des Stoffes für das Kap. 15 über formale Sprachen haben wir uns auf den Nachweis zentraler Eigenschaften konzentriert. Der Abschnitt über deterministische Sprachen liefert einerseits Anwendungsbeispiele für die in den Beweisen der vorangehenden Abschnitte benutzten Konstruktionsmethoden für Automaten; andererseits behandelt er die Grundlagen der Syntaxanalyse mit LR(k)- und LL(k)-Grammatiken, die wegen ihrer allgemeinen Bedeutung nicht erst in Übersetzerbauvorlesungen gebracht werden sollten.

Letztlich ist die Ausführung eines Programms auf einem Rechner eine Simulation im Sinne des in den Kap. 13 - 15 benutzten Simulationsbegriffs; die Übersetzung des Programms aus einer Spezifikation oder höheren Programmiersprache definiert das Simulationsverfahren. Die Übersetzung ist korrekt, wenn das übersetzte Programm das Gleiche leistet wie das ursprüngliche Programm, wenn also die semantische Äquivalenz nachgewiesen wird. Die theoretische Informatik hat mit Turingmaschinen und den anderen Berechenbarkeitsbegriffen die Bedeutung eines Programms auf die elementare Manipulation von Zeichenreihen oder ganzen Zahlen reduziert, weshalb in diesem Bereich die Korrektheit der Simulationen relativ leicht nachzuweisen ist.

Das Kap. 16 über Programmtransformationen zeigt, daß die semantische Äquivalenz solcher Simulationen zahlreiche und oft schwer nachweisbare Nebenbedingungen erfordert, wenn man die Simulation tatsächlich programmieren muß. Die Probleme, die sich in der praktischen Anwendung zusätzlich aus Ressourcenbeschränkungen wie der Beschränktheit der Zahldarstellung und der Speicherkapazität ergeben, und, auf die wir hier nicht eingehen, verschärfen dieses Problem noch.

Daneben soll dieses Kapitel dem Leser bewußt machen, daß die zahlreichen Programmumformungen, die man in der täglichen Arbeit vornimmt, eine systematische und genau beschreibbare Grundlage haben. Schließlich bilden die hier aufgeführten Transformationsschemata die Grundlage, auf der zahlreiche weiterführende Quelle-zu-Quelle-Transformationen aufbauen, die wir bei der Übersetzung funktionaler oder logischer Programmiersprachen und bei der Transformation von Spezifikationen in ausführbare Form benutzen. Das Problem ist nicht auf den Übersetzerbau im engeren Sinne beschränkt: Auch die Umsetzung von html-Text in eine ansprechende Web-Seite oder die Umkodierung einer Zeichnung in Postskript sind Anwendungen von Transformationsschemata, bei denen dann allerdings der Begriff der semantischen Äquivalenz anders definiert ist.

Das Thema Programmtransformationen schlägt zugleich die Brücke zu den restlichen Kapiteln, die formalen Spezifikationen gewidmet sind. Das Beiwort formal weist darauf hin, daß Spezifikationstechniken auf Techniken der theoretischen Informatik aufsetzen, und suggeriert, daß es hier etwas zu beweisen gibt. Ersteres ist nicht nur für die von uns ausgewählten Spezifikationstechniken Z und statecharts richtig.

Hingegen resultiert die Bedeutung formaler Spezifikationen nur zum Teil aus der Möglichkeit, zu verifizieren, daß das schlußendlich konstruierte Programm der Spezifikation genügt, also eine Simulation derselben darstellt. Wie die Erfahrungen in der Industrie, namentlich auch in Großbritannien, zeigen, sind Spezifikationstechniken vor allem Hilfsmittel, um in der Anforderungsanalyse und den frühen Stadien eines Systementwurfs die Erkenntnisse über ein Anwendungsproblem und seine Anforderungen klar und präzise zu formulieren.

Spezifikationen beschreiben immer nur eine Teilansicht des zu konstruierenden Systems; insbesondere nicht-funktionale Anforderungen wie Zeitbedingungen, Einhaltung sonstiger Ressourcenbeschränkungen, bestimmte Zuverlässigkeitsanforderungen, usw. werden oft nicht erfaßt. Die Entwicklung einer neuen Spezifikationstechnik, die bestimmte Nachteile vorhandener Methoden vermeidet, ist daher ein beliebtes Forschungsthema. Die daraus entstandene Flut verschiedener Spezifikationsverfahren hat den praktischen Gebrauch eher erschwert als erleichtert: Wenn jeder Fachmann eine andere Meinung über die Qualität eines Verfahrens äußert, kann man dem verantwortlichen Hochschullehrer in Automatisierungstechnik oder Manager, der über die Auswahl eines Verfahrens entscheiden soll, nicht übelnehmen, wenn er seine Finger von allen Verfahren läßt.

Die Wahl von Z und statecharts als Spezifikationstechniken, die in den Kapiteln 17 und 18 vorgestellt werden, folgt daher dem Kriterium, daß sich diese Methoden trotz der auch ihnen eigenen Unzulänglichkeiten und Beschränkungen bei größeren Aufgaben außerhalb des Bereichs der Forschung über Spezifikationstechniken bewährt haben. Dabei handelt es bei Z in erster Linie um eine Notation zur Dokumentation von Spezifikationen, während man aus statecharts-Spezifikationen auch sehr erfolgreich ausführbaren Code erzeugen kann.

Die Beschäftigung mit formalen Spezifikationen wird gemeinhin der Programmiertechnik zugerechnet. In Wahrheit sind die meisten Verfahren auf beliebige diskrete Systeme anwendbar, insbesondere solche, die auch Hardwarekomponenten umfassen. Dies wird auch aus den Beispielen in Kap. 17 und 18 deutlich, die keine reinen Softwareprobleme darstellen.

Schließlich sei betont, daß sich der Wert von Spezifikationen oft erst dann erweist, wenn der Schwierigkeitsgrad oder der Umfang die Übersicht über das zu lösende Problem beeinträchtigt. Gut verstandene oder kleine Beispiele dienen daher der Einübung der Spezifikationstechniken. Sie können jedoch nicht die Einsicht über den Wert des Gebrauchs formaler Spezifikationen befördern. Beim Gebrauch des Buches in Vorlesungen ist es daher wesentlich, daß die begleitenden Übungen auch nicht elementare Spezifikationsaufgaben stellen. Beispiele dafür gibt es in der in 17 und 18 zitierten Literatur in großer Anzahl.

Zu dem in diesem Buch behandelten theoretischen Stoff, einschließlich Programmtransformationen, gibt es zahlreiche sehr gute, vertiefende Lehrbücher, die in Teilen auch als Vorbild bei der Abfassung der Kap. 13-15 dienten. Auch zu Z gibt es mehrere gute englischsprachige Bücher, die aber neben Fallstudien vor allem die Einübung der für den Praktiker ungewohnten mengentheoretischen und prädikatenlogischen Notation zum Gegenstand haben. Für die Darstellung von statecharts wurde auf die Originalliteratur zurückgegriffen. Die Firma Berner&Mattner stellte freundlicherweise eine Lizenz von STATEMATE von i-Logix für die Beispiele und Bilder in Kap. 18 zur Verfügung.

Beim Schreiben dieses Buches haben mich meine Mitarbeiter Andreas Heberle und Martin Trapp sowie Dr. Wolf Zimmermann, Dr. Uwe Aßmann, Jörn Eisenbiegler, Thilo Gaul, Daniela Genius, Sabine Glesner, Thomas Lindner, Rainer Neumann und Martin Spott tatkräftig unterstützt. Die ersten drei Kapitel gehen auf eine erste Ausarbeitung von Herrn Zimmermann zurück. Den Kollegen Jan van Leeuwen und Roland Vollmar danke ich für die Durchsicht von Teilen des Manuskripts, zahlreiche nützliche Hinweise und Verbesserungsvorschläge. Die Mitarbeiter des Springer-Verlags haben mich nach Kräften bei der Gestaltung des endgültigen Textes beraten. Nicht zuletzt möchte ich mich bei meiner Frau für die Durchsicht des Manuskripts und die Nachsicht und Geduld bedanken, mit der sie die Arbeit auch an diesem Buch ertrug.

Karlsruhe, im Juli 1997 Gerhard Goos


Zur Heimatseite

Inhaltsverzeichnis Band 3

13 Berechenbarkeit
13.1 Der Algorithmusbegriff und die Churchsche These
13.2 loop-, while- und goto-Algorithmen
13.2.1 loop-Algorithmen
13.2.2 Makros
13.2.3 while-Algorithmen
13.2.4 goto-Algorithmen
13.3 Turingmaschinen
13.3.1 Zusammengesetzte Turingmaschinen
13.3.2 Mehrbändrige Turingmaschinen
13.3.3 Nicht-deterministische Turingmaschinen
13.3.4 Universelle Turingmaschinen und das Halteproblem
13.4 Primitiv und Mü-rekursive Funktionen
13.5 Das Postsche Korrespondenzproblem
13.6 Anmerkungen und Verweise
14 Komplexitätstheorie
14.1 Klassifikation
14.2 Beispielprobleme
14.3 Die Klasse NP
14.3.1 Die NP-Vollständigkeit von SAT
14.3.2 Andere NP-vollständige Probleme
14.4 Weitere Komplexitätsklassen
14.5 Anmerkungen und Verweise
15 Formale Sprachen
15.1 Reguläre Sprachen und endliche Automaten
15.1.1 Abschlußeigenschaften und Entscheidbarkeit
15.2 Kontextfreie Sprachen
15.2.1 Eigenschaften
15.2.1.1 Normalformen kontextfreier Grammatiken
15.2.1.2 Der Satz von Parikh und verwandte Sätze
15.2.1.3 Entscheidbarkeitseigenschaften
15.2.2 Nicht-deterministische Kellerautomaten
15.2.3 Deterministische kontextfreie Sprachen
15.2.3.1 LR(k)-Zerteilung
15.2.3.2 LL(k)-Zerteilung
15.3 Kontextsensitive Sprachen
15.4 Anmerkungen und Verweise
16 Programmtransformationen
16.1 Transformationsschemata
16.2 Elementare Transformationsregeln
16.3 Entrekursivierung
16.4 Transformation in rechtsrekursive Form
16.5 Beispiele
16.6 Anmerkungen und Verweise
17 Spezifikationstechniken: Die Z Notation
17.1 Spezifikation und Systementwicklung
17.2 Grundbegriffe der Z Notation
17.2.1 Uuml;bersicht
17.2.2 Schemata
17.2.3 Schemata als Typen
17.2.4 Operationen auf Schemata
17.2.5 Generische Schemata und Definitionen
17.2.6 Weitere Elemente von Spezifikationen
17.3 Datenstrukturen
17.4 Verfeinerung
17.5 Beispiel Fertigungszelle
17.5.1 Beschreibung der Fertigungszelle
17.5.1.1 Zuführband
17.5.1.2 Hubdrehtisch
17.5.1.3 Roboter
17.5.1.4 Presse
17.5.1.5 Ablageband
17.5.1.6 Aktuatoren und Sensoren
17.5.1.7 Sicherheitsforderungen
17.5.2 Die Spezifikation
17.5.2.1 Die Komponenten
17.5.2.2 Zusammensetzung der Komponenten
17.5.2.3 Fehlerbehandlung
17.6 Anmerkungen und Verweise
18 Ablaufspezifikationen, Synchronisierung und Kommunikation
18.1 Grundbegriffe von Statecharts
18.1.1 Ereignisse und Bedingungen, Aktionen und Tätigkeiten
18.1.2 Zeitlicher Ablauf
18.2 Spezifikation einer digitalen Armbanduhr
18.3 Konstruktionsprinzipien
18.3.1 Sequentielle Systeme
18.3.2 Nebenläufige Systeme
18.4 Synchrone und asynchrone Kommunikation
18.4.1 Synchrone Kommunikation zwischen Prozessoren
18.4.2 Speichergestützte Kommunikation, Semaphore
18.5 Kanäle
18.5.1 Kommunikation im Netz
18.6 Anmerkungen und Verweise


Zur Heimatseite

Band 4
Parallelität und nicht-analytische Lösungsverfahren

Vorwort

Der vorliegende vierte Band der Reihe Vorlesungen über Informatik entstand aus Vorlesungen an der Universität Karlsruhe. Er behandelt parallele Rechenverfahren und Problemlösungsmethoden, die nicht auf ein mathematisches Lösungsmodell im üblichen Sinne zurückgreifen, und baut in vielfältiger Weise auf den Ergebnissen der Vorgängerbände auf, die meist nur mit Angabe der Abschnittsnummern zitiert werden.

Kap. 19 ist dem Thema paralleles Rechnen gewidmet. Zerlegung in parallel ausführbare Teile ist wie rekursive Problemzerlegung eines der Grundprinzipien der Informatik. Dementsprechend stehen in diesem Kapitel nicht so sehr die technischen Möglichkeiten von Parallelrechnern, sondern die Info4-Cover abstrakten Modelle solcher Rechner als Grundlage für den Entwurf paralleler Algorithmen im Vordergrund. Daran schließen sich Entwurfsmethoden an, die vor allem zeigen, daß parallele Algorithmen nicht nur durch Parallelisierung von Schleifen aus sequentiellen Programmen entstehen.

Viele parallele Algorithmen kann man in Netzen von Arbeitsplatzrechnern ausführen, wenn die erforderliche Kommunikationsbandbreite zur Verfügung steht. Insoweit besteht zwischen einem echten Parallelrechner und der Parallelarbeit in einem verteilten System kein prinzipieller Unterschied. Die ausführliche Behandlung der Abbildung planbarer paralleler Algorithmen auf das LogP-Modell resultiert aus der Erfahrung, daß ein sehr großer Teil der parallelen Programme im wissenschaftlichen Rechnen planbar ist; die vorgestellte Methodik liefert zusätzliche Leistungssteigerungen gegenüber herkömmlichen Implementierungsmethoden.

Der Engpaß vieler paralleler Programme ist nicht die Rechenleistung, sondern die zum Transport und zur Speicherung immenser Datenmengen erforderliche Kommunikationsbandbreite. Nicht die geschickte Verteilung der Arbeit auf die Prozessoren, sondern die geschickte Verteilung der Daten entscheidet in den meisten Fällen über den Erfolg. Daher sind optimale Lösungen auch gewöhnlich nicht für beliebige Prozessorzahlen p skalierbar, wie man dies fälschlicherweise vielleicht aufgrund der vorgestellten theoretischen Resultate vermuten möchte: Mit steigender Prozessorzahl ändern sich die Engpässe des Kommunikationssystems; Lösungen, die vielleicht bei p=16 tauglich erschienen, sind es für 256 Prozessoren vielleicht nicht mehr.

Die in Kap. 20 behandelten Zellularautomaten erscheinen vordergründig als Spezialfall eines massiv parallelen Rechenmodells im Sinne des vorangehenden Kapitels. Entscheidend ist aber der folgende Ansatz zum Problemlösen: Die Zellen eines Zellularautomaten unterscheiden nicht zwischen dem Ausführungszustand ihres Programms und den dazu benötigten Daten. Auch können sie wegen der ausschließlich lokalen Kommunikationsbeziehungen keinerlei Überblick über den globalen Zustand einer Berechnung gewinnen. Daß sich aus lokalen Verhaltensweisen global sichtbare systematische Entwicklungen ergeben, ist eine Erfahrung, die man in vielen physikalischen und sozialen Systemen machen kann. Zellularautomaten sind ein formales Hilfsmittel, um solche Phänomene zu studieren. Die Anwendungen zeigen, daß man mit ihnen vor allem auch solche Systeme simulieren kann.

Das Thema der weiteren Kapitel heißt heute im Amerikanischen Soft Computing oder Computational Intelligence. Gemeinhin zählt man hierzu die Gebiete künstliche neuronale Netze, evolutionäre Algorithmen sowie unscharfes Schließen, denen auch die Kapitel 21-23 gewidmet sind. Den Themenbereichen ist das natürliche Vorbild gemein: Auslöser ist die Beobachtung von Mechanismen in Biologie, Physik, Chemie und sozialen Systemen, die sich natürlich entwickelt und als erfolgreich erwiesen haben. Grundtechnik ist die Nachahmung dieser Mechanismen.

Biologen, Philosophen und Physiker befassen sich mit diesem Thema und versuchen damit menschliches Denken aus seiner vermuteten biologischen Arbeitsweise heraus zu erklären. Für den Informatiker und Ingenieur sind neben dem Erkenntnisgewinn vor allem Gesichtspunkte wichtig, wie sie Lotfi A. Zadeh (1994) in seiner Definition von Soft Computing betont:

The real world is pervasively imprecise and uncertain. Precision and certainty carry a cost. The guiding principle of soft computing is: Exploit the tolerance for imprecision, uncertainty, and partial truth to achieve tractability, robustness, and low solution cost
Hierauf weist auch der Untertitel nicht-analytische Lösungsverfahren des Buches hin: Analytische Modellbildung auf mathematischer Grundlage verlangt bei vielen Problemen nur schwer oder gar nicht zugängliche Informationen, ohne daß die Genauigkeit der Lösung irgendeinen signifikanten Vorteil gegenüber einer ungenaueren Lösung hätte, die mit wesentlich geringerem Aufwand zu erreichen ist. Methoden des Soft Computing sind darüber hinaus auch bei Problemen einsetzbar, für die überhaupt keine analytischen Modelle verfügbar oder denkbar sind. Man spricht daher oft von modellfreien Verfahren, obwohl in Wahrheit klar definierte Rechenmodelle vorliegen.

Bei der Auswahl des Stoffes für das Kap. 21 standen naturgemäß die praktisch wichtigen Verfahren zum überwachten Lernen in vorwärtsgerichteten Netzen im Vordergrund. Beim unüberwachten Lernen werden Kohonen-Karten und Hopfield-Netze ausführlich behandelt; viele weiterführende Konzepte bleiben unberücksichtigt.

Kap. 22 über zufallsgesteuerte Optimierung beginnt mit Gradientenverfahren. Diese deterministischen Verfahren gehören eigentlich nicht unter die Kapitelüberschrift, werden aber als Grundlage in weiteren Verfahren benötigt; beim Gebrauch in Vorlesungen kann man diesen Abschnitt auch als Exkurs vor 21 einschieben, wo sie ebenfalls angewandt werden. Der praktische Einsatz der weiteren Verfahren wie simuliertes Tempern, Evolutionsstrategien und genetische Algorithmen verlangt Erfahrung bei der Problem-Codierung und der zweckmäßigen Wahl der Parameter, die in einer Einführung nur unzureichend vermittelt werden kann.

Kap. 23 über unscharfe Informationsverarbeitung konzentriert sich zuerst auf unscharfe Mengen und Relationen, um diese dann bei Aufgaben der unscharfen Regelung einzusetzen. Abschließend werden kursorisch unscharfe Maße behandelt. In Vorlesungen kann man auch unscharfe Maße an den Anfang stellen und von da zu unscharfen Mengen und unscharfer Logik übergehen.

Viele weiterführende Hinweise und praktische Beispiele zu den hier behandelten Themen findet man heute auf dem Internet. Wir haben daher an einigen Stellen Netz-Adressen angegeben, obwohl solche Adressen schnellebiger sind als ein Buch.

Beim Schreiben dieses Buches haben mich meine Mitarbeiter Andreas Heberle und Martin Trapp tatkräftig unterstützt. Das erste Kapitel geht auf eine erste Ausarbeitung der Herren Dr. Wolf Zimmermann und Dr. Welf Löwe, das zweite Kapitel auf Herrn Dr. Thomas Worsch und die restlichen Kapitel auf Herrn Dr. Joachim Weisbrod und Herrn Martin Spott zurück. Ihnen und den Mitarbeitern Dr. Uwe Aßmann, Jörn Eisenbiegler, Thilo Gaul, Daniela Genius, Thomas Lindner, Andreas Ludwig und Rainer Neumann danke ich für die Mitarbeit und Durchsicht der einzelnen Kapitel, aus denen viele Korrekturen und Verbesserungen resultierten. Den Kollegen Wolfgang Banzhaf, Peter Lockemann, Alfred Schmitt, Hans-Paul Schwefel, Theo Ungerer und Roland Vollmar sowie den Herren Dr. Jürgen Goos und Dr. Martin Riedmiller danke ich für die Durchsicht von Teilen des Manuskripts, zahlreiche nützliche Hinweise und Verbesserungsvorschläge. Die Mitarbeiter des Springer-Verlags, allen voran Herr Engesser, Frau Georgiadis und Herr Straßer, haben mich auch bei diesem Band und seiner endgültigen Gestaltung tatkräftig unterstützt. Nicht zuletzt bedanke ich mich bei meiner Frau für die Durchsicht des Manuskripts und die Nachsicht und Geduld, mit der sie die Arbeit auch an diesem Buch ertrug.

Karlsruhe, im März 1998 Gerhard Goos


Zur Heimatseite

Inhaltsverzeichnis Band 4

19 Paralleles Rechnen
19.1 Parallele Rechenmodelle
19.1.1 Die parallele Registermaschine
19.1.1.1 Aufwandsmaße
19.1.2 Datenflußmodell
19.1.2.1 Sortiernetze
19.1.3 Abstrakte Netzwerkmodelle
19.1.3.1 Das BSP-Modell
19.1.3.2 Das LogP-Modell
19.2 Technische Modelle
19.2.1 Klassifikation von Parallelrechnern
19.2.2 Vektorrechner
19.2.3 Gemeinsamer Speicher
19.2.4 Verbindungsnetzwerke
19.2.4.1 Bussysteme, Kreuzschienen, Permutationsnetze
19.2.4.2 Sternförmige Netzwerke
19.2.4.3 Lineare Reihungen und Ringe
19.2.4.4 Zweidimensionale Gitter und Tori
19.2.4.5 Hyperwürfel
19.2.4.6 Bäume
19.2.5 Abbildung von PRAM- auf LogP-Algorithmen
19.2.6 PVM und MPI
19.3 Entwurfstechniken für parallele Algorithmen
19.3.1 Die Komplexitätsklasse NC
19.3.2 Paralleles Teile-und-Herrsche
19.3.2.1 Bitones Sortieren
19.3.2.2 Schnelle Fouriertransformation
19.3.3 Ausgewogene Bäume
19.3.4 Präfixgraphen
19.3.5 Zeigerspringen
19.3.6 Die Euler-Tour
19.4 Anmerkungen und Verweise
20 Zellularautomaten
20.1 Grundlagen
20.2 LIFE: Das Spiel des Lebens
20.3 Turing-Mächtigkeit
20.4 Anwendungen
20.4.1 Ein Synchronisierungsproblem
20.4.2 Modelle aus Differentialgleichungen
20.4.3 Gittergase
20.4.4 Verkehrssimulation
20.5 Anmerkungen und Verweise
21 Künstliche neuronale Netze
21.1 Neuronen
21.1.1 Das biologische Vorbild
21.1.2 Künstliche Neuronen
21.2 Zur Konstruktion von KNNs
21.2.1 Einsatzbedingungen
21.2.2 Lernen statt Programmieren
21.3 Vorwärtsgerichtete Netze
21.3.1 Das einfache Perzeptron
21.3.2 Das mehrschichtige Perzeptron
21.3.2.1 Lernen durch Rückkopplung
21.3.2.2 Adaptive Rückkopplung
21.4 Unüberwachtes Lernen
21.4.1 Wettlernen
21.4.2 Topologie-erhaltende Karten
21.5 Hopfield-Netze
21.5.1 Synchrone Hopfield-Netze
21.5.2 Asynchrone Hopfield-Netze
21.6 Anwendungen
21.7 Anmerkungen und Verweise
22 Zufallsgesteuerte Optimierung
22.1 Optimierungsaufgaben
22.1.1 Schrittweise Optimierung
22.1.2 Gradientenverfahren
22.2 Stochastische Optimierung
22.2.1 Simuliertes Tempern
22.2.2 Tempern mit deterministischer Akzeptanz
22.3 Evolutionäre Algorithmen
22.3.1 Evolutionsstrategien
22.3.2 Genetische Algorithmen
22.3.3 Evolutionsstrategien und genetische Algorithmen im Vergleich
22.4 Anmerkungen und Verweise
23 Unscharfe Informationsverarbeitung
23.1 Unscharfe Mengen
23.1.1 Grundoperationen auf unscharfen Mengen
23.1.2 Allgemeinere unscharfe Mengen
23.2 Unscharfe Relationen
23.2.1 Max-Min Komposition und Erweiterungsprinzip
23.2.2 Relationengleichungen
23.3 Unscharfe Regelung
23.3.1 Entwurf unscharfer Regler
23.4 Unscharfe Maße
23.4.1 Maßbasen
23.4.2 Glaubwürdigkeits- und Plausibilitätsmaße
23.4.3 Möglichkeits- und Notwendigkeitsmaße
23.4.4 Klassifikation unscharfer Maße
23.4.5 Möglichkeitsmaße und unscharfe Mengen
23.4.6 Unscharfe Maße in der Anwendung
23.5 Anmerkungen und Verweise Literaturverzeichnis
D Fourierreihen und Fouriertransformation
D.1 Fourierreihen
D.2 Fouriertransformation
D.2.1 Eigenschaften von Fouriertransformierten und Fourierreihen
D.2.2 Das Abtasttheorem
D.3 Diskrete Fouriertransformation
D.3.1 Polynommultiplikation
D.3.2 Schnelle Fouriertransformation
D.4 Anmerkungen und Verweise


Zur Heimatseite

Kommentare und Problemmeldungen bitte an TG. Springer-Verlag Heidelberg Heimatseite Prof. Goos Heimatseite Prof. Goos Heimatseite Prof. Goos Heimatseite Prof. Goos Band1: Grundlagen und funktionales Programmieren Band2: Objektorientiertes Programmieren und Algorithmen Band3: Berechenbarkeit, formale Sprachen und Spezifikationen Band4: Parallelität und nicht-analytische Lösungsverfahren