25. Sep 2008, 01:06

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 Programme TeX und Metafont entwickelt hat. 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.

Die Darstellung der Beispielprogramme erfolgt dabei in einer von Knuth entwickelten Assemblersprache für einen von ihm entwickelten fiktiven „idealen“ Computer namens MIX, der in Zukunft durch das „Nachfolgemodell“ MMIX abgelöst werden wird. Er verwendet die Assembler-Sprache MIXAL (MIX-Assembler-Language). Knuth 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.

Inhaltsverzeichnis 1 Aufbau der Buchreihe 2 Arbeitsfortschritt und Würdigung des Werkes 3 Literatur 4 Weblinks 5 Einzelnachweis

[Bearbeiten] 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.

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

[Bearbeiten] 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

[Bearbeiten] Weblinks

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

[Bearbeiten] 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

Dieser Artikel ist eine Kopie aus der freien Enzyklopädie Wikipedia. Am Originalartikel kann jeder Korrekturen und Ergänzungen vornehmen. Zudem kann man frühere Versionen einsehen.

Abkürzungen • Dateiendungen • Netzjargon