Algorithmen – Eine Einführung
Schwierigkeitsgrad: Schwer
Autoren: Thomas H. Cormen et al.
Erscheinungsdatum: 2. Auflage, März 2007
ISBN: 978-3-486-5262-8
Preis: EUR 69,80
Verlag (inkl. Bestellmöglichkeit): Oldenbourg Wissenschaftsverlag
Englische Originalausgabe: Cormen, Thomas H.: Introduction to Algorithms/Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest; Massachussets Institute of Technology (1990); ISBN 0-262-03141-8 (hardcover), 0-262-53091-0 (Taschenbuch)
1188 Seiten
Rezension von Julian Risch (18 Jahre)
Das Buch ist ein Standardwerk, das man eher zum Nachschlagen, als zum Durchlesen verwenden kann, denn das Durcharbeiten des Buches beansprucht sehr viel Zeit. Für jeden Algorithmus werden Korrektheit und Laufzeit detailliert bewiesen und natürlich der Pseudocode angegeben. Wenn es das Verständnis erleichtert, findet man einfach gehaltene, einfarbige Grafiken. Am Ende jeden Abschnitts findet man Übungsaufgaben, die die Themen weiter vertiefen. Lösungen zu den Aufgaben sucht man im Buch vergeblich, aber zu einigen Aufgaben gibt es Lösungen im Internet.
Im 70-seitigen Anhang findet man die wichtigsten verwendeten mathematischen Grundlagen.
Der Aufbau eines Abschnitts anhand des Standardthemas Quicksort:
Der Abschnitt zu Quicksort hat mir besonders gut gefallen. Bereits auf der ersten Seite werden die Vor- und Nachteile von Quicksort gegenüber anderen Sortieralgorithmen erklärt. Darauf folgen eine umgangssprachliche Beschreibung des Algorithmus und der Pseudocode. Es folgt eine Grafik, die den Zustand der zu sortierenden Zahlenfolge Schritt für Schritt aufzeigt. Dann wird relativ schnell ein intuitives Argument für die mittlere Laufzeit O(n log n) erläutert und zum Abschluss diese Asymptote bewiesen. Die Übungsaufgaben betreffen dann zum Beispiel eine bessere Wahl des Pivot-Elements und die Best-Case-Analyse.
Der Aufbau eines Kapitels anhand des Spezialthemas Fast Fourier Transformation:
Ohne andere Hilfsmittel und einen sehr ausführlichen Schulunterricht hätte ich dieses Abschnitt nicht verstanden. Obwohl die n-ten Einheitswurzeln einer Komplexen Zahl noch verständlich erklärt werden, ist das hohe Niveau verbunden mit den vielen Formeln eher entmutigend.
Was das Buch nicht abdeckt:
Metropolis- und Las-Vegas-Algorithmen werden in diesem Buch nicht behandelt. Auf Genetische Algorithmen wird komplett verzichtet. Sweepline-Algorithmen kommen etwas kurz, sind aber enthalten.
Fazit: Ein klar strukturiertes, sehr ausführliches Nachschlagewerk, das seinen Schwerpunkt auf die mathematische Betrachtung der Algorithmen und Datenstrukturen legt.
Link zum Buch beim Verlag:
http://www.oldenbourg-wissenschaftsverlag.de/olb/de/1.c.1159980.de
Link zum Inhaltsverzeichnis:
http://www.oldenbourg-wissenschaftsverlag.de/fm/694/3-486-58262_i.pdf
Link zur Leseprobe:
http://www.oldenbourg-wissenschaftsverlag.de/fm/694/3-486-58262_p.pdf
Link zu zwei weiteren Rezensionen:
http://matheplanet.com/matheplanet/nuke/html/reviews.php?op=showcontent&id=408
Link zu Lösungen einiger Aufgaben:
http://mitpress.mit.edu/algorithms/