Grundlegende Algorithmen mit Java Doina Logofătu Grundlegende Algorithmen mit Java Lern- und Arbeitsbuch für Informatiker und Mathematiker 2. Aufl age Prof. Dr. Doina Logofătu Frankfurt am Main, Deutschland ISBN 978-3-8348-1972-7 ISBN 978-3-8348-2355-7 (eBook) DOI 10.1007/978-3-8348-2355-7 Die Deutsche Nationalbibliothek verzeichnet diese Publikation in der Deutschen Nationalbibliografi e; detaillierte bibliografi sche Daten sind im Internet über http://dnb.d-nb.de abrufb ar. Springer Vieweg © Springer Fachmedien Wiesbaden 2008, 2014 Das Werk einschließlich aller seiner Teile ist urheberrechtlich geschützt. Jede Verwertung, die nicht aus- drücklich vom Urheberrechtsgesetz zugelassen ist, bedarf der vorherigen Zustimmung des Verlags. Das gilt insbesondere für Vervielfältigungen, Bearbeitungen, Übersetzungen, Mikroverfi lmungen und die Ein- speicherung und Verarbeitung in elektronischen Systemen. Die Wiedergabe von Gebrauchsnamen, Handelsnamen, Warenbezeichnungen usw. in diesem Werk be- rechtigt auch ohne besondere Kennzeichnung nicht zu der Annahme, dass solche Namen im Sinne der Warenzeichen- und Markenschutz-Gesetzgebung als frei zu betrachten wären und daher von jedermann benutzt werden dürft en. Gedruckt auf säurefreiem und chlorfrei gebleichtem Papier Springer Vieweg ist eine Marke von Springer DE. Springer DE ist Teil der Fachverlagsgruppe Springer Science+Business Media. www.springer-vieweg.de Take your life in your own hands and what happens? A terrible thing: no one is to blame. Erica Jong Geleitwort Das vorliegende Buch „Grundlegende Algorithmen mit Java“ vermittelt Grundlagen zu Algorithmen und zur Komplexitätstheorie und illustriert danach allgemeine Lö- sungsprinzipien (z. B. „Teile und Herrsche", „Dynamische Programmierung"). Drei ausgewählte Problemstellungen – „Verschachtelte Schachteln" als einführendes Bei- spiel, das „Data Ordering Problem" als Beispiel für ein NP-vollständiges Problem und Berechnung von Potenzsummen als mathematisch nichttriviales Problem werden aus- führlicher in eigenen Kapiteln behandelt. Jedes Lösungsprinzip wird nach einem theoretischen Vorspann anhand von Proble- men – von trivialen Beispielen bis hin zu umfangreicheren Aufgaben aus Program- mierwettbewerben – erläutert, die anhand von Übungsaufgaben vertieft werden kön- nen. In dem Buch wird ein besonderer Schwerpunkt auf das Prinzip der dynamischen Programmierung gesetzt. Zu allen näher besprochenen Algorithmen gibt es jeweils, nach einigen Kommentaren zur Implementierung, ein komplettes Java-Programm. Das Buch setzt einfache Kennt- nisse in Java voraus, wobei einige Konzepte und Grund legende Klassen am einfüh- renden Beispiel der verschachtelten Schachteln wiederholt werden. Vom über proze- durale Programmierung hinaus gehenden Sprachumfang von Java kommt hauptsäch- lich die Objektorientierung zum Einsatz (insbesondere für abstrakte Datentypen), Ne- benläufigkeit und Netzwerktechniken kommen nicht vor. Dafür finden sich einige Sprachkonstrukte und Klassen, die in Java 5, teils sogar Java 6 eingeführt worden sind, und man lernt manche wenig bekannte Bereiche kennen, z. B. die Buffer-Klassen aus dem Paket java.nio und java.util.Arrays. Fast alle Programme erhalten ihre Einga- ben aus einer Datei (oder von der Tastatur) und schreiben die Ergebnisse in eine ande- re Datei; im Kapitel "Rekursion" kommen daneben auch graphische Ausgaben frakta- ler Strukturen vor. Neben vielen Abbildungen lockern auch einige kleine Bilder, jeweils passend zum Thema, den Text auf. Am Ende des Buches finden sich ein Literaturverzeichnis und ein Stichwortverzeichnis. Dr. Eric Müller Vorwort Viele Problemstellungen dieses Buches habe ich bereits in meinen Buch Algorithmen und Problemlösungen mit C++ behandelt. Die Theorie und die Problembeschreibungen sind größtenteils die gleichen, geändert haben sich natürlich die Programme und die Abschnitte, die sich auf die Programmiersprache beziehen. Neu in diesem Buch ist das erste Kapitel über Algorithmen und die Komplexitätstheorie und das vierte Kapi- tel Data Ordering Problem, in dem ein NP-vollständiges Problem analysiert und mit verschiedenen Ansätzen gelöst wird. Hinzugekommen sind auch neue Probleme wie z. B. die Huffmann-Codierung im Greedy-Kapitel, Sudoku im Backtracking-Kapitel und LCS (longest common substring) im Kapitel über die Dynamische Programmierung. Ich habe die Problemstellungen und Erklärungen aus dem C++-Buch überarbeitet und mir außerdem ein paar zusätzliche Übungen ausgedacht. Ich möchte auch hier durch unterhaltsame Aufgaben Ihre Begeisterung und Ihre Neugier für die Informatik we- cken und Ihnen die Fähigkeit vermitteln, für neue Probleme eigene Lösungen zu fin- den. Grundlegende Algorithmen mit Java beinhaltet in den neun Kapiteln 60 Probleme bzw. Aufgaben, die vollständig analysiert und in Java gelöst werden, knapp 240 Übungs- aufgaben und gut 130 Abbildungen und Bilder. Die nötigen Grundlagen am Anfang jedes Kapitels ermöglichen einen theoretischen Überblick über die Thematik. Zu je- dem Problem wird beschrieben, wie die Eingabe- und Ausgabedateien aufgebaut sind, und ein Beispiel dafür angegeben. Damit können Sie selbstgeschriebene Pro- gramme überprüfen. Dann folgt der Abschnitt Problemanalyse und Entwurf der Lösung, der einen detaillierten algorithmischen/mathematischen Lösungsansatz und ein Java- Programm präsentiert. Die Programme sind kompakt und die Schlüsselwörter in blauer Farbe, um eine gute Lesbarkeit zu gewährleisten. Darum befinden sich auch die Kommentare meistens nicht direkt im Code, sondern daneben in blauen Kästchen. Die Programme sind mit dem JDK 1.6. kompiliert worden, den Oracle® kostenlos zur Verfügung stellt (http://docs.oracle.com/javase/6/docs/). Zu jedem Problem gehö- ren Übungen, die Sie meist auffordern, Programme zu ändern oder neue Programme zu schreiben, damit Sie das gerade Erlernte wiederholen können und Ihre Program- mierfähigkeiten verbessern. Alle Aufgaben bzw. Probleme wenden die am jeweiligen Kapitelanfang vorgestellten mathematischen Konzepte bzw. algorithmischen Verfahren an und vertiefen sie. Die Absicht, die dahinter steht, ist die, dass Sie die Theorie dadurch erlernen, indem Sie sehen und üben, wie sie in der Praxis, also in den Problemen, eingesetzt wird. Viele Probleme sind klassisch, wie z. B. Fibonacci-Zahlen, Koch’sche Schneeflockenkurve, Türme von Hanoi, N-Damen, Haus des Nikolaus, Kartenfärbung, Konvexe Hülle, X Grundlegende Algorithmen mit Java Multiplikation einer Matrizenfolge und Edit-Distanz. Aufgaben aus dem Program- mierwettbewerben Association for Computer Machinery (ACM), International Olympiad in Informatics (IOI) und Central-European Olympiad in Informatics (CEOI) inspirierten mich dazu, zahlreiche Probleme für das Buch zu formulieren. Ab und zu finden Sie, quasi als Belohnung für Ihren Fleiß, zwischen zwei Kapiteln Überraschungsbilder wie: Don Quijotes Windmühlen, Schwäne auf der Isar, Kapelle in Dorohoi, Statue in Bremen, Strandkörbe auf Norderney. Den Online-Service zum Buch finden Sie hier: http://algorithmen-und-problemloesungen.de Ich bitte Sie, mir Ihre Anmerkungen, Lob und Kritik zu senden: [email protected] Dafür bedanke ich mich im Voraus. Viel Vergnügen beim Lesen und spannendes Lernen! Frankfurt am Main, im November 2013 Doina Logof(cid:169)tu www.doina-logofatu.de Danksagung Ganz besonders herzlich bedanke ich mich bei Herrn Dr. Eric Müller, der mir beim Schreiben dieses zweiten Buches wieder treu zur Seite stand. Unermüdlich hat er sehr viele schöne Ideen, wunderbare Vorschläge und Korrekturen und auch ein komplettes Programm für das Problem Orangensport im Backtracking-Kapitel beigesteuert. Dr. Eric Müller gewann zwischen 1986 und 1988 dreimal einen zweiten Preis (Silberme- daille) bei den Internationalen Mathematik-Olympiaden (IMO) und wirkt seit einigen Jahren bei der Vorbereitung der deutschen Teilnehmer auf diesen Schülerwettbewerb mit. Ebenso bedanke ich mich ganz besonders herzlich beim General, der mir meisterhaft bei der Erstellung der Java-Programme geholfen und mir somit viel Zeit erspart hat. Mein besonderer Dank gebührt Herrn Prof. Dr. Rolf Drechsler, dem Leiter der Arbeits- gruppe Rechnerarchitektur der Universität Bremen. Von ihm habe ich gelernt, mich besser in die Position des Lesers zu versetzen und meine Aufgaben "eine nach der an- deren" zu erledigen. Außerdem hat er mir die Vorlagen für die Testmusterkompaktie- rung (Problem 12, Kapitel 7, Backtracking) und das Data Ordering Problem (Kapitel 4) gegeben. Über diese Probleme und andere Themen habe ich mit Görschwin Fey, Daniel Große, Dr. Rüdiger Ebendt, Sebastian Kinder und Junhao Shi interessante Gespräche ge- führt. Dafür danke ich ihnen. Für Informationen zu ACM Problemen danke ich den Herren Prof. Dr. Miquel Revilla Samos (Universität Valladolid, Spanien), Prof. Dr. Cristian Giumale und Prof. Dr. Nicolae (cid:108)(cid:169)pu(cid:242) (beide Universität Bukarest, Rumänien). Für die Erlaubnis, Fotos im Buch verwenden zu dürfen, bedanke ich mich bei den Herren Prof. Dr. Stephen Arthur Cook (erstes Kapitel), Michael W. Davidson (Fotos von Euklid, Euler und Fermat), Robert D. Colburn (Foto von Richard Bellman) und Wolf- gang Weege (das Spiegelfoto im Rekursions-Kapitel). Ich danke Katja Schnelle-Romaus (Karsunke) dafür, dass sie mich vor ein paar Jahren beim Erlernen der deutschen Sprache unterstützt hat. Sie schenkte mir damals ein Buch mit der Geschichte über die Feldmaus Frederik und steigerte dadurch meine Lernmotivation um ein Vielfaches. Ein tiefer Dank gebührt meinen Mathematiklehrern Rodica Ungureanu (Gymnasium "Gr. Ghica") und Victor Barnea (Volksschule 7) in meiner kleinen Heimatstadt Dorohoi XII Grundlegende Algorithmen mit Java im Nordosten Rumäniens. Sie haben es mit ihren anspruchsvollen und interessanten Aufgaben geschafft, mich immer wieder für die Mathematik zu begeistern. Und schließlich danke ich allen, die die Fertigstellung des Buches ermöglicht haben. München, im August 2007 Doina Logof(cid:169)tu