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
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
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
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
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
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:
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 Buches
Einfü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 Konzepte
Objektorientierung
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.
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