The Art of Computer Programming

The Art of Computer Programming (TAOCP, deutsch Die Kunst der Computerprogrammierung) ist eine mehrbändige Monografie des US-amerikanischen Informatikers Donald E. Knuth über grundlegende Algorithmen und Datenstrukturen, für dessen Textsatz er die Programme TeX und Metafont entwickelt hat.

Die Beispielprogramme werden in einer von Knuth erdachten Assemblersprache dargestellt, die er für einen fiktiven „idealen“ Computer namens MIX entwickelte; dieser wurde mit Band 4a durch das „Nachfolgemodell“ MMIX abgelöst. Er verwendet die Assembler-Sprache MIXAL (MIX-Assembler-Language). Es ist geplant, die Bände 1–3 zu überarbeiten und alle Codebeispiele auf MMIX umzuschreiben. Knuth begründet den radikalen Schritt, eine eigene Assemblersprache zu benutzen, 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.

Vom Compilerbuch zum mehrbändigen Grundlagenwerk

Ursprünglich hatte der Verleger Knuth, der damals noch ein Student im Hauptstudium war, 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.”

„Ich dachte, wenn ich ein Buch über Compiler schreibe, dann sollte ich ein paar Kapitel über grundlegende Techniken einfügen, mit denen die Leute in Berührung kommen, bevor sie auf Compiler stoßen. So packte ich ein Kapitel über jedes Thema, für das ich mich interessierte, hinzu.“

Nach Abschluss seines Studiums schrieb er dem Verleger und bat um die Erlaubnis, die Dinge etwas mehr im 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.”

„Würde es Ihnen etwas ausmachen, wenn ich das Buch ein bisschen ausführlicher machen würde, da ich denke, dass diese Dinge einer etwas detaillierteren Erklärung bedürfen.“

Die Antwort seines Verlegers fiel positiv aus.

“They said, ‚Oh no, go right ahead. Make it as long as you feel necessary.’”

„Sie sagten: ‚Aber nein, fangen Sie gleich an. Machen Sie es so umfangreich, wie Sie es für nötig halten.‘“

Der erste handgeschriebene Entwurf von 1967 umfasste 3900 Seiten. So entstand der Plan, eine siebenteilige Reihe zu verfassen, die wesentliche Grundlagen der Computerprogrammierung abdeckt.

Aufbau der Buchreihe

Die Reihe war wie folgt geplant:

Volume 1. Fundamental Algorithms (Erstausgabe 1968)

Chapter 1: Basic Concepts

Chapter 2: Information Structures

Volume 2. Seminumerical Algorithms (Erstausgabe 1969)

Chapter 3: Random Numbers

Chapter 4: Arithmetic

Volume 3. Sorting and Searching (Erstausgabe 1973)

Chapter 5: Sorting

Chapter 6: Searching

Volume 4. Combinatorial Algorithms (Erstausgabe 2011)

Chapter 7: Combinatorial Searching

Chapter 8: Recursion

Volume 5. Syntactical Algorithms (geplanter Veröffentlichungstermin 2030)

Chapter 9: Lexical Scanning

Chapter 10: Parsing

Volume 6. The Theory of Context Free Languages

Chapter 11: The Theory of Context Free Languages

Volume 7. Compilers

Chapter 12: Compilers

Bisher sind die ersten drei Teile und ein Kapitel erschienen, bereits in mehreren überarbeiteten Auflagen. Zu Band 1 erschien 2005 ein Faszikel mit der Spezifikation von MMIX. Band 4 wurde ebenfalls seit 2005 vorab in Form von zwei Faszikeln pro Jahr veröffentlicht. Band 4A liegt seit Februar 2011 vor. Auf Knuths Webseite 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. Die Bände 4B und 4C (und womöglich noch weitere) sollen folgen.

Zu den oben genannten Büchern kommt ein weiteres, von Graham/Knuth/Patashnik Concrete Mathematics, welches die mathematischen Grundlagen von Band 1 in ausführlicherer Form behandelt.

Arbeitsfortschritt und Würdigung des Werkes

Obwohl 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 2030 und plant anschließend eine (erneute) Aktualisierung und Überarbeitung der Bände 1 bis 3 sowie die Zusammenfassung der wichtigsten Inhalte der fünf Bände in einem neuen Werk. Die „stärker spezialisierten“ Bände 6 und 7 wolle er danach nur schreiben, sofern ihre Themen dann „noch relevant (seien) und noch nicht gesagt wurden“.

Seit 1992 befindet sich Knuth im Ruhestand, um sich ausschließlich 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 der Zeit vom Ersterscheinungsdatum bis 1987 wurden jeden Monat zwischen 1000 und 2000 Exemplare verkauft.

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 Akkuratesse seines Werkes, das der American Scientist zu den besten zwölf naturwissenschaftlichen Monographien des 20. Jahrhunderts zählt, 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 256 US-Cent für inhaltliche Fehler bzw. 32 US-Cent für Kommafehler u. ä. honoriert. Die Schecks werden jedoch von den meisten Empfängern nicht eingelöst – nur neun wurden eingelöst –, sondern eingerahmt. Seit Oktober 2008 werden die Schecks jedoch nicht mehr in US-Dollar, sondern in der virtuellen, hexadezimalen Währung der Bank of San Serriffe ausgestellt – dies begründet Knuth mit der Angst vor Scheckbetrug.

Am Ende der einzelnen Kapitel gibt es einen Abschnitt zu Geschichte und Bibliographie mit historischen Informationen. Die Übungsaufgaben sind nach Schwierigkeitsgrad eingeteilt (und entsprechend markiert), die von extrem einfach (00) bis zum bis dahin nicht gelösten Forschungsproblem (50) reichen.

Literatur

• Karen A. Frenkel: Donald E. Knuth – Scholar with a Passion for the Particular. In: Communications of the ACM. Vol. 30, No. 10, Oktober 1987.
• Donald E. Knuth: The Art of Computer Programming
  • Vol. 1: Fundamental Algorithms. 3rd edition. Addison-Wesley 1997, ISBN 0-201-89683-4.
  • Vol. 1, Fascicle 1: MMIX – A RISC Computer for the New Millennium. Addison-Wesley 2005, ISBN 0-201-85392-2.
  • Vol. 2: Seminumerical Algorithms. 3rd edition. Addison-Wesley 1998, ISBN 0-201-89684-2.
  • Vol. 3: Sorting and Searching. 2nd edition. Addison-Wesley 1998, ISBN 0-201-89685-0.
  • Vol. 4A: Combinatorial Algorithms. Addison-Wesley 2011, ISBN 0-201-03804-8.
  • Vol. 4B: Combinatorial Algorithms. Addison-Wesley 2022, ISBN 0-201-03806-4.

Weblinks

• The Art of Computer Programming (TAOCP) auf der Website von Donald E. Knuth