Algorithmen und Datenstrukturen E-Book

Gunter Saake

• Herausgeber: dpunkt.verlag
• Kategorie: Wissenschaft und neue Technologien
• Sprache: Deutsch
• Veröffentlichungsjahr: 2020

Seitenzahl: 737

Beschreibung

Algorithmen und Datenstrukturen von Grund auf verstehen

• Fundierte Einführung mit klarem didaktischen Aufbau
• Mit konkreten Anwendungsbeispielen
• Eine reichhaltige Fundgrube für Lehre und Selbststudium

Kenntnisse von Algorithmen und Datenstrukturen sind ein Grundbaustein des Studiums der Informatik und verwandter Fachrichtungen. Das Buch behandelt diese Thematik in Verbindung mit der Programmiersprache Java und schlägt so eine Brücke zwischen den klassischen Lehrbüchern zur Theorie von Algorithmen und Datenstrukturen und den praktischen Einführungen in eine konkrete Programmiersprache.

Die konkreten Algorithmen und deren Realisierung in Java werdenumfassend dargestellt. Daneben werden die theoretischen Grundlagen vermittelt, die in Programmiersprachen-Kursen oft zu kurz kommen: abstrakte Maschinenmodelle, Berechenbarkeit, Algorithmenparadigmen sowie parallele und verteilte Abläufe. Einen weiteren Schwerpunkt bilden Datenstrukturen wie Listen, Bäume, Graphen und Hashtabellen sowie deren objektorientierte
Implementierung mit modernen Methoden der Softwareentwicklung.

Die 6. Auflage führt einige neue Algorithmen ein und berücksichtigt die Neuerungen der aktuellen Java-Versionen, u.a. zu Themen wie Parallelisierung.

Leseprobe

Gunter Saake ist Professor für Datenbanken und Informationssysteme an der Otto-von-Guericke-Universität Magdeburg und forscht unter anderem auf den Gebieten Datenbankintegration, digitale Bibliotheken, objektorientierte Informationssysteme und Informationsfusion. Er ist Koautor mehrerer Lehrbücher, u. a. zu Datenbankkonzepten und -implementierungstechniken, Datenbanken & Java.

Kai-Uwe Sattler ist Professor für Datenbanken und Informationssysteme an der TU Ilmenau. Zu seinen Arbeitsgebieten zählen Anfrageverarbeitung sowie Architekturen, Datenstrukturen und Algorithmen für das Datenmanagement auf Basis moderner Hardwaretechnologien. Er ist Koautor mehrerer Lehrbücher zu Datenbankkonzepten, -architekturen und -implementierungstechniken.

Zu diesem Buch – sowie zu vielen weiteren dpunkt.büchern – können Sie auch das entsprechende E-Book im PDF-Format herunterladen. Werden Sie dazu einfach Mitglied bei dpunkt.plus+:

www.dpunkt.plus

Gunter Saake · Kai-Uwe Sattler

Algorithmen undDatenstrukturen

Eine Einführung mit Java

6., überarbeitete und erweiterte Auflage

Prof. Dr. Gunter Saake

Institut für Technische und Betriebliche Informationssysteme

Otto-von-Guericke-Universität Magdeburg

Universitätsplatz 2, 39106 Magdeburg

E-Mail: [email protected]

Prof. Dr. Kai-Uwe Sattler

Fakultät für Informatik und Automatisierung

FG Datenbanken und Informationssysteme

Technische Universität Ilmenau

PF 100565, 98684 Ilmenau

E-Mail: [email protected]

Lektorat: Christa Preisendanz

Copy-Editing: Ursula Zimpfer, Herrenberg

Satz: Kai-Uwe Sattler, Ilmenau

Herstellung: Stefanie Weidner

Umschlaggestaltung: Helmut Kraus, www.exclam.de

Bibliografische Information der Deutschen Nationalbibliothek

Die Deutsche Nationalbibliothek verzeichnet diese Publikation in der Deutschen Nationalbibliografie; detaillierte bibliografische Daten sind im Internet über http://dnb.d-nb.de abrufbar.

ISBN:

Print    978-3-86490-769-2

PDF     978-3-96910-066-0

ePub   978-3-96910-067-7

mobi   978-3-96910-068-4

6., überarbeitete und erweiterte Auflage 2021

Copyright © 2021 dpunkt.verlag GmbH

Wieblinger Weg 17

69123 Heidelberg

Hinweis:

Dieses Buch wurde auf PEFC-zertifiziertem Papier aus nachhaltiger Waldwirtschaft gedruckt. Der Umwelt zuliebe verzichten wir zusätzlich auf die Einschweißfolie.

Schreiben Sie uns:

Falls Sie Anregungen, Wünsche und Kommentare haben, lassen Sie es uns wissen: [email protected].

Die vorliegende Publikation ist urheberrechtlich geschützt. Alle Rechte vorbehalten. Die Verwendung der Texte und Abbildungen, auch auszugsweise, ist ohne die schriftliche Zustimmung des Verlags urheberrechtswidrig und daher strafbar. Dies gilt insbesondere für die Vervielfältigung, Übersetzung oder die Verwendung in elektronischen Systemen.

Es wird darauf hingewiesen, dass die im Buch verwendeten Soft- und Hardware-Bezeichnungen sowie Markennamen und Produktbezeichnungen der jeweiligen Firmen im Allgemeinen warenzeichen-, marken- oder patentrechtlichem Schutz unterliegen.

Alle Angaben und Programme in diesem Buch wurden mit größter Sorgfalt kontrolliert. Weder Autor noch Verlag können jedoch für Schäden haftbar gemacht werden, die in Zusammenhang mit der Verwendung dieses Buches stehen.

5 4 3 2 1 0

Vorwort

Seit der letzten Auflage des Buches sind fast 7 Jahre vergangen – eine lange Zeit für ein schnelllebiges Gebiet wie die Informatik. So ist die Java-Umgebung mittlerweile bei Version 14 angelangt, das Java-Ökosystem ist deutlich diverser geworden und Themen wie neuronale Netze, die wir schon in der ersten Auflage des Buches als ein Paradigma behandelt haben, die aber über viele Jahre eher ein Randthema waren, sind aktuell im Kontext von künstlicher Intelligenz und »Deep Learning« in aller Munde.

Dennoch ist es unserer Meinung nach weiterhin notwendig, sich in der Informatik mit grundlegenden Themen wie Algorithmen und Datenstrukturen zu beschäftigen. Auch Java ist trotz aller Konkurrenz durch Sprachen wie Python, Scala, Kotlin, Swift oder Rust nach wie vor ein geeignetes Mittel zum Erlernen einer ersten Programmiersprache.

Daher haben wir auch mit dieser Auflage des Buches versucht, zum einen gezielt einige wichtige und interessante Datenstrukturen und Algorithmen (z.B. Skip-Listen, weitere Hashverfahren und Graphalgorithmen) aufzunehmen und zum anderen relevante Neuerungen von Java aus den letzten Jahren zu berücksichtigen. Unser Fokus liegt aber weiterhin auf Algorithmen und Datenstrukturen – die Programmiersprache Java ist nur das Werkzeug.

Mit der Überarbeitung des Buches haben wir auch die Beispielprogramme aktualisiert. Der Quellcode der Beispiele ist jetzt zeitgemäß auf GitHub unter

https://github.com/ksattler/algoj

zu finden.

Unser Dank gilt allen Leserinnen und Lesern, die durch Hinweise, Kommentare und Kritiken geholfen haben, Fehler zu korrigieren und Verbesserungen vorzunehmen. Weiterhin bedanken wir uns bei allen, die uns unterstützt haben: unseren Familien und natürlich auch dem dpunkt.verlag.

Magdeburg und Ilmenau, September 2020

Gunter Saake und Kai-Uwe Sattler

Vorwort zur 5. Auflage

Auch mit der nunmehr 5. Auflage des Buches haben wir versucht, unserem Ziel treu zu bleiben, den Rahmen einer zweisemestrigen Einführungsvorlesung in das Thema Algorithmen, Datenstrukturen und Java nicht zu sprengen. Natürlich hat jeder Dozent seine Vorlieben für bestimmte Themen und so wird man auch weiterhin vielleicht den einen oder anderen Algorithmus oder eine ganz bestimmte Datenstruktur vermissen.

In gleicher Weise haben wir bei der Überarbeitung die mit jeder neuen Java-Version eingeführten oder angekündigten Erweiterungen eher zurückhaltend berücksichtigt. Gerade beim Erlernen des Programmierens und einer Programmiersprache ist es oft einfacher, zunächst mit einem kleinen Kern von Sprachelementen zu beginnen – die »bells and whistles« erschließen sich dann später recht schnell.

So enthält die 5. Auflage als Neuerungen »nur« einen Überblick zu den mit Java 8 eingeführten Lambda-Ausdrücken, die eine schöne Anwendung des applikativen (funktionalen) Paradigmas darstellen, sowie neue Beispiele, die aus dem Einsatz des Materials in einigen Einführungsvorlesungen entstanden sind. Natürlich haben wir ebenfalls versucht, Feedback und Fehlerkorrekturen zu berücksichtigen, und möchten uns dafür bei unseren Lesern – ganz speziell bei Niklas Peter und Jan Sellner – bedanken.

Magdeburg und Ilmenau, Oktober 2013

Gunter Saake und Kai-Uwe Sattler

Vorwort zur 4. Auflage

Nach fast 5 Jahren Bestand der 3. Auflage war es an der Zeit, wieder einmal eine Überarbeitung vorzunehmen. Auch wenn die relevanten Änderungen an der Programmiersprache Java eher marginal sind – die Java-Plattform hat sich dagegen sehr viel weiter entwickelt, aber das ist für ein Buch dieser Art weniger von Bedeutung –, haben wir einige Hinweise und eigene Lehrerfahrungen integriert. Unser Anliegen bleibt jedoch weiterhin ein Begleitbuch für Erst- und Zweitsemester in Informatik-lastigen Studiengängen: Weder wollten wir den Umfang durch Aufnahme einer Vielzahl weiterer Algorithmen und Datenstrukturen sprengen noch im Interesse von Überblicksvorlesungen oder Programmierkursen abspecken. Wir haben in dieser Auflage als neue Algorithmen den für die Routenplanung wichtigen A*-Algorithmus und die Levenshtein-Distanz zum Ähnlichkeitsvergleich von Texten aufgenommen. Weiterhin ist für den B-Baum nun auch eine einfache Beispielimplementierung angegeben. Auf die Neuerungen der seit der 3. Auflage eingeführten Sprachversion 6.0 sowie der für Ende 2010 geplanten Version Java SE 7.0 wird an geeigneter Stelle eingegangen.

Schließlich möchten wir allen Lesern (Studierenden wie Kollegen) danken, die uns wertvolles Feedback geliefert haben.

Magdeburg und Ilmenau, April 2010

Gunter Saake und Kai-Uwe Sattler

Vorwort zur 3. Auflage

Die Nachfrage nach diesem Buch, einige in der 2. Auflage übersehene Fehler und nicht zuletzt die Weiterentwicklung der Sprache Java haben die 3. Auflage früher als erwartet notwendig gemacht. Somit beziehen sich die Neuerungen dieser Auflage im Wesentlichen auf die Vorstellung der neuen Sprachkonzepte von Java in der Version 5.0, die gerade im Zusammenhang mit Datenstrukturen wie Feldern oder Listen von Bedeutung sind. Weiterhin haben wir uns bemüht, alle gemeldeten Fehler zu korrigieren. Für entsprechende Hinweise von aufmerksamen Lesern möchten wir uns an dieser Stelle ausdrücklich bedanken.

Magdeburg und Ilmenau, November 2005

Gunter Saake und Kai-Uwe Sattler

Vorwort zur 2. Auflage

Zur 1. Auflage dieses Buches haben wir eine Vielzahl von Rückmeldungen von Dozenten und Studierenden an Universitäten und Fachhochschulen, aber auch von Informatik-Lehrern an Gymnasien erhalten. Neben Lob, Kritik und Hinweisen auf einige Fehler befanden sich darunter auch einige Wünsche nach der Behandlung von Algorithmen und Datenstrukturen, die im Buch bisher fehlten. Daher haben wir uns entschlossen, für die vorliegende 2. Auflage nicht nur Fehlerkorrekturen vorzunehmen, sondern auch einige Ergänzungen aufzunehmen. So werden nun mit den genetischen Algorithmen und den neuronalen Netzen zwei weitere »Algorithmenparadigmen« vorgestellt. Weitere Neuerungen betreffen die Aufnahme von Rot-Schwarz-Bäumen, die gern als Alternative zu AVL-Bäumen behandelt werden, sowie praktische Realisierungen von Tries und erweiterbaren Hashverfahren. Dabei haben wir jedoch versucht, dem ursprünglichen Anliegen des Buches als ein Begleitwerk zu einer einführenden »Algorithmen & Datenstrukturen«-Vorlesung für Informatik-Studiengänge an Universitäten und Fachhochschulen treu zu bleiben. Dies bedeutet für uns eine gesunde Mischung aus Theorie und Praxis, wobei jedoch Themen, die normalerweise im weiteren Verlauf des Studiums noch vertiefend behandelt werden (z.B. Theoretische Informatik, Komplexitätstheorie, Objektorientierte Programmierung oder alternative Algorithmenkonzepte), nur soweit angesprochen werden, wie es für das grundlegende Verständnis von Zusammenhängen des Stoffes notwendig ist.

Abschließend gilt unser Dank speziell Ilona Blümel, Christian Borgelt, Martin Dietzfelbinger, Horst-Michael Groß und Dominik Gruntz sowie allen Lesern der 1. Auflage, die mit ihren Hinweisen und Kommentaren zur Verbesserung und somit zu der vorliegenden 2. Auflage beigetragen haben.

Magdeburg und Ilmenau, März 2004

Gunter Saake und Kai-Uwe Sattler

Vorwort zur 1. Auflage

Genese des Buches

Das vorliegende Buch entstand aus den Begleitmaterialien einer Vorlesung »Einführung in Algorithmen und Datenstrukturen«, die die Autoren an der Universität Magdeburg im Vorlesungszyklus 1999/2000 für die Studienanfänger in den Diplomstudiengängen Informatik, Wirtschaftsinformatik und Computervisualistik neu konzipierten, da erstmals diese Grundvorlesung mit praktischen Übungen in der Programmiersprache Java angeboten wurde. Neben dem in dem Buch aufbereiteten Stoff wurden Einschübe z.B. zur Realisierung relationaler Datenbanken in der Vorlesung integriert, die zur Verdeutlichung der vermittelten Techniken anhand realer Problemstellungen dienten. Diese Einschübe dürften bei anderer Gelegenheit jeweils durch Einschübe aus dem konkreten Arbeitsgebiet der Vorlesenden gewählt werden, so dass sie in diesem Buch weggelassen wurden.

Zielgruppe des Buches

Die Zielgruppe dieses Buches sind somit insbesondere Studierende in universitären Grundstudiumsvorlesungen, die einen Umfang von bis zu acht Semesterwochenstunden haben und eine Einführung in die Grundkonzepte der praktischen Informatik, begleitet durch praktische Übungen in Java, geben sollen, um das Fundament für die vertiefende Behandlung der verschiedenen Teilgebiete der praktischen Informatik zu bilden. Dabei wird davon ausgegangen, dass die mathematischen Grundlagen sowie die Konzepte der theoretischen Informatik und insbesondere der technischen Informatik in parallelen oder anschließenden separaten Vorlesungen behandelt werden.

Um den Studierenden den Zugang zu erleichtern, wurde, wenn immer es möglich und sinnvoll erschien, auf etablierte Notationen und Beispiele (etwa dem Schülerduden entnommen) zurückgegriffen.

Inhalt des Buches

Der Inhalt des Buches orientiert sich an den Inhalten vergleichbarer Studienangebote an deutschen Universitäten und den bekannten Empfehlungen zu Grundstudiumsangeboten der genannten Studiengänge. Als Besonderheiten sind zu nennen:

Einige der behandelten theoretischen Grundlagen (abstrakte Maschinenmodelle, Berechenbarkeit, Halteproblem, Algorithmenparadigmen) kommen unseren Recherchen nach oft in Programmiersprachen-gestützten Kursen zu kurz. Diese wurden bewusst aufgenommen, um durch Verknüpfung dieser Themen mit konkreter Programmierung in Java (etwa die Simulation einer Registermaschine) den Studierenden die Vernetzung dieser abstrakten Konzepte zu ermöglichen.

Entgegen anderer Vorlesungszyklen wurde die Behandlung von parallelen und verteilten Abläufen bewusst in den dem ersten Semester zugeordneten Vorlesungsteil aufgenommen.

Die Behandlung des üblichen Kanons von Basisdatenstrukturen wurde um einige, in der Praxis wichtige Verfahren und Algorithmen (spezielle Suchbäume, Graphenalgorithmen) erweitert.

Besonderheiten

Wenn man dieses Buch mit anderen Büchern für Grundlagenvorlesungen »Algorithmen und Datenstrukturen« vergleicht, erscheint es auf den ersten Blick widersprüchlich: Einerseits beinhaltet es eine ganze Reihe von Grundlagenthemen, die sich nicht stark von entsprechenden Materialien von vor 20 Jahren unterscheiden, andererseits wird mit den Abschnitten über Java-Programmierung eine der modernsten Programmiersprachen zur Illustration der Konzepte genutzt. Dieser Widerspruch ist Methode: Die Autoren wollen hiermit verdeutlichen, dass die Informatik die Reife einer Wissenschaftsdisziplin mit etablierten methodischen und theoretischen Grundlagen erlangt hat und auf einem reichen Schatz an gefestigtem Basiswissen beruht, und dieses mit dem (zum Teil spielerischen, zum Teil ernsthaften) Umgang mit Methoden und Sprachen moderner Softwareerstellung verbinden.

Das Lehrziel des Buches fußt dabei auf beiden Aspekten: Studierende sollen eine Grundlage für die theoretischen und praktischen Vertiefungen eines intensiven Hauptstudiums bekommen und diese Grundkenntnisse direkt umsetzen können in den »praktischen Alltag« des Arbeitens mit Programmen, Spezifikationen und Modellierungen. Das vorliegende Buch hat weder den Anspruch eines Basiswerkes über die Theorie der Algorithmen und Datenstrukturen, noch ist es eine reine Einführung in die Programmierung mit Java.

Einsatz des BuchesEinführung in Java

Das Buch ist in drei Teile aufgeteilt, wobei die ersten beiden Teile den Stoff des ersten Semesters abdecken. Der dritte Teil, ergänzt um spezifische Inhalte wie oben erläutert, bildet den Stoff eines dem Thema »Datenstrukturen« gewidmeten zweiten Semesters. Beide Vorlesungen sollten durch Veranstaltungen zur Einführung in die Programmiersprache Java begleitet werden, wobei der Stoff eine schrittweise Einführung über die Stufen »Java als imperative Programmiersprache«, »Funktionen und Rekursion in Java«, »Objektorientierung: Klassen und Methoden« und abschließend »Methoden des Software Engineering in Java« nahe legt. Im Laufe des zweiten Semesters sollte eine über eine längere Zeit zu bearbeitende größere Programmieraufgabe, eventuell bereits in Kleingruppen, gelöst werden oder (wie in unserer Veranstaltung) in Form eines Programmierwettbewerbs die Studierenden zur kreativen Nutzung des erarbeiteten Wissens animiert werden.

Funktionale und imperative KonzepteObjektorientierung

Die Trennung von Algorithmen und Datenstrukturen erscheint im Zeitalter von Objektorientierung auf den ersten Blick vielleicht anachronistisch. Erfahrungen der Autoren haben aber gezeigt, dass ein Zugang zu dieser Thematik gerade Studienanfängern leichter fällt, wenn der Fokus zunächst auf funktionale und imperative Konzepte zur Formulierung und Implementierung von Algorithmen gelegt wird und die (objektorientierten) Eigenschaften der Programmiersprache nur so weit wie notwendig vorgestellt werden. Probleme wie Suchen oder Sortieren lassen sich am einfachsten ohne den »Ballast« von Klassen oder Objekten erfassen. Das Verständnis für Objektorientierung ergibt sich später mit der Einführung von abstrakten Datentypen und in der praktischen Arbeit mit der Java-Klassenbibliothek. Nicht vergessen sollte man dabei auch, dass Objektorientierung nur ein Paradigma neben anderen (z.B. funktional) ist.

Der Buchstoff kann (und sollte) durch animierte Algorithmen und Datenstrukturen ergänzt und insbesondere in den Übungen durch »best practice«-Programmfragmente (und deren abschreckende Gegenstücke) vertieft werden. Auf der Webseite diese Buches findet sich ein Vorrat derartiger Ergänzungen, der laufend erweitert werden soll:

www.dpunkt.de/buch/alg_dat.html

Dort wird auch Folienmaterial zur Verfügung gestellt.

Danksagungen

Ein Buch über derartig grundlegende Themen basiert natürlich auf den Vorarbeiten und der Unterstützung einer ganzen Reihe von Personen, von denen wir hier einigen besonders danken wollen.

Die Notationen und Beispiele im Kapitel Registermaschinen sind an die Ausführungen in einem Skript von Jürgen Dassow angelehnt.

Viele Beispiele und Notationen betreffend Grundlagen und Paradigmen von Algorithmen sind durch Vorlesungsunterlagen von Hans-Dieter Ehrich beeinflusst. Dies erfolgte direkt und indirekt über Materialien von Rudolph Kruse und Gunter Saake, die ihrerseits auf den ursprünglichen Materialien von Ehrich aufbauten.

Weiterhin wollen wir allen danken, die durch Hinweise oder Korrekturlesen des Manuskriptes zum Gelingen des Buches beigetragen haben. Hier sind zuerst unsere Kollegen aus der Arbeitsgruppe Datenbanken Sören Balko, Oliver Dunemann, Martin Endig, Ingolf Geist, Hagen Höpfner, Eike Schallehn, Ingo Schmitt und Nadine Schulz zu nennen sowie alle Übungsleiter zur Vorlesung »Algorithmen & Datenstrukturen« 1999/2000, wobei wir stellvertretend Ilona Blümel hervorheben möchten, die uns mit zahlreichen Beispielen und Hinweisen unterstützt hat. Last but not least danken wir den Studierenden, die die erste Version des Skriptes im Rahmen der Vorlesung kritisch begleitet haben.

Unser Dank geht auch an unsere Lektorin Christa Preisendanz vom dpunkt.verlag, die uns anfangs zu diesem Projekt ermutigt und später mit Geduld begleitet hat, sowie an Ursula Zimpfer für die vielen Korrekturhinweise.

Der Dank von Gunter Saake gilt denjenigen aus seiner Familie und dem Bekanntenkreis, die auch bei diesem Buchprojekt in unterschiedlichem Grade unter der Bucherstellung zu leiden hatten.

Kai-Uwe Sattler dankt seinem Sohn Bennett, der aufmerksam darüber gewacht hat, dass Papas »Klackern« nicht zulasten so wichtiger Dinge wie Legobauen und Rollerfahren ging, und natürlich seiner Frau Britta, die die »Nur-noch«-Ausreden (Nur noch dieses Kapitel!, Nur noch diese Woche! etc.) dieses Mal noch länger ertragen musste und dennoch für den notwendigen Rückhalt gesorgt hat, ohne den ein Buchprojekt wohl nicht möglich wäre. Er dankt weiterhin seinen Eltern für das Verständnis, wenn gerade in der Endphase der Bucherstellung die wenigen Besuche auch noch durch das mitgebrachte Notebook gestört wurden. Ein abschließender Dank gilt Fred Kreutzmann und Steffen Thorhauer, die im Kaffeekochen inzwischen nicht nur uneinholbar vorn liegen, sondern auch ihren oftmals gestressten Bürokollegen mit Geduld ertragen haben.

Magdeburg, August 2001

Gunter Saake und Kai-Uwe Sattler

Inhaltsverzeichnis

IGrundlegende Konzepte

1Vorbemerkungen und Überblick

1.1Informatik, Algorithmen und Datenstrukturen

1.2Historischer Überblick: Algorithmen

1.3Historie von Programmiersprachen und Java

1.4Grundkonzepte der Programmierung in Java

2Algorithmische Grundkonzepte

2.1Intuitiver Algorithmusbegriff

2.1.1Beispiele für Algorithmen

2.1.2Bausteine für Algorithmen

2.1.3Pseudocode-Notation für Algorithmen

2.1.4Struktogramme

2.1.5Rekursion

2.2Sprachen und Grammatiken

2.2.1Begriffsbildung

2.2.2Reguläre Ausdrücke

2.2.3Backus-Naur-Form (BNF)

2.3Elementare Datentypen

2.3.1Datentypen als Algebren

2.3.2Signaturen von Datentypen

2.3.3Der Datentyp bool

2.3.4Der Datentyp integer

2.3.5Felder und Zeichenketten

2.4Terme

2.4.1Bildung von Termen

2.4.2Algorithmus zur Termauswertung

2.5Datentypen in Java

2.5.1Primitive Datentypen

2.5.2Referenzdatentypen

2.5.3Operatoren

3Algorithmenparadigmen

3.1Überblick über Algorithmenparadigmen

3.2Applikative Algorithmen

3.2.1Terme mit Unbestimmten

3.2.2Funktionsdefinitionen

3.2.3Auswertung von Funktionen

3.2.4Erweiterung der Funktionsdefinition

3.2.5Applikative Algorithmen

3.2.6Beispiele für applikative Algorithmen

3.3Imperative Algorithmen

3.3.1Grundlagen imperativer Algorithmen

3.3.2Komplexe Anweisungen

3.3.3Beispiele für imperative Algorithmen

3.4Das logische Paradigma

3.4.1Logik der Fakten und Regeln

3.4.2Deduktive Algorithmen

3.5Weitere Paradigmen

3.5.1Genetische Algorithmen

3.5.2Neuronale Netze

3.6Umsetzung in Java

3.6.1Ausdrücke und Anweisungen

3.6.2Methoden

3.6.3Applikative Algorithmen und Rekursion

4Literaturhinweise zum Teil I

IIAlgorithmen

5Ausgewählte Algorithmen

5.1Suchen in sortierten Folgen

5.1.1Sequenzielle Suche

5.1.2Binäre Suche

5.2Sortieren

5.2.1Sortieren: Grundbegriffe

5.2.2Sortieren durch Einfügen

5.2.3Sortieren durch Selektion

5.2.4Sortieren durch Vertauschen: BubbleSort

5.2.5Sortieren durch Mischen: MergeSort

5.2.6QuickSort

5.2.7Sortieren durch Verteilen: RadixSort

5.2.8Sortierverfahren im Vergleich

6Formale Algorithmenmodelle

6.1Registermaschinen

6.2Abstrakte Maschinen

6.3Markov-Algorithmen

6.4Church’sche These

6.5Interpreter für formale Algorithmenmodelle in Java

6.5.1Java: Markov-Interpreter

6.5.2Registermaschine in Java

7Eigenschaften von Algorithmen

7.1Berechenbarkeit und Entscheidbarkeit

7.1.1Existenz nichtberechenbarer Funktionen

7.1.2Konkrete nichtberechenbare Funktionen

7.1.3Das Halteproblem

7.1.4Nichtentscheidbare Probleme

7.1.5Post’sches Korrespondenzproblem

7.2Korrektheit von Algorithmen

7.2.1Relative Korrektheit

7.2.2Korrektheit von imperativen Algorithmen

7.2.3Korrektheitsbeweise für Anweisungstypen

7.2.4Korrektheit imperativer Algorithmen an Beispielen

7.2.5Korrektheit applikativer Algorithmen

7.3Komplexität

7.3.1Motivierendes Beispiel

7.3.2Asymptotische Analyse

7.3.3Komplexitätsklassen

7.3.4Analyse von Algorithmen

8Entwurf von Algorithmen

8.1Entwurfsprinzipien

8.1.1Schrittweise Verfeinerung

8.1.2Einsatz von Algorithmenmustern

8.1.3Problemreduzierung durch Rekursion

8.2Algorithmenmuster: Greedy

8.2.1Greedy-Algorithmen am Beispiel

8.2.2Greedy: Optimales Kommunikationsnetz

8.2.3Verfeinerung der Suche nach billigster Kante

8.3Rekursion: Divide-and-conquer

8.3.1Das Prinzip »Teile und herrsche«

8.3.2Beispiel: Spielpläne für Turniere

8.4Rekursion: Backtracking

8.4.1Prinzip des Backtracking

8.4.2Beispiel: Das Acht-Damen-Problem

8.4.3Beispiel: Tic Tac Toe mit Backtracking

8.5Dynamische Programmierung

8.5.1Das Rucksackproblem

8.5.2Rekursive Lösung des Rucksackproblems

8.5.3Prinzip der dynamischen Programmierung

9Parallele und verteilte Berechnungen

9.1Grundlagen

9.2Modell der Petri-Netze

9.2.1Definition von Petri-Netzen

9.2.2Formalisierung von Petri-Netzen

9.2.3Das Beispiel der fünf Philosophen

9.3Programmieren nebenläufiger Abläufe

9.3.1Koordinierte Prozesse

9.3.2Programmieren mit Semaphoren

9.3.3Philosophenproblem mit Semaphoren

9.3.4Verklemmungsfreie Philosophen

9.4Nebenläufige Berechnungen in Java

9.4.1Threads und wechselseitiger Ausschluss

9.4.2Parallelisierung in Java

9.4.3Das Philosophenproblem in Java

10Literaturhinweise zum Teil II

IIIDatenstrukturen

11Abstrakte Datentypen

11.1Signaturen und Algebren

11.2Algebraische Spezifikation

11.2.1Spezifikationen und Modelle

11.2.2Termalgebra und Quotiententermalgebra

11.2.3Probleme mit initialer Semantik

11.3Beispiele für abstrakte Datentypen

11.3.1Der Kellerspeicher (Stack)

11.3.2Beispiel für Kellernutzung

11.3.3Die Warteschlange (Queue)

11.4Entwurf von Datentypen

12Klassen, Schnittstellen und Objekte in Java

12.1Grundzüge der Objektorientierung

12.2Klassen und Objekte in Java

12.3Vererbung

12.4Abstrakte Klassen und Schnittstellen

12.5Ausnahmen

12.6Umsetzung abstrakter Datentypen

12.7Lambda-Ausdrücke

13Grundlegende Datenstrukturen

13.1Stack und Queue als Datentypen

13.1.1Implementierung des Stacks

13.1.2Implementierung der Queue

13.1.3Bewertung der Implementierungen

13.2Verkettete Listen

13.3Doppelt verkettete Listen

13.4Skip-Listen

13.5Das Iterator-Konzept

13.6Java Collection Framework

13.7Generics in Java

14Bäume

14.1Bäume: Begriffe und Konzepte

14.2Binärer Baum: Datentyp und Basisalgorithmen

14.2.1Der Datentyp »Binärer Baum«

14.2.2Algorithmen zur Traversierung

14.3Suchbäume

14.3.1Suchen in Suchbäumen

14.3.2Einfügen und Löschen

14.3.3Komplexität der Operationen

14.4Ausgeglichene Bäume

14.4.1Rot-Schwarz-Bäume

14.4.2AVL-Bäume

14.4.3B-Bäume

14.5Digitale Bäume

14.5.1Tries

14.5.2Patricia-Bäume

14.6Praktische Nutzung von Bäumen

14.6.1Sortieren mit Bäumen: HeapSort

14.6.2Sets mit binären Suchbäumen

15Hashverfahren

15.1Grundprinzip des Hashens

15.2Grundlagen und Verfahren

15.2.1Hashfunktionen

15.2.2Behandlung von Kollisionen

15.2.3Aufwand beim Hashen

15.2.4Hashen in Java

15.2.5Cuckoo-Hashing

15.3Dynamische Hashverfahren

15.3.1Grundideen für dynamische Hashverfahren

15.3.2Erweiterbares Hashen

15.3.3Umsetzung des erweiterbaren Hashens

16Graphen

16.1Arten von Graphen

16.1.1Ungerichtete Graphen

16.1.2Gerichtete Graphen

16.1.3Gewichtete Graphen

16.1.4Weitere Eigenschaften von Graphen

16.2Realisierung von Graphen

16.2.1Knoten- und Kantenlisten

16.2.2Adjazenzmatrix

16.2.3Graphen als dynamische Datenstrukturen

16.2.4Transformationen zwischen Darstellungen

16.2.5Vergleich der Komplexität

16.2.6Eine Java-Klasse für Graphen

16.3Ausgewählte Graphenalgorithmen

16.3.1Breitendurchlauf

16.3.2Tiefendurchlauf

16.3.3Zyklenfreiheit und topologisches Sortieren

16.4Algorithmen auf gewichteten Graphen

16.4.1Kürzeste Wege

16.4.2Dijkstras Algorithmus

16.4.3A*-Algorithmus

16.4.4Kürzeste Wege mit negativen Kantengewichten

16.4.5Maximaler Durchfluss

16.4.6Der Ford-Fulkerson-Algorithmus

16.5Zentralitätsanalyse in Graphen

16.6Weitere Fragestellungen für Graphen

17Algorithmen auf Texten

17.1Probleme der Worterkennung

17.2Knuth-Morris-Pratt

17.3Boyer-Moore

17.4Pattern Matching

17.4.1Reguläre Ausdrücke

17.4.2Endliche Automaten

17.4.3Java-Klassen für reguläre Ausdrücke

17.5Ähnlichkeit von Zeichenketten

17.5.1Levenshtein-Distanz

17.5.2n-Gramme

17.5.3Anwendungen der Ähnlichkeitsvergleiche

18Literaturhinweise zum Teil III

IVAnhang

AQuelltext der Klasse IOUtils

Abbildungsverzeichnis

Tabellenverzeichnis

Algorithmenverzeichnis

Beispielverzeichnis

Programmverzeichnis

Literaturverzeichnis

Index

Teil I

Grundlegende Konzepte

1Vorbemerkungen und Überblick

Im beginnenden neuen Jahrtausend ist es eigentlich nicht mehr notwendig, Begriffe wie Computer, Programm oder Software einzuführen. Wir werden in diesem Kapitel trotzdem einige Vorbemerkungen machen, um den Kontext dieses Buches und der behandelten Begriffe zu verdeutlichen.

1.1Informatik, Algorithmen und Datenstrukturen

Informatik

Informatik ist ein Kunstwort aus den 60er Jahren, das die Assoziationen Informatik gleich Information oder Technik oder Informatik gleich Information und Mathematik erwecken sollte. Bei der Begriffsbildung sollte durchaus bewusst ein Gegensatz zum amerikanischen Begriff Computer Science aufgebaut werden, um zu verdeutlichen, dass die Wissenschaft Informatik nicht nur auf Computer beschränkt ist. Informatik als Begriff ist insbesondere im nicht englischsprachigen europäischen Raum gebräuchlich. Die Informatik hat zentral zu tun mit

systematischer Verarbeitung von Informationen und

Maschinen, die diese Verarbeitung automatisch leisten.

Wichtige Grundkonzepte der Informatik können in einer maschinenunabhängigen Darstellung vermittelt werden. Der Bezug zu den Themen diese Buches kann durch die folgende Aussage hergestellt werden:

Algorithmen und Daten

Die »systematische Verarbeitung« wird durch den Begriff Algorithmus präzisiert, Information durch den Begriff Daten.

In einer ersten Näherung kann man das Konzept des Algorithmus wie folgt charakterisieren:

Ein Algorithmus ist eine eindeutige Beschreibung eines in mehreren Schritten durchgeführten (Bearbeitungs-)Vorganges.

In der Informatik werden nun speziell Berechnungsvorgänge statt allgemeiner Bearbeitungsvorgänge betrachtet, wobei der Schwerpunkt auf der Ausführbarkeit durch (abstrakte) Maschinen liegt, die auch als Prozessoren bezeichnet werden:

Prozessor

Ein Prozessor führt einen Prozess (Arbeitsvorgang) auf Basis einer eindeutig interpretierbaren Beschreibung (dem Algorithmus) aus.

In diesem Buch werden eine Reihe von Fragestellungen behandelt, die Aspekte des Umgangs mit Algorithmen betreffen. Die verschiedenen Notationen für die Beschreibung von Algorithmen führen direkt zu Sprachkonzepten moderner Programmiersprachen.

Ausdrucksfähigkeit verschiedener Notationen

Wenn verschiedene Notationen verwendet werden können, stellt sich die Frage der Ausdrucksfähigkeit dieser Algorithmensprachen. Man kann sich diese Fragestellungen daran verdeutlichen, dass man sich überlegt, wie ausdrucksfähig die Bienensprache, die ja konkrete Wegbeschreibungen ermöglicht, im Vergleich zu einer Programmiersprache zur Wegfindungsprogrammierung von Robotern ist, oder ob dressierte Hunde tatsächlich dieselbe Sprache verstehen wie Menschen.

Korrektheit und Zeitbedarf

Spätestens beim Übergang zu konkreten Programmen in einer Programmiersprache müssen natürlich die Fragestellungen der Korrektheit und des Zeitbedarfs bzw. der Geschwindigkeit von Programmen betrachtet werden.

In diesem Buch geht es primär um Algorithmen für Rechner, also schnelle (aber dumme) Prozessoren (ein Rechner ist im Vergleich zu einem Menschen ein »Hochgeschwindigkeitstrottel«, der falsche Anweisungen prinzipiell nicht erkennen kann, aber sehr schnell als Programm vorgegebene Anweisungen ausführen kann). Hierzu werden mathematisch formale Grundlagen von Algorithmen eingeführt – ein Rechner »versteht« nur Bits, so dass jede Anweisungssprache auf diese einfache Ebene heruntergebrochen werden muss. Die Umsetzung von menschenverständlichen Algorithmen in eine maschinennahe Darstellung geht natürlich nur, wenn die Bedeutung beider Darstellungen exakt formal festgelegt ist.

Datenstrukturen

Auch wenn sich beim Programmieren scheinbar alles um die Algorithmen dreht, ist das Gegenstück, die Datenstrukturen, ebenfalls ein zentraler Aspekt der Grundlagen der Informatik. Erst rechnerverarbeitbare Darstellungen von Informationen erlauben das Programmieren realistischer Probleme auf einer angemessenen Abstraktionsebene – die Zeit, in der ein Programmierer sich an den Rechner anpassen und direkt in Bits und Bytes denken musste, ist zumindest in der nicht stark hardwarenahen Programmierung vorbei.

1.2Historischer Überblick: Algorithmen

Die in diesem Buch behandelten Konzepte der Informatik sind älter als die Geschichte der Computer, die Programme ausführen können. Die Informatik behandelt Konzepte, die auch ohne existierende Computer gültig sind – aber zugegebenermaßen erst durch den Siegeszug der Computer die heutige praktische Relevanz erlangten.

In diesem Abschnitt wollen wir kurz einige Ergebnisse aus der Zeit vor dem Bau des ersten Computers nennen, um dies zu verdeutlichen:

300 v. Chr.:Euklids Algorithmus zur Bestimmung des ggT (beschrieben im 7. Buch der Elemente), also des größten gemeinsamen Teilers, mit dem etwa

sehr effizient berechnet werden kann, ist die erste Beschreibung eines Verfahrens, das modernen Kriterien für Algorithmen gerecht wird.

800 n. Chr.: Der persisch-arabische Mathematiker Muhammed ibn Musa abu Djafar alChoresmi (oft auch als »al Chworesmi« oder »al Charismi« geschrieben) veröffentlicht eine Aufgabensammlung für Kaufleute und Testamentsvollstrecker, die später ins Lateinische als Liber Algorithmi übersetzt wird.

Das Wort Algorithmus ist ein Kunstwort aus dem Namen dieses Mathematikers und dem griechischen »arithmos« für Zahl.

1574:Adam Rieses Rechenbuch verbreitet mathematische Algorithmen in Deutschland.

1614:Die ersten Logarithmentafeln werden algorithmisch berechnet – ohne Computer dauerte dies 30 Jahre!

1703:Binäre Zahlensysteme werden von Leibnitz eingeführt. Diese Zahlensysteme bilden die Grundlage der internen Verarbeitung in modernen Computern.

1815:Augusta Ada Lovelace, die erste »Computer-Pionierin«, wird geboren. Sie entwickelt schon früh Konstruktionspläne für verschiedenartige Maschinen, wird Assistentin von Babbage und entwirft Programme für dessen erste Rechenmaschinen.

1822:Charles Babbage entwickelt die sogenannte Difference Engine, die in einer verbesserten Version 1833 fertiggestellt wird. Später entwickelt er auch die Analytical Engine, die bereits die wichtigsten Komponenten eines Computers umfasst, aber niemals vollendet wird.

1931:Gödels Unvollständigkeitssatz beendet den Traum vieler damaliger Mathematiker, die gesamte Beweisführung aller Sätze in der Mathematik mit algorithmisch konstruierten Beweisen durchzuführen.

1936:Die Church’sche These vereinheitlicht die Welt der Sprachen zur Notation von Algorithmen, indem für viele der damaligen Notationen die gleiche Ausdrucksfähigkeit postuliert wird.

danach:Mit der Realisierung der ersten Computer erfolgte natürlich der Ausbau der Algorithmentheorie zu einem eigenen Wissenschaftsgebiet.

Auch für den Bereich der Datenstrukturen können lang zurückreichende Wurzeln gefunden werden, etwa das Indexierungssystem historischer Bibliotheken.

Ein historischer Überblick, der auch die technische Informatik, die Programmierung und Aspekte des Software Engineering behandelt, würde den Rahmen des vorliegenden Buches sprengen. So werden wir nur noch im folgenden Abschnitt, der die Wahl der Sprache Java als Ausbildungssprache motivieren soll, die Historie der Programmiersprachen kurz anreißen.

1.3Historie von Programmiersprachen und Java

AutocodeFortranAlgolLispCOBOL

Bevor wir näher auf die in diesem Buch verwendete Programmiersprache Java eingehen, lohnt es sich, einen Blick in die Geschichte zu werfen. Die Ursprünge höherer Programmiersprachen reichen zurück an den Anfang der fünfziger Jahre, als erste Sprachen wie Autocode vorgeschlagen wurden, die bereits arithmetische Ausdrücke, Schleifen, bedingte Sprünge und Prozeduren umfassten. Daraus wurde dann Fortran (FORmula TRANslator) entwickelt, deren erste Fassung 1954 vorgestellt wurde und die auch heute noch speziell im wissenschaftlich-technischen Bereich zum Einsatz kommt. Anfang der sechziger Jahre wurden dann Algol (ALGOrithmic Language), eine Sprache, die u.a. Pascal nachhaltig beeinflusst hat, Lisp, als die Grundlage aller funktionalen Programmiersprachen und im Bereich der künstlichen Intelligenz immer noch häufig eingesetzt, und die vielleicht noch am weitesten verbreitete Programmiersprache COBOL (COmmon Business Oriented Language) entwickelt. Auch die Entwicklung von BASIC geht auf die Mitte der sechziger Jahre zurück.

Pascal

Die Methode der strukturierten Programmierung wurde wesentlich durch Pascal begründet, eine Entwicklung von Niklaus Wirth zu Beginn der siebziger Jahre. Mit Pascal wurden nicht nur Sprachmittel eingeführt, die heute in allen modernen Programmiersprachen zu finden sind, sondern es wurde auch erstmals die Programmausführung durch die Interpretation von Zwischencode (sogenannten P-Code) verwirklicht. Dieses Verfahren wurde dann beispielsweise für Java »wiederentdeckt« und hat wesentlich zur Verbreitung der Sprache beigetragen.

C

Ebenfalls Anfang der siebziger Jahre wurde ausgehend von Sprachen wie CPL und BCPL die Programmiersprache C entwickelt und zur Implementierung des Betriebssystems UNIX eingesetzt. Damit wurde erstmals eine höhere Programmiersprache für die Betriebssystementwicklung verwendet. Der sich daraus ergebenden weitgehenden Maschinenunabhängigkeit ist es letztendlich zu verdanken, dass UNIX und die Vielzahl der Derivate (wie u.a. Linux) heute auf nahezu allen Hardwareplattformen zu finden sind.

Modula

Die Idee modularer Programmiersprachen wurde ab Mitte der siebziger Jahre wiederum von Wirth mit Modula entwickelt und speziell auch in Ada umgesetzt.

Simula-67SmalltalkC++

Objektorientierte Programmiersprachen wie Smalltalk, C++ oder Java haben ihren Ursprung in Simula-67, die um 1967 in Norwegen als eine Sprache für die ereignisorientierte Simulation entstanden ist. Das Potenzial objektorientierter Programmierung wurde zu dieser Zeit jedoch noch nicht wirklich erkannt. Erst mit der Entwicklung von Smalltalk durch Xerox PARC Ende der siebziger Jahre fanden Konzepte wie »Klasse« oder «Vererbung« Einzug in die Programmierung. Ausgehend vom objektorientierten Paradigma einerseits und der Systemprogrammiersprache C andererseits wurde 1983 bei AT&T die Programmiersprache C++ entworfen, die nicht zuletzt wegen der »Abwärtskompatibilität« zu C schnell eine weite Verbreitung fand.

Eiffel

Als Entwicklungen der letzten Jahre vor Java sind insbesondere Eiffel von Bertrand Meyer mit dem neuen Konzept der Zusicherungen bzw. des vertraglichen Entwurfs (design by contract), Oberon von Wirth mit dem Ziel einer Rückbesinnung auf einen einfachen, kompakten und klaren Sprachentwurf sowie die Vielzahl von Skriptsprachen wie Perl, Tcl oder Python zu nennen.

Java

Die Arbeiten zu Java lassen sich bis in das Jahr 1990 zurückverfolgen, als bei Sun Microsystems eine Sprache für den Consumer-Electronics-Bereich unter dem Namen Oak entwickelt werden sollte. Entwurfsziele dieser Sprache waren bereits Plattformunabhängigkeit durch Verwendung von Zwischencode und dessen interpretative Ausführung, Objektorientierung und die Anlehnung an C/C++, um so den Lernaufwand für Kenner dieser Sprachen gering zu halten. Mit der Entwicklung des World Wide Web um 1993 fand im Entwicklerteam eine Umorientierung auf Webanwendungen und damit eine Umbenennung in Java – die bevorzugte Kaffeesorte der Entwickler – statt.

HotJavaNetscapeJava Development KitJ2SE 5.0Java SE 6.0Java SE 7.0Java SE 8

1995 wurde die Sprache dann zusammen mit einer Referenzimplementierung und dem HotJava-Browser der Öffentlichkeit vorgestellt. Dieser Browser ermöglichte erstmals aktive Webinhalte – durch sogenannte Applets. Hinter diesem Begriff verbergen sich kleine Java-Programme, die als Teil eines Webdokumentes von einem Server geladen und in einem geschützten Bereich des Browsers ausgeführt werden können. Da der HotJava-Browser selbst in Java geschrieben wurde, war dies gleichzeitig die Demonstration der Eignung von Java für größere Projekte. Als Netscape – damals unbestrittener Marktführer bei Webbrowsern – kurz darauf die Unterstützung von Java-Applets in der nächsten Version des Navigators bekannt gab, fand Java in kürzester Zeit eine enorme Verbreitung. Dies wurde auch noch dadurch verstärkt, dass die Entwicklungsumgebung für Java von Sun kostenlos über das Web zur Verfügung gestellt wurde. Im Jahre 1997 wurde dann die Version 1.1 des Java Development Kit (JDK) freigegeben und alle großen Softwarefirmen wie IBM, Oracle oder Microsoft erklärten ihre Unterstützung der Java-Plattform. Mit der Veröffentlichung von Java 2 im Jahr 1998 und der Folgeversionen des JDK hat sich dann nicht nur die Anzahl der Systemplattformen, auf denen Java-Programme lauffähig sind, vergrößert, sondern insbesondere auch die Zahl der Klassenbibliotheken, die für Java verfügbar sind. In der im Sommer 2005 freigegebenen Version J2SE 5.0 (Java 2 Platform Standard Edition) wurden schließlich auch einige neue Sprachkonzepte wie Generics und variable Parameterlisten eingeführt, auf die wir an geeigneter Stelle eingehen werden. Die Nachfolgeversion Java SE 6.0 erschien im Dezember 2006 und hat seitdem einige Updates erfahren. Wesentliche Änderungen an der Sprache selbst bietet diese Version jedoch nicht. Seit 2006 ist Java auch als Open-Source-Software – das OpenJDK – verfügbar. 2009/2010 wurde die Firma Sun Microsystems, und damit auch die Java-Technologien, vom Datenbankhersteller Oracle gekauft. Die Weiterentwicklung von Java, die im sogenannten Java Community Process (JCP) stattfindet, wird nun also von Oracle geleitet. Die nächste Version Java SE 7.0 wurde im Juli 2011 veröffentlicht und enthält neben API-Erweiterungen nur einige kleinere Spracherweiterungen. 2014 wurde Java SE 8 veröffentlicht. In dieser Version wurde mit den Lambda-Ausdrücken ein sehr interessantes Konzept aus dem Bereich funktionaler Programmiersprachen in die Sprache aufgenommen, das wir ebenfalls kurz vorstellen werden.

Java SE 9Java SE 14

Nach einer dreijährigen Pause wurde 2017 die Version Java SE 9 freigegeben, mit der u.a. die Java-Shell eingeführt wurde. Die aktuelle Version ist die im März 2020 veröffentlichte Version Java SE 14.

Geblieben sind die ursprünglichen Ansprüche: eine leicht erlernbare, klare und kompakte Sprache, die die Komplexität beispielsweise von C++ vermeidet, aber dennoch das objektorientierte Paradigma umsetzt. Gleichzeitig ist Java architekturneutral, d.h., durch Verwendung eines plattformunabhängigen Zwischencodes sind Programme auch in kompilierter Form portabel – eine Eigenschaft, die für eine moderne Internet-Programmiersprache fundamental ist. Über die Sprache selbst hinaus spielt die Java Virtual Machine (JVM) eine wichtige Rolle als Plattform für andere Sprachen. Neben Umsetzungen anderer Sprachen auf die JVM wie JRuby oder JPython zählen hierzu insbesondere neue Sprachen wie Scala, Groovy, Clojure oder Kotlin.

1.4Grundkonzepte der Programmierung in Java

Programm

Ein fundamentaler Begriff beim Programmieren – eigentlich beim Umgang mit Computern allgemein – ist das Programm. Egal ob man ein Textverarbeitungssystem oder ein kleines, selbst geschriebenes Java-Programm zur Berechnung der Fakultät einer Zahl betrachtet – in beiden Fällen handelt es sich um ein Programm (oder eine Sammlung davon).

Definition 1.1 Programm

Ein Programm ist die Formulierung eines Algorithmus und der zugehörigen Datenstrukturen in einer Programmiersprache.

Die Grundbausteine von Programmen in höheren Programmiersprachen werden wir erst in den nächsten Kapiteln kennen lernen. Intuitiv wissen wir aber, dass zumindest Anweisungen wie elementare Operationen, bedingte Anweisungen und Schleifen, Datentypen zur Festlegung der Struktur der Daten und darauf definierte Operationen sowie die Möglichkeit der Formulierung von Ausdrücken benötigt werden.

Compiler

Die syntaktisch korrekte Kombination dieser Bausteine allein führt jedoch noch nicht zu einem ausführbaren Programm. Da Programme meist in einer für Menschen schreib- und lesbaren Form erstellt werden, sind sie für Computer, die nur einen von der jeweiligen Prozessorarchitektur (etwa Intels x86-Familie, die SPARC-Prozessoren von Sun oder die PowerPC-Prozessorfamilie der Macs bzw. IBM-Rechner) abhängigen Maschinencode »verstehen«, nicht direkt ausführbar. Es ist daher eine Übersetzung oder auch Kompilierung (engl. compile) des Programms aus der Programmiersprache in den Maschinencode notwendig. Die Übersetzung erfolgt durch ein spezielles Programm, das als Compiler bezeichnet wird. Neben der Übersetzung in Maschinencode führt ein solcher Compiler auch noch verschiedene Überprüfungen des Programms durch, z.B. ob das Programm hinsichtlich der Syntax korrekt ist, ob benutzte Variablen und Prozeduren deklariert sind u.Ä. Programmiersprachen wie C, C++ oder (Turbo-)Pascal basieren auf diesem Prinzip.

InterpreterSkriptsprachen

Da jede Änderung am Programmtext eine Neukompilierung erfordert, verzichtet man bei einigen Sprachen auf die Übersetzung, indem die Programme interpretiert werden. Das bedeutet, dass ein spezielles Programm – der sogenannte Interpreter – den Programmtext schrittweise analysiert und ausführt. Der Interpreter muss also Syntax und Semantik der Sprache kennen! Der Vorteil dieses Ansatzes ist, dass die Kompilierung entfällt und dadurch Änderungen vereinfacht werden. Auch ist das Programm (man spricht häufig auch von Skripten) unabhängig von einer konkreten Prozessorarchitektur. Diese Vorteile werden durch die Notwendigkeit eines Interpreters und eine durch die interpretierte Ausführung verschlechterte Performance erkauft. Beispiele für Sprachen, die mit diesem Prinzip realisiert werden, sind insbesondere die im Webumfeld beliebten Skriptsprachen wie JavaScript.

Bytecode

Java basiert auf einem kombinierten Ansatz (Abbildung 1–1). Programme werden zwar kompiliert, jedoch nicht in einen prozessorspezifischen Maschinencode, sondern in einen sogenannten Bytecode. Hierbei handelt sich um Code für eine abstrakte Stack-Maschine. Dieser Bytecode wird schließlich von einem Java-Interpreter, der virtuellen Java-Maschine (Java VM – engl. Virtual Machine), ausgeführt. Da der Bytecode relativ maschinennah ist, bleibt die Interpretation und Ausführung einfach, wodurch der Performance-Verlust gering gehalten werden kann. Andererseits lassen sich auf diese Weise auch übersetzte Java-Programme auf unterschiedlichen Prozessorarchitekturen ausführen, sofern dort eine Java-VM verfügbar ist.

Aufbau von Java-ProgrammenKlasseMethoden

Wie ist nun ein Java-Programm aufgebaut? Ein solches Programm besteht aus einer oder mehreren Klassen, die damit das Hauptstrukturierungsmittel in Java darstellen. Wir werden auf den Begriff der Klasse später im Zusammenhang mit Datenstrukturen noch genauer eingehen. Zunächst wollen wir darunter nur ein Modul verstehen, das eine Menge von Variablen und Prozeduren bzw. Funktionen kapselt. Im Sprachgebrauch von Java werden Prozeduren und Funktionen, d.h. die Zusammenfassung von Anweisungen zu einer logischen Einheit, auch als Methoden bezeichnet.

Abb. 1–1 Compiler und Interpreter bei Java

Abb. 1–2 Struktur eines Java-Programms

main-Methode

Abbildung 1–2 verdeutlicht den Aufbau eines Java-Programms aus mehreren Klassen. Jede Klasse ist durch einen Namen gekennzeichnet und kann Attribute und Methoden definieren. Mindestens eine Klasse muss eine spezielle Methode main besitzen, die den Einstiegspunkt für die Ausführung bildet. Wenn das Programm später ausgeführt werden soll, ist der Name der Klasse mit der main-Methode (engl. für »Haupt«-Methode) anzugeben. Beim Start wird dann zuerst diese Methode aufgerufen, die damit das »Hauptprogramm« bildet.

Kompilierung

Dateien mit Klassendefinitionen werden in Java mit der Endung .java gespeichert, wobei für jede öffentliche, d.h. von »außen« nutzbare Klasse eine eigene Datei verwendet wird, die den Namen der Klasse trägt. Die Klassen müssen zur Erstellung eines ausführbaren Programms zunächst mit dem Java-Compiler in Bytecode übersetzt (kompiliert) werden. Der Java-Compiler ist entweder in eine Entwicklungsumgebung wie Eclipse oder NetBeans integriert oder als ein Programm mit dem Namen javac verfügbar. Im ersten Fall erfolgt die Kompilierung einfach über die grafische Benutzerschnittstelle der Entwicklungsumgebung – meist sogar im Hintergrund, ohne dass explizit die Kompilierung angestoßen werden muss. Im zweiten Fall wird dies durch ein Kommando der folgenden Form vorgenommen:

> javac Klasse.java

AusführungCLASSPATH

Als Ergebnis der Übersetzung entsteht für jede Klasse eine Datei mit der Endung .class, die den Bytecode enthält und durch die Java-Maschine ausgeführt werden kann. Diese Java-Maschine kann ein Interpreter für den Bytecode sein oder auch den Bytecode intern in direkt ausführbaren Maschinencode übersetzen. Letzteres wird als Just-in-Time-Kompilierung (JIT-Kompilierung) bezeichnet. Ein explizites Binden der übersetzten Klassen, wie es etwa bei C-Programmen durchgeführt werden muss, ist dagegen nicht notwendig. Zur Ausführung muss die Java-Maschine – ein Programm mit dem Namen java – gestartet werden, wobei der Name der Klasse als Parameter übergeben wird. Sind in der auszuführenden Klasse weitere Klassen referenziert, so wird der benötigte Bytecode vom Interpreter bei Bedarf nachgeladen. Dazu muss bekannt sein, wo dieser Code zu finden ist. Sowohl Compiler als auch Interpreter werten daher eine Umgebungsvariable CLASSPATH aus, die eine Liste von Verzeichnissen bzw. von Archiven mit .class-Dateien beinhaltet. Im einfachsten Fall ist dies das aktuelle Verzeichnis, das durch ».« bezeichnet wird. Sollen mehrere Verzeichnisse angegeben werden, so werden diese unter UNIX durch »:« bzw. unter Windows durch »;« getrennt.

Package

Ein weiteres wichtiges Strukturierungsmittel in Java sind Packages oder Pakete. Hierbei handelt es sich um einen Mechanismus zur Organisation von Java-Klassen. Durch Pakete werden Namensräume gebildet, die Konflikte durch gleiche Bezeichnungen verhindern. So kann eine Klasse Object definiert werden, ohne dass es dadurch zu Konflikten mit der Standardklasse java.lang.Object kommt. Ein Paket demo wird beispielsweise durch die Anweisung

package demo;

Importieren

vereinbart, wobei dies am Anfang der Quelldatei anzugeben ist. Jede Klasse, in deren Quelldatei diese Anweisung steht, wird dem Paket demo zugeordnet. Über die Notation demo.MeineKlasse kann danach eindeutig die im Paket demo definierte Klasse MeineKlasse identifiziert werden. Diese Schreibweise lässt sich jedoch abkürzen, indem zu Beginn der Quelldatei eine import-Anweisung eingefügt wird:

import demo.MeineKlasse;

Danach kann die Klasse MeineKlasse ohne vorangestellten Paketnamen verwendet werden. Alle Klassen eines Paketes lassen sich durch Angabe eines * importieren:

import demo.*;

PaketnamenStandard-API

Paketnamen können hierarchisch aufgebaut werden, wobei die einzelnen Namensbestandteile durch ».« getrennt werden. Allerdings wird durch Angabe des »*« beim Import kein rekursives Importieren durchgeführt, sondern es sind nur die Klassen des bezeichneten Paketes betroffen. Zu beachten ist weiterhin, dass die Pakete, die mit java. beginnen, zum Standard-API gehören und nicht verändert werden dürfen, d.h., eigene Paketnamen dürfen nicht mit java. beginnen.

Pakete liefern dem Java-Compiler auch Hinweise, wo die kompilierten Klassendateien (Dateien mit der Endung .class) abgelegt werden sollen. Danach werden Punkte im Paketnamen durch den Separator für Verzeichnisnamen ersetzt. Eine Klassendatei der Klasse algoj.sort.QuickSort wird demzufolge im Verzeichnis algoj/sort unter dem Namen QuickSort.class abgelegt.

Betrachten wir nun am Beispiel einer einfachen Klasse die Schritte der Erstellung eines Java-Programms. Die Klasse Hello aus Programm 1.1 soll die typische Aufgabe eines jeden ersten Programms aus Einführungsbüchern zu Programmiersprachen erfüllen: die Ausgabe der Meldung »Hello World!«.

Programm 1.1 »Hello World!« in Java

// Hello World! in Java

public class Hello {

public static void main(String[ ] args) {

System.out.println("Hello World!");

}

}

Klassenbezeichner

Für das Programm muss zunächst eine Klasse definiert werden, die als »Kapsel« dient: Attribute und Methoden können nur im Rahmen von Klassen definiert werden. Eine Klassendefinition wird durch das Schlüsselwort class, gefolgt vom Bezeichner der Klasse, eingeleitet. Das im obigen Programm vorangestellte Schlüsselwort public definiert zusätzlich noch die Sichtbarkeit der Klasse und gibt an, dass diese Klasse öffentlich ist, d.h. auch von anderen Modulen aus zugreifbar ist. Es sei an dieser Stelle noch betont, dass bei Java zwischen Groß- und Kleinschreibung unterschieden wird: Die Schlüsselwörter der Sprache (z.B. class) werden grundsätzlich kleingeschrieben, bei Bezeichnern (wie etwa der Name einer Klasse) bleibt dies dem Entwickler überlassen, muss aber konsistent erfolgen. So bezeichnen eineKlasse, EineKlasse und EINEKLASSE verschiedene Klassen!

Definition der Attribute und MethodenKlassenmethode

Im Anschluss an den Klassenbezeichner folgt in geschweiften Klammern die Definition der Attribute und Methoden. In unserem Beispiel umfasst die Klasse nur eine Methode main. Diese Methode ist öffentlich (public), liefert kein Ergebnis zurück (Typ void) und erwartet als Parameter ein Feld von Zeichenketten (String[] args). Obwohl die Parameter in unserem Beispiel nicht benötigt werden, müssen sie dennoch hier angegeben werden, da der Java-Interpreter eine Methode mit exakt der Signatur static void main (String[]) sucht und aufruft. Das Schlüsselwort static kennzeichnet die Methode als, d.h., sie kann ohne Objekt aufgerufen werden. Da wir die Konzepte der Objektorientierung erst in Kapitel 11 behandeln, werden wir zunächst alle Methoden als Klassenmethoden realisieren.

Ausgabe

Die main-Methode besteht nur aus einer Anweisung zur Ausgabe der Zeichenkette »Hello World!« auf den Bildschirm. Diese Anweisung ist der Aufruf der Methode println. Das vorangestellte System.out bezeichnet das Objekt, für das diese Methode aufgerufen wird – es handelt sich hier konkret um ein Objekt, das durch das Attribut out der Klasse System bezeichnet wird und die Ausgabe repräsentiert.

Kommentar

Ein Kommentar im Quelltext wird durch das Voranstellen der Zeichenfolge // gekennzeichnet. In diesem Fall erstreckt sich der Kommentar bis zum Zeilenende. Eine zweite Möglichkeit ist das Einschließen in /* Kommentar */. Hier kann sich der Kommentar auch über mehrere Zeilen erstrecken.

Übersetzung

Der Quelltext der obigen Klasse Hello wird in einer Datei Hello.java gesichert und mithilfe des Compilers übersetzt:

> javac Hello.java

Schließlich wird der erzeugte Bytecode mit dem Interpreter ausgeführt und dabei die Meldung »Hello World!« ausgegeben:

> java Hello

Hello World!

Zu beachten ist, dass nur der Name der auszuführenden Klasse als Parameter angegeben wird und nicht der vollständige Dateiname.

Java-Shell REPL

In der Version 9 wurde mit der JShell ein neues interaktives Werkzeug eingeführt. Hierbei handelt es sich um eine REPL (Read Eval Print Loop), d.h., Java-Deklarationen und -Anweisungen können eingegeben werden und werden sofort ausgeführt. Dies bietet sich gerade für erste Schritte oder einfache Versuche an, da nicht jeweils der Zyklus Editor → Compiler → Interpreter durchlaufen werden muss. Außerdem können auch einzelne Anwendungen direkt ausgeführt werden, ohne dass ein vollständiges Programm zu implementieren ist:

> jshell

| Welcome to JShell – Version 14.0.2

| For an introduction type: /help intro

jshell> System.out.println("Hello Shell!");

Hello Shell!

jshell>

Applet

Eine spezielle Form von Java-Programmen sind die Applets. Das sind kleine Module, die im Rahmen von Webseiten in einem Webbrowser ausgeführt werden. Daraus ergibt sich, dass diese Applets gemeinsam mit dem Dokument vom Webserver geladen werden – das Installieren von Programmen kann damit entfallen. Applets dienen vor allem zur Gestaltung aktiver Elemente in Webseiten. Sie ermöglichen es, Anwendungslogik im Form von Java-Code im Browser auszuführen. So lassen sich beispielsweise Spiele realisieren oder Daten aus anderen Quellen interaktiv präsentieren und manipulieren. Ähnliche Konzepte existieren inzwischen auch für die Ausführung von Java-Programmen auf Mobiltelefonen. Da Applets jedoch aus Sicht der Programmierung keine wesentlichen Unterschiede aufweisen und mit der Version 11 entfernt wurden, werden wir uns im Weiteren auf »normale« Java-Programme beschränken.

2Algorithmische Grundkonzepte

Der Begriff des Algorithmus entstammt ursprünglich den Bemühungen, mathematische Berechnungsvorschriften eindeutig zu beschreiben und zu dokumentieren. In der Informatik geht es speziell darum, »durch Rechner bearbeitbare Aufgaben« zu beschreiben – Algorithmen sind somit ein abstrakteres Konzept für auf konkreten Rechnern ausführbare Programme.

In diesem Abschnitt werden die Grundkonzepte von Algorithmen und derer Beschreibung vorgestellt. Wir beginnen mit einem intuitiven Zugang zu Algorithmen, aus dem wir Anforderungen an einen formal fundierten Ansatz ableiten werden. Die folgenden Abschnitte stellen einige Voraussetzungen für die Formalisierung von Algorithmen zusammen – wie legt man eine Sprache für Algorithmen fest, wie beschreibt man von Algorithmen zu verarbeitende Daten, wie notiert man elementare arithmetische Berechnungsschritte.

Dieses Kapitel präsentiert die Grundkonzepte von Algorithmen bewusst ohne Zugriff auf eine konkrete Programmiersprache, da diese universell gültig sind und nicht an eine konkrete maschinelle Interpretation gebunden sind.

2.1Intuitiver Algorithmusbegriff

Der Begriff des Algorithmus ist zentral für die Informatik. Wir werden uns in diesem Abschnitt diesem Begriff von der intuitiven, d.h. nicht mathematisch formalisierten Sichtweise her nähern, bevor wir den Schritt der Formalisierung in den folgenden Abschnitten vollziehen.

2.1.1Beispiele für Algorithmen

Algorithmen sind als mathematische Berechnungsvorschriften entstanden. Allgemeiner kann man Algorithmen als Vorschriften zur Ausführung einer Tätigkeit charakterisieren, wie die folgenden Beispiele verdeutlichen.

Beispiel 2.1 Intuitiver Algorithmenbegriff

Die folgenden Algorithmen im intuitiven Sinne begegnen uns im täglichen Leben:

Bedienungsanleitungen,

Bauanleitungen,

Kochrezepte.

Diese Ausführungsvorschriften sind für ausführende Menschen gedacht, nicht etwa für Rechner, und sind nicht unbedingt in dem engeren Sinne Algorithmen, wie wir diesen Begriff später benutzen werden.

Aus diesen Beispielen lässt sich nun eine intuitive Begriffsbestimmung ableiten, die als erste Konkretisierung des Algorithmenbegriffs dient:

Intuitive Begriffsbestimmung

Ein Algorithmus ist eine präzise (d.h. in einer festgelegten Sprache abgefasste) endliche Beschreibung eines allgemeinen Verfahrens unter Verwendung ausführbarer elementarer (Verarbeitungs-)Schritte.

Die Bedeutung einiger Teile dieser Festlegung wird in den folgenden Abschnitten noch klarer. So bezieht sich die Endlichkeit auf die Tatsache, dass eine Algorithmenbeschreibung eine feste Länge haben muss und nicht einfach »endlos weitergehen« darf. Mit der festgelegten Sprache schließen wir vorerst nur in beliebiger »Prosa« verfasste Texte aus; stattdessen gehen wir von festen Beschreibungsmustern aus, wie sie auch in den intuitiven Beispielen zum Teil genutzt werden. Später werden wir hier weiter einschränken.

Beispiel 2.2 Bekannte Algorithmen

Eine Reihe von Algorithmen in diesem engeren Sinne sind den meisten aus der elementaren Schulmathematik und dem Organisieren von Unterlagen bekannt:

Terminierung

Bevor wir uns die Beschreibung von Algorithmen genauer anschauen, werden erst einige grundlegende Begriffe eingeführt. Der erste ist der Begriff der Terminierung:

Ein Algorithmus heißt terminierend, wenn er (bei jeder erlaubten Eingabe von Parameterwerten) nach endlich vielen Schritten abbricht.

Unser erster Algorithmus zur Addition zweier Dezimalzahlen bestimmt das Ergebnis auch sehr großer Zahlen in endlich vielen Schritten, da er ja jede Stelle der Zahlen (von hinten nach vorne) nur einmal betrachtet und den Übertrag sozusagen »vor sich her schiebt«.

Determinismus

Ein weiterer, ähnlich klingender, aber völlig anders gearteter Begriff ist der Begriff des Determinismus. Der Determinismus legt im gewissen Sinne die »Wahlfreiheit« bei der Ausführung eines Verfahrens fest. Er begegnet uns dabei in zwei Spielarten:

Ein

deterministischer Ablauf

bedeutet, dass der Algorithmus eine eindeutige Vorgabe der Schrittfolge der auszuführenden Schritte festlegt.

Ein

determiniertes Ergebnis

wird von Algorithmen dann geliefert, wenn bei vorgegebener Eingabe ein eindeutiges Ergebnis geliefert wird – auch bei mehrfacher Durchführung des Algorithmus (natürlich mit denselben Eingabeparametern).

Von Rechnern ausgeführte Programme erfüllen in der Regel beide Eigenschaften – man muss sich sogar Mühe geben, um nichtdeterminierte Effekte zu simulieren, zum Beispiel bei einem Programm, das ein zufälliges Ergebnis etwa beim Würfeln nachbildet. Während nichtdeterminierte Ergebnisse in der Regel unerwünscht sind, sind nichtdeterministische Abläufe gerade beim Entwurf von Algorithmen ein häufig eingesetztes Konzept.

Beispiel 2.3 Nichdeterministischer Ablauf

Ein Beispiel für einen nichtdeterministischen Ablauf bildet die folgende Bearbeitungsvorschrift für das Sortieren eines Stapels von Karteikarten:

Sortieren: Wähle zufällig eine Karte, bilde zwei Stapel (lexikographisch vor der Karte, lexikographisch nach der Karte), sortiere diese (kleineren) Stapel, füge die sortierten Stapel wieder zusammen.

Das Ergebnis ist auf jeden Fall ein korrekt sortierter Stapel, das Verfahren ist somit determiniert.

Das folgende Beispiel zeigt ein nichtdeterminiertes Ergebnis:

Wähle zufällig eine Karte.

Determinierte Algorithmen

Wir bezeichnen nichtdeterministische Algorithmen mit determiniertem Ergebnis als determiniert. Die folgenden Beispiele sollen diese Begriffe noch einmal verdeutlichen:

Beispiel 2.4 Nichtdeterminierter vs. determinierter Algorithmus

Die folgende Berechnungsvorschrift bildet ein Beispiel für einen nichtdeterminierten Algorithmus:

Nehmen Sie eine beliebige Zahl

x

.

Addieren Sie 5 hinzu und multiplizieren Sie mit 3.

Schreiben Sie das Ergebnis auf.

Hingegen ist die folgende Berechnungsvorschrift ein Beispiel für einen determinierten, allerdings nichtdeterministischen Algorithmus:

Nehmen Sie eine Zahl

x

ungleich 0.

Entweder: Addieren Sie das Dreifache von

x

zu

x

und teilen das Ergebnis durch

x

(3x +x)/x

Oder: Subtrahieren Sie 4 von x und subtrahieren das Ergebnis von x

x − (x − 4)

Schreiben Sie das Ergebnis auf.

Nach einigem Nachdenken sieht man, dass dieses Verfahren immer das Ergebnis 4 liefert (im ersten Fall durch Herauskürzen von x), egal welche Variante man in Schritt 2 gewählt hat.

Diese Beispiele zeigen, dass man Nichtdeterminiertheit und Nichtdeterminismus nur durch eine im gewissen Sinne »freie Wahlmöglichkeit« bekommen kann, ein Konzept, das einem »mechanisch« arbeitenden Computer natürlich prinzipiell fremd ist.

Ein-/Ausgabefunktion

Eine wichtige Klasse für unsere späteren Überlegungen sind daher deterministische, terminierende Algorithmen. Diese definieren jeweils eine Ein-/Ausgabefunktion:

f : Eingabewerte → Ausgabewerte

Genau genommen betrachten wir mit dieser Funktionsdefinition determinierte, terminierende Algorithmen. Algorithmen geben eine konstruktiv ausführbare Beschreibung dieser Funktion an.

Bedeutung / Semantik von Algorithmen

Die Ein-/Ausgabefunktion bezeichnen wir als Bedeutung (oder Semantik) des Algorithmus. Es kann mehrere verschiedene Algorithmen mit der gleichen Bedeutung geben.

Beispiel 2.5 Funktionen zu den Beispielalgorithmen

Die folgende Aufzählung zeigt Funktionen zu den Algorithmen aus Beispiel 2.2:

2.1.2Bausteine für Algorithmen

Unserer ersten Begriffsbestimmung für Algorithmen zufolge beschreibt ein Algorithmus ein Verfahren, das einen Bearbeitungsvorgang aus elementaren Schritten zusammensetzt. Bevor wir uns konkreten Sprachen für die Formulierung von Algorithmen zuwenden, listen wir einige gängige Bausteine für derartige Algorithmenbeschreibungen auf, die auch aus Handlungsvorschriften des täglichen Lebens bekannt sein dürften. Wir werden diese Bausteine anhand einfacher Vorschriften aus Kochrezepten verdeutlichen.

Elementare Operationen

Die Basiselemente sind die

elementaren Operationen

, die ausgeführt werden, ohne näher aufgeschlüsselt zu werden:

»Schneide Fleisch in kleine Würfel.«

Sequenzielle Ausführung

Das Hintereinanderausführen von Schritten bezeichnet man als

sequenzielle Ausführung

:

»Bringe das Wasser zum Kochen, dann gib das Paket Nudeln hinein, schneide das Fleisch, dann das Gemüse.«

Parallele Ausführung

Die

parallele Ausführung

hingegen bedeutet das gleichzeitige Ausführen von Schritten:

»Ich schneide das Fleisch, du das Gemüse.«

Im Gegensatz zur sequenziellen Ausführung verbindet man mit der parallelen Ausführung in der Regel mehrere Prozessoren, also ausführende Subjekte bzw. Maschinen.

Bedingte Ausführung

Unter einer

bedingten Ausführung

verstehen wir einen Schritt, der nur ausgeführt wird, wenn eine bestimmte Bedingung erfüllt wird.

»Wenn die Soße zu dünn ist, füge Mehl hinzu.«

Eine bedingte Ausführung erfordert also einen Test einer Bedingung. Eine Variante der bedingten Ausführung erhält man, indem auch für den negativen Ausgang des Tests ein auszuführender Schritt angegeben wird.

Schleife

Unter einer

Schleife

versteht man die Wiederholung einer Tätigkeit, bis eine vorgegebene Endbedingung erfüllt wird:

»Rühre, bis die Soße braun ist.«

Man bewegt sich also »im Kreise«, bis man etwas fertiggestellt hat – man kann sich den Begriff gut mit der Assoziation einer »Warteschleife« eines Flugzeuges merken.

Unterprogramm

Bereits aus dem Sprachgebrauch der Informatik stammt das Konzept des

Unter»programms«

:

»Bereite Soße nach Rezept Seite 42.«

Ein Unterprogramm beschreibt durch einen Namen (oder hier durch eine Seitennummer) eine Bearbeitungsvorschrift, die »aufgerufen« wird, um dann ausgeführt zu werden. Nach Ausführung des Unterprogramms fährt man im eigentlichen Algorithmus an der Stelle fort, an der man zum Unterprogramm gewechselt war.

Rekursion

Eines der Kernkonzepte der Informatik ist die

Rekursion

. Die Rekursion bedeutet die Anwendung desselben Prinzips auf in gewisser Weise »kleinere« oder »einfachere« Teilprobleme, bis diese Teilprobleme so klein sind, dass sie direkt gelöst werden können. Hier gibt es leider offenbar keine direkten Beispiele aus Kochbüchern, so dass wir uns mit dem folgenden eher künstlichen Beispiel behelfen:

»Viertele das Fleischstück in vier gleich große Teile. Falls die Stücke länger als 2 cm sind, verfahre mit den einzelnen Stücken wieder genauso (bis die gewünschte Größe erreicht ist).«

Rekursion wird uns durch das ganze Buch begleiten – sollte das Prinzip bei diesem eher künstlichen Beispiel nicht klar geworden sein, verweisen wir auf die folgenden Abschnitte, in denen Rekursion intensiv behandelt wird.

Ausdrucksfähigkeit von Algorithmensprachen

Bei einer derart langen Auflistung stellt man sich schnell die Frage, ob denn alle diese Konstrukte auch notwendig sind. Diese Frage betrifft das Problem der Ausdrucksfähigkeit von Algorithmensprachen und wird uns noch näher beschäftigen. Hier sei nur bemerkt, dass die Konstrukte

elementare Operationen + Sequenz + Bedingung + Schleifen

ausreichen, um eine genügend ausdrucksstarke Algorithmensprache festzulegen – allerdings genügen hierfür auch andere Kombinationen, wie wir später sehen werden.

2.1.3Pseudocode-Notation für Algorithmen

Die genannten Bausteine sind dafür geeignet, auf der intuitiven Ebene (also nicht auf der Basis mathematischer Strenge) Algorithmen zu formulieren. Ein Aspekt der Formulierung ist die Nutzung einer genormten, festgelegten Ausdrucksweise. Wir werden eine derartige Ausdrucksweise kennen lernen, die die genannten Bausteine benutzt und auf einer leicht verständlichen Ebene bleibt. Da die Formulierung der Algorithmen nahe an den Konstrukten verbreiteter Programmiersprachen ist, in denen Programme »kodiert« werden, bezeichnet man diese intuitiven Algorithmen auch als Pseudocode-Algorithmen.

Pseudocode-Notation für AlgorithmenSchlüsselwort

In der Informatik werden derartige Pseudocode-Algorithmen in der Regel unter der Verwendung spezieller englischer Begriffe formuliert. Diese englischen Begriffe sind der Alltagssprache entnommen und haben eine festgelegte Bedeutung für den Ablauf eines Verfahrens und werden daher als Kontroll- oder Schlüsselwörter bezeichnet. So wird eine bedingte Anweisung mit dem englischen if für »wenn/falls« eingeleitet. Wir beginnen allerdings mit einer semiformalen Notation, die angelehnt an das Lehrbuch von Goldschlager und Lister [GL90] vorerst mit deutschen Kontrollwörtern arbeitet, um den Zugang zu den Konzepten zu erleichtern.

Die Erläuterungen erfolgen wieder anhand eines Beispiels aus dem täglichen Leben, nämlich dem Kaffeekochen. Die Basisoperationen haben in diesem Beispiel die Form einfacher deutscher Befehlssätze, etwa »koche Kaffee!«.

Sequenz

Notation der Sequenz

Die Sequenz, also die zeitliche Abfolge von Schritten, kann man auf verschiedene Arten notieren. Eine Möglichkeit ist es, die Schritte durchzunummerieren, um ihre Reihenfolge vorzugeben:

(1) Koche Wasser

(2) Gib Kaffeepulver in Tasse

(3) Fülle Wasser in Tasse

Verfeinerung

Diese Notation hat den Vorteil, dass sie gleichzeitig eine elegante Form der Verfeinerung von Schritten ermöglicht, indem ein Schritt, zum Beispiel der Schritt (2), durch eine Folge von Einzelschritten, etwa (2.1) bis (2.4), ersetzt wird, die den bisher nur grob beschriebenen Schritt detaillierter, sozusagen »feiner« darstellen. Der Schritt

(2) Gib Kaffeepulver in Tasse

kann zum Beispiel zu folgender Sequenz verfeinert werden:

(2.1) Öffne Kaffeeglas

(2.2) Entnehme Löffel voll Kaffee

(2.3) Kippe Löffel in Tasse

(2.4) Schließe Kaffeeglas

Schrittweise Verfeinerung

Auf dieser Idee der Verfeinerung beruht das Entwurfsprinzip der schrittweisen Verfeinerung, das oft beim Entwurf von Algorithmen eingesetzt wird.

Sequenzoperator

Um das oft umständliche Durchnummerieren zu vermeiden und um den Aspekt der Sequenz zu verdeutlichen, wird in Pseudocode-Algorithmen der explizite Sequenzoperator, ; notiert als ;, eingesetzt. Die Notation mit dem Semikolon wurde auch in viele Programmiersprachen übernommen. Unser Beispiel lautet nun wie folgt:

Koche Wasser;

Gib Kaffeepulver in Tasse;

Fülle Wasser in Tasse

Diese Notation erspart die Durchnummerierung und entfernt auch irrelevante Information aus den Algorithmen – so ist die Tatsache, dass es sich beim Wassereinfüllen um den dritten, und nicht etwa den vierten Schritt handelt, für die Ausführung des Algorithmus nicht relevant.

Bedingte Anweisungen

Bedingte Anweisungen: Auswahl / Selektion

Bedingte Anweisungen wählen aufgrund einer zu testenden Bedingung einen Schritt aus. Sie werden daher auch als Auswahl- oder Selektionsschritte bezeichnet. Wie bereits erwähnt, gibt es zwei Varianten: Entweder wird nur bei positivem Test der Schritt ausgeführt (der Schritt also andernfalls übersprungen) oder es gibt eine weitere Angabe eines Schritts für den negativen Testausgang. Notiert werden diese beiden Varianten als

falls Bedingung

dann Schritt

bzw. als

falls Bedingung

dann Schritt a

sonst Schritt b

Ein Beispiel, diesmal aus einem anderen Alltagsbereich, soll den Einsatz der Auswahl verdeutlichen:

falls Ampel rot oder gelb

dann stoppe

sonst fahre weiter

Der Test liefert einen Wahrheitswert »wahr« oder »falsch«, aufgrund dessen die Ausführung des ersten oder zweiten Schritts entschieden wird.

Schachtelung von Selektionen

Die Schachtelung mehrerer Selektionen ineinander ermöglicht komplexe Auswahlen unter mehreren Schritten, wie das folgende Beispiel zeigt:

falls Ampel ausgefallen

dann fahre vorsichtig weiter

sonst falls Ampel rot oder gelb

dann stoppe

sonst fahre weiter

Das Konstrukt falls … dann … sonst … entspricht in verbreiteten Programmiersprachen den folgenden Konstrukten:

if Bedingung then … else … fi

if Bedingung then … else … endif

if ( Bedingung ) … else …

Das letzte Beispiel gibt die Notation in Java wieder. In Programmiersprachen werden also in der Regel die entsprechenden englischen Wörter verwendet, wobei sich die Sprachen darin unterscheiden, ob sie alle Wörter explizit notieren (in Java wird das then durch eine Klammerung der Bedingung überflüssig) und ob sie ein spezielles Schlüsselwort (etwa endif) zum Abschluss der bedingten Anweisung benutzen. Die erste Variante der Bedingung (Ausführung eines Schrittes nur bei positivem Test) wird jeweils durch Weglassen des else-Teiles realisiert.

Schleifen / Iteration

Schleife

Die Wiederholung eines Schrittes in einer Schleife wird nach dem folgenden Muster notiert:

wiederhole Schritte

bis Abbruchkriterium

Das folgende Beispiel, das bereits nahe an einer von Rechnern interpretierbaren Form ist, zeigt das Prinzip anhand einer Suche nach der nächstgrößeren Primzahl:

/* nächste Primzahl */

wiederhole

Addiere 1;

Teste auf Primzahleigenschaft

bis Zahl Primzahl ist;

gebe Zahl aus

Dieses Beispiel zeigt gleichzeitig die Kombination mehrerer Bausteine mittels Schachtelung, hier eine Sequenz innerhalb einer Schleife. Die inneren Schritte einer Schleife werden als Schleifenrumpf bezeichnet.

Varianten der Iteration

Die bisherige Schleifenvariante hat jeweils den Schleifenrumpf ausgeführt, um danach zu testen, ob sie eine weitere Iteration durchführt oder die Schleife abbricht. Der Schleifenrumpf wird somit mindestens einmal durchlaufen. Eine andere verbreitete Notation führt diesen Test am Beginn jeden Durchlaufs durch:

solange Bedingung

führe aus Schritte

While-Schleife

Nach der englischen Übersetzung des Schlüsselwortes ist diese Variante insbesondere unter dem Namen While-Schleife bekannt. Ein Beispiel für den Einsatz der While-Schleife zeigt folgender Algorithmus:

/* Bestimmung der größten Zahl einer Liste */

Setze erste Zahl als bislang größte Zahl;

solange Liste nicht erschöpft

führe aus

Lies nächste Zahl der Liste;

falls diese Zahl > bislang größte Zahl

dann setze diese Zahl als bislang größte Zahl;

gebe bislang größte Zahl aus

Bei While-Schleifen kann der Fall auftreten, dass der Schleifenrumpf keinmal ausgeführt wird, da die Abbruchbedingung bereits vor dem ersten Durchlauf zutrifft.

Iteration über festen Bereich

Die letzte verbreitete Variante ist die Iteration über einen festen Bereich, zum Beispiel über einen Zahlenbereich. Wir notieren diesen Fall wie folgt:

wiederhole für Bereichsangabe

Schleifenrumpf

For-Schleife

Nach dem englischen Schlüsselwort sind derartige Schleifen als For-Schleifen bekannt. Typische Bereichsangaben wären z.B. »jede Zahl zwischen 1 und 100«, »jedes Wagenrad«, »jeden Hörer der Vorlesung«. Der Bereich, und somit die Zahl der Ausführungen des Schleifenrumpfs, ist – im Gegensatz zu den bisher diskutierten Varianten – bei Beginn der Schleifenausführung festgelegt.

Die vorgestellten Schleifenkonstrukte entsprechen wieder jeweils Programmiersprachenkonstrukten:

wiederhole ... bis repeat ... until ...

do ... while not ...

solange ... führe aus while ... do ...

while (...) ...

wiederhole für for each ... do ...

for ... do ...

for (...) ...

Bei der Umsetzung von wiederhole... bis mit einem do-while-Konstrukt ist jedoch zu beachten, dass dabei die Bedingung negiert wird, da erstere Variante eine Abbruchbedingung erwartet, während bei der letzteren die Schleife so lange ausgeführt wird, wie die Bedingung erfüllt ist.

2.1.4Struktogramme

Struktogramme

Struktogramme – auch als Nassi-Shneidermann-Diagramme bekannt – ermöglichen eine standardisierte grafische Notation für den Aufbau von Algorithmen mittels Sequenz, Bedingung und Schleife (vergleiche z.B. Duden Informatik [Vol03]).

Die Notation für Struktogramme wird in Abbildung 2–1 eingeführt (es gibt weitere Konstrukte für Mehrfachverzweigungen etc., auf die wir hier nicht eingehen werden). Elementare Aktionen entsprechen beschrifteten Rechtecken. Die Konstrukte können beliebig ineinander geschachtelt werden.

Abb. 2–1 Notation für Struktogramme

Abbildung 2–2 zeigt unseren oben eingeführten Ablauf zum Kaffeekochen als Sequenz in einem Struktogramm.

Abb. 2–2 Beispiel eines Struktogramms

Die Schachtelung sowie die Konstrukte für Schleifen und bedingte Anweisung illustriert Abbildung 2–3 mit dem Algorithmus zur Bestimmung der größten Zahl einer Liste, den wir bereits als Pseudocode eingeführt haben.

Abb. 2–3 Schleifen und bedingte Anweisung im Struktogramm

2.1.5Rekursion

Fakultätfunktion