- The Art of Computer Programming
-
The Art of Computer Programming (deutsch: Die Kunst der Computerprogrammierung) 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 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.
Inhaltsverzeichnis
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.“[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.”
„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 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 (Erstausgabe 2011)
- Chapter 7: Combinatorical Searching
- Chapter 8: Recursion
- Volume 5. Syntactical Algorithms (geplanter Veröffentlichungstermin 2020)
- 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 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 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. 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 2020. 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[2], 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.[3]
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. 4A: Combinatorial Algorithms, Addison-Wesley 2011, ISBN 0-201-03804-8, 883 Seiten
Weblinks
Einzelnachweis
- ↑ 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
- ↑ American Scientist: 100 or so Books that shaped a Century of Science, von Philip, Phylis Morrison in der Nov/Dez Ausgabe von 1999
- ↑ Donald Knuth: Recent News: Financial Fiasco
Kategorie:- Sachbuch (Informatik)
Wikimedia Foundation.
