TAOCP

The Art of Computer Programming ist ein mehrbändiges Werk des 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 wird in Zukunft durch das „Nachfolgemodell“ MMIX abgelöst. Er verwendet die Assembler-Sprache MIXAL (MIX-Assembler-Language). 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." (deutsch: „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, das mich interessiert, hinzu.“) ^[1]

Nach Abschluss seines Studiums schrieb er dem Verleger und bat um die Erlaubnis, 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." (deutsch: „Würde es Ihnen etwas ausmachen, wenn ich das Buch ein bisschen ausführlicher machen würde; denn ich denke, es bedarf einer etwas detaillierteren Erklärung.“)

Die Antwort seines Verlegers fiel positiv aus.

"They said, 'Oh no, go right ahead. Make it as long as you feel necessary.'” (deutsch: „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 ist 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 (Teile zur Überprüfung veröffentlicht)

Chapter 7: Combinatorical Searching

Chapter 8: Recursion

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

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 Heft (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 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 2015. 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 den über 20 Jahren wurden jeden Monat zwischen 1000 und 2000 Exemplare verkauft ^[1].

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, 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.^[2]

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. 1, Fascicle 1: MMIX - A RISC Computer for the New Millennium, Addison-Wesley 2005, ISBN 0-201-85392-2, 134 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. 4, Fascicle 0: Introduction to Combinatorial Algorithms and Boolean Functions, Addison-Wesley 2008, ISBN 0-321-53496-4, 216 Seiten
  • Vol. 4, Fascicle 2: Generating All Tuples and Permutations, Addison-Wesley 2005, ISBN 0-201-85393-0, 127 Seiten
  • Vol. 4, Fascicle 3: Generating All Combinations and Partitions, Addison-Wesley 2005, ISBN 0-201-85394-9, ca. 150 Seiten
  • Vol. 4, Fascicle 4: Generating All Trees; History of Combinatorial Generation, Addison-Wesley 2006, ISBN 0-321-33570-8, 128 Seiten

Weblinks

• http://www-cs-faculty.stanford.edu/~knuth/taocp.html

Einzelnachweis

1. ↑ ^{a b} Frenkel, Karen A.: Donald E. Knuth - Scholar with a Passion for the Particular, Communications of the ACM, October 1987, Volume 30, Number 10
2. ↑ Donald Knuth: Recent News: Financial Fiasco