The Art of Computer Programming
The Art of Computer Programming ist ein mehrbändiges Werk des amerikanischen Informatik-Professors Donald E. Knuth über grundlegende Algorithmen und Datenstrukturen, zu dessen Realisierung er die berühmten Programme TeX und Metafont entwickelt hat. Ursprünglich hatte der Verleger Knuth (damals noch ein Student im Hauptstudium) damit beauftragt, ein einzelnes Buch über Compiler zu schreiben. Knuth wollte jedoch alles notwendige Wissen zu diesem Thema präsentieren und dies in einer ausgereiften Form.
- I figured, as long as I’m going to do a book on compilers, I should include a few other chapters on basic techniques that people would use before they got all the way to compilers. So I threw in a chapter on everything I was interested in. (siehe Frenkel)
Nach Abschluss seines Studiums schrieb er dem Verleger und bat die Dinge mit etwas mehr Detail zu schildern.
- Do you mind if I make this book a little bit longer, because I think there’s a need for explaining these things in somewhat more detail.
Die Antwort seines Verlegers fiel positiv aus.
- They said, “Oh no, go right ahead. Make it as long as you feel necessary.”
Der erste handgeschriebene Entwurf von 1967 umfasste 3900 Seiten. So entstand der Plan, eine siebenteilige Reihe zu verfassen, die wesentliche Grundlagen der Computerprogrammierung abdeckt.
Die Darstellung der Beispielprogramme erfolgt dabei in einer von Knuth entwickelten Assemblersprache für eine von ihm entwickelten idealen Computer namens MIX, der in Zukunft durch das "Nachfolgemodell" MMIX abgelöst werden wird. Er begründet den radikalen Schritt der Benutzung einer eigenen Assemblersprache konsequent sowohl mit technischen als auch pädagogischen Argumenten sowie der Absicht, ein langfristiges Werk zu schaffen, das nicht von der jeweiligen Modeprogrammiersprache beeinflusst sein soll.
Die Reihe ist wie folgt geplant:
- Volume 1. Fundamental Algorithms
- Chapter 1: Basic Concepts
- Chapter 2: Information Structures
- Volume 2. Seminumerical Algorithms
- Chapter 3: Random Numbers
- Chapter 4: Arithmetic
- Volume 3. Sorting and Searching
- Chapter 5: Sorting
- Chapter 6: Searching
- Volume 4. Combinatorial Algorithms
- Chapter 7: Combinatorical Searching
- Chapter 8: Recursion
- Volume 5. Syntactical Algorithms
- Chapter 9: Lexical Scanning
- Chapter 10: Parsing
- Volume 6. The Theory of Languages
- Chapter 11: The Theory of Languages
- Volume 7. Compilers
- Chapter 12: Compilers
Bisher sind die ersten drei Teile erschienen, bereits in mehreren überarbeiteten Auflagen. Zu Band 1 erschien 2005 ein Faszikel mit der Spezifikation von MMIX. Band 4 wird ebenfalls seit 2005 vorab in Form von zwei Faszikeln pro Jahr veröffentlicht. Auf der Webseite von Knuth sind jeweils vor der Veröffentlichung als Faszikeln erste Vorabversionen (Pre-Fascicles) verfügbar, damit Interessierte schon vor dem Druck erste Fehler finden können. Im Anschluss wird dann Band 4 in wenigstens 3 Teilbänden veröffentlicht.
Zu den o.g. Büchern kommt ein weiteres von Graham/Knuth/Patashnik Concrete Mathematics, welches die mathematischen Grundlagen von Band 1 in ausführlicherer Form behandelt. Obwohl Don Knuth bereits 1962 mit dem Schreiben begonnen hat, ist noch nicht abzusehen, wann das Werk vollendet sein wird. Der Autor rechnet mit der Fertigstellung von Band 5 im Jahr 2010. Seit 1992 befindet sich Knuth im Ruhestand, um sich ausschliesslich der Fertigstellung seiner Buchreihe zu widmen. Er bekommt dadurch kein Gehalt mehr, andererseits ist The Art of Computer Programming eine kommerziell sehr erfolgreiche Reihe, in den über 20 Jahren wurden jeden Monat zwischen 1000 und 2000 Exemplare verkauft (siehe Frenkel).
Während der Arbeit an der überarbeiteten Neuauflage von Band 2 kämpfte Knuth mit den Unzulänglichkeiten der damaligen Satztechniken und entwickelte schließlich sein eigenes System, das digitale Satzsystem TeX, das mittlerweile als Standard für Publikationen in der Mathematik und den Naturwissenschaften etabliert ist.
Die Akkuratheit seines Werkes, das der American Scientist zu den besten zwölf naturwissenschaftlichen Monographien des 20. Jahrhunderts zählt, ist legendär. Sie liegt Knuth so am Herzen, dass er regelmäßig ausführliche Fehlerkorrekturen bis hin zum kleinsten Satzfehler veröffentlicht und den ersten Finder jedes Fehlers mit einem Scheck über 2,56 US-Dollar honoriert. Die Schecks werden jedoch von den meisten Empfängern nicht eingelöst, sondern eingerahmt.
Literatur
- Frenkel, Karen A.: Donald E. Knuth - Scholar with a Passion for the Particular, Communications of the ACM, October 1987, Volume 30, Number 10
- Knuth, Donald E.: The Art of Computer Programming
- Vol. 1: Fundamental Algorithms, 3rd ed., Addison-Wesley 1997, ISBN 0-201-89683-4, 672 Seiten
- Vol. 2: Seminumerical Algorithms, 3rd ed., Addison-Wesley 1998, ISBN 0-201-89684-2, 784 Seiten
- Vol. 3: Sorting and Searching, 2nd ed., Addison-Wesley 1998, ISBN 0-201-89685-0, 800 Seiten
- Vol. 1, Fascicle 1: MMIX - A RISC Computer for the New Millennium, Addison-Wesley 2005, ISBN 0-201-85392-2, 134 Seiten
- Vol. 4, Fascicle 2: Generating All Tuples and Permutations, Addison-Wesley 2005, ISBN 0-201-85393-0, 127 Seiten