Die Kunst der Computerprogrammierung (Akronym: TAOCP) ist eine umfassende Monografie, die von Donald Knuth geschrieben ist, der viele Arten bedeckt, Algorithmen und ihre Analyse zu programmieren.

Knuth hat das Projekt, ursprünglich konzipiert als ein einzelnes Buch mit zwölf Kapiteln 1962 begonnen. Wie man dann erwartete, waren die ersten drei wovon ein siebenbändiger Satz wurden 1968, 1969, und 1973 veröffentlicht. Die erste Rate des Bands 4 (ein Paperback-Bündel) wurde 2005 veröffentlicht. Der Band 4A des eingebundenen Buches wurde 2011 veröffentlicht. Zusätzliche Bündel-Raten werden für die Ausgabe ungefähr halbjährlich geplant.

Geschichte

Nach dem Gewinnen einer Westinghouse Talent-Suchgelehrsamkeit hat sich Knuth am Fall-Institut für die Technologie eingeschrieben (jetzt Fall Westreserveuniversität), wo seine Leistung so hervorragend war, dass die Fakultät gestimmt hat, um ihn ein Master der Wissenschaft nach seiner Vollziehung des Vordiplom-Grads zuzuerkennen. Während seiner Sommerurlaube wurde Knuth angestellt, um Bearbeiter zu schreiben, mehr in seinen Sommermonaten verdienend, als volle Professoren das ganze Jahr getan hat. Solche Großtaten haben Knuth ein Thema der Diskussion unter der Mathematik-Abteilung gemacht, die Richard S. Varga eingeschlossen hat.

Knuth hat angefangen, ein Buch über das Bearbeiter-Design 1962 zu schreiben, und hat bald begriffen, dass das Spielraum des Buches viel größer sein musste. Im Juni 1965 hat Knuth den ersten Entwurf dessen beendet, was ursprünglich geplant wurde, um ein einzelnes Volumen von zwölf Kapiteln zu sein. Sein handschriftliches Manuskript des ersten Entwurfs (vollendet 1966) war 3,000 Seiten lang: Er hatte angenommen, dass ungefähr fünf handschriftliche Seiten in eine gedruckte Seite übersetzen würden, aber sein Herausgeber hat stattdessen gesagt, dass ungefähr 1½ handschriftliche Seiten zu einer gedruckter Seite übersetzt haben. Das hat bedeutet, dass das Buch etwa 2,000 Seiten in der Länge sein würde. Der Herausgeber war über das Annehmen solch eines Projektes von einem Studenten im Aufbaustudium nervös. An diesem Punkt hat Knuth Unterstützung von Richard S. Varga erhalten, der der wissenschaftliche Berater vom Herausgeber war. Varga besuchte Olga Taussky-Todd und John Todd an Caltech. Mit der begeisterten Indossierung von Varga hat der Herausgeber die ausgebreiteten Pläne von Knuth akzeptiert. In seiner ausgebreiteten Version würde das Buch in sieben Volumina, jedem mit gerade einem oder zwei Kapiteln veröffentlicht. Wegen des Wachstums im Material hat sich der Plan für den Band 4 seitdem ausgebreitet, um Bände 4A, 4B, 4C, und vielleicht mehr einzuschließen.

1976 hat Knuth eine zweite Ausgabe des Bands 2 vorbereitet, es verlangend, Schriftsatz wieder zu sein, aber der Stil des Typs, der in der Erstausgabe verwendet ist (hat heißen Typ genannt), war nicht mehr verfügbar. 1977 hat er sich dafür entschieden, ein paar Monate auszugeben, etwas Passenderes verarbeitend. Acht Jahre später ist er mit TeX zurückgekehrt, der zurzeit für alle Volumina verwendet wird.

Das berühmte Angebot einer Belohnung überprüft wert "einem hexadecimal Dollar" (100 Basis 16 Cent, in der Dezimalzahl, sind 2.56 $) für irgendwelche Fehler gefunden, und die Korrektur dieser Fehler in nachfolgendem printings, hat hoch poliert und noch herrische Natur der Arbeit lange nach seiner ersten Veröffentlichung beigetragen. Eine andere Eigenschaft der Volumina ist die Schwankung in der Schwierigkeit der Übungen. Das Niveau der Schwierigkeit erstreckt sich von "Aufwärmen"-Übungen bis ungelöste Forschungsprobleme, eine Herausforderung für jeden Leser zur Verfügung stellend. Die Hingabe von Knuth ist auch berühmt:

Zusammenbau-Sprache im Buch

Alle Beispiele in den Büchern verwenden eine Sprache genannt "MISCHUNGS-Zusammenbau-Sprache", die auf dem hypothetischen MISCHUNGS-Computer läuft. (Zurzeit wird der MISCHUNGS-Computer durch den MMIX Computer ersetzt, der eine RISC Version ist.) Software wie GNU besteht MDK, um Wetteifer der MISCHUNGS-Architektur zur Verfügung zu stellen.

Einige Leser werden durch den Gebrauch der Zusammenbau-Sprache beiseite gelegt, aber Knuth betrachtet das als notwendig, weil Algorithmen im Zusammenhang in der Größenordnung von ihrem Geschwindigkeits- und zu beurteilenden Speichergebrauch sein müssen. Das beschränkt wirklich jedoch die Zugänglichkeit des Buches für einige Leser, die mit dem Zusammenbau nicht vertraut sein können, oder wer widerwillig sein kann, Zusammenbau-Sprachcode in eine höhere Programmiersprache zu übersetzen. (Mehrere alternative Lehrbücher mit Beispielen der höheren Programmiersprache bestehen.)

Kritische Antwort

Amerikanischer Wissenschaftler hat diese Arbeit unter "ungefähr 100 Büchern eingeschlossen, die ein Jahrhundert der Wissenschaft gestaltet haben", sich auf das 20. Jahrhundert beziehend, und innerhalb der Informatik-Gemeinschaft es als das erste und dennoch die beste umfassende Behandlung seines Themas betrachtet wird. Deckel der dritten Ausgabe des Bands 1 zitieren Bill Gates, "Wenn Sie denken, dass Sie ein wirklich guter Programmierer … die Kunst von gelesenem (Knuth) des Computers sind, … Programmierend, sollten Sie mir einen résumé bestimmt senden, wenn Sie alles lesen können." Die New York Times hat es als "die Definieren-Abhandlung des Berufs" gekennzeichnet.

Volumina

• Band 1 - Grundsätzliche Algorithmen (Kapitel 1 und 2)
• Band 2 - Halbnumerische Algorithmen (Kapitel 3 und 4)
• Band 3 - Sortierend und Forschend (Kapitel 5 und 6)
• Band 4 - Kombinatorische Algorithmen (Kapitel 7 und 8, die in mehreren Subvolumina veröffentlicht sind)
• Band 5 - Syntaktische Algorithmen (bezüglich 2011, geschätzt 2020) (Kapitel 9 und 10)
• Band 6 - Die Theorie von Sprachen ohne Zusammenhänge hat (geplant)
• Band 7 - Bearbeiter-Techniken haben (geplant)

Kapitel

• Kapitel 1 - Grundlegende Konzepte (Band 1)
• Kapitel 2 - Informationsstrukturen (Band 1)
• Kapitel 3 - Zufallszahlen (Band 2)
• Kapitel 4 - Arithmetik (Band 2)
• Kapitel 5 - das Sortieren (des Bands 3)
• Kapitel 6 - Forschend (Bands 3)
• Kapitel 7 - Kombinatorische Suche (Band 4)
• Kapitel 8 - Recursion (Band 4)
• Kapitel 9 - Lexikalische Abtastung (schließt auch Schnur-Suche und Datenkompression ein) (Band 5)
• Kapitel 10 - Syntaxanalyse von Techniken (Band 5)

Kapitel-Umriss von veröffentlichten Volumina

• Band 1 - Grundsätzliche Algorithmen
• Kapitel 1 - Grundlegende Konzepte
• 1.1. Algorithmen
• 1.2. Mathematische Einleitungen
• 1.2.1. Mathematische Induktion
• 1.2.2. Zahlen, Mächte und Logarithmen
• 1.2.3. Summen und Produkte
• 1.2.4. Funktionen der ganzen Zahl und Elementare Zahlentheorie
• 1.2.5. Permutations und Factorials
• 1.2.6. Binomische Koeffizienten
• 1.2.7. Harmonische Zahlen
• 1.2.8. Fibonacci-Zahlen
• 1.2.9. Das Erzeugen von Funktionen
• 1.2.10. Analyse eines Algorithmus
• 1.2.11. Asymptotische Darstellungen
• 1.2.11.1. Die O-Notation
• 1.2.11.2. Die Summierungsformel von Euler
• 1.2.11.3. Einige asymptotische Berechnungen
• 1.3 MMIX (VERMISCHEN SICH in der Kopie des eingebundenen Buches, aber aktualisiert durch das Bündel 1)
• 1.3.1. Beschreibung von MMIX
• 1.3.2. Die MMIX Zusammenbau-Sprache
• 1.3.3. Anwendungen auf Versetzungen
• 1.4. Einige Grundsätzliche Programmiertechniken
• 1.4.1. Unterprogramme
• 1.4.2. Koroutinen
• 1.4.3. Interpretierende Routinen
• 1.4.3.1. Ein MISCHUNGS-Simulator
• 1.4.3.2. Spur-Routinen
• 1.4.4. Eingang und Produktion
• 1.4.5. Geschichte und Bibliografie
• Kapitel 2 - Informationsstrukturen
• 2.1. Einführung
• 2.2. Geradlinige Listen
• 2.2.1. Stapel, Warteschlangen und Deques
• 2.2.2. Folgende Zuteilung
• 2.2.3. Verbundene Zuteilung
• 2.2.4. Kreisförmige Listen
• 2.2.5. Doppelt Verbundene Listen
• 2.2.6. Reihe und Orthogonale Listen
• 2.3. Bäume
• 2.3.1. Das Überqueren Binärer Bäume
• 2.3.2. Binäre Baumdarstellung von Bäumen
• 2.3.3. Andere Darstellungen von Bäumen
• 2.3.4. Grundlegende Mathematische Eigenschaften von Bäumen
• 2.3.4.1. Freie Bäume
• 2.3.4.2. Orientierte Bäume
• 2.3.4.3. Das "Unendlichkeitslemma"
• 2.3.4.4. Enumeration von Bäumen
• 2.3.4.5. Pfad-Länge
• 2.3.4.6. Geschichte und Bibliografie
• 2.3.5. Listen und Müll-Sammlung
• 2.4. Mehrverbundene Strukturen
• 2.5. Dynamische Lagerungszuteilung
• 2.6. Geschichte und Bibliografie
• Band 2 - Halbnumerische Algorithmen
• Kapitel 3 - Zufallszahlen
• 3.1. Einführung
• 3.2. Das Erzeugen Gleichförmiger Zufallszahlen
• 3.2.1. Die Geradlinige Congruential Methode
• 3.2.1.1. Wahl des Moduls
• 3.2.1.2. Wahl des Vermehrers
• 3.2.1.3. Stärke
• 3.2.2. Andere Methoden
• 3.3. Statistische Tests
• 3.3.1. Allgemeine Testverfahren, um Zufällige Daten Zu studieren
• 3.3.2. Empirische Tests
• 3.3.3. Theoretische Tests
• 3.3.4. Der Geisterhafte Test
• 3.4. Andere Typen von Zufälligen Mengen
• 3.4.1. Numerischer Vertrieb
• 3.4.2. Zufällige Stichprobenerhebung und das Schlurfen
• 3.5. Was Ist eine Zufallsfolge?
• 3.6. Zusammenfassung
• Kapitel 4 - Arithmetik
• 4.1. Stellungszahl-Systeme
• 4.2. Das Schwimmen der Punkt-Arithmetik
• 4.2.1. Berechnungen der einfachen Präzision
• 4.2.2. Genauigkeit der Schwimmpunkt-Arithmetik
• 4.2.3. Berechnungen der doppelten Genauigkeit
• 4.2.4. Vertrieb von Schwimmpunkt-Zahlen
• 4.3. Vielfache Präzisionsarithmetik
• 4.3.1. Die Klassischen Algorithmen
• 4.3.2. Modularithmetik
• 4.3.3. Wie Schnell können Wir Multiplizieren?
• 4.4. Basis-Konvertierung
• 4.5. Vernünftige Arithmetik
• 4.5.1. Bruchteile
• 4.5.2. Der Größte Allgemeine Teiler
• 4.5.3. Analyse des Algorithmus von Euklid
• 4.5.4. Factoring in die Blüte
• 4.6. Polynomische Arithmetik
• 4.6.1. Abteilung von Polynomen
• 4.6.2. Factorization von Polynomen
• 4.6.3. Einschätzung von Mächten
• 4.6.4. Einschätzung von Polynomen
• 4.7. Manipulation der Macht-Reihe
• Band 3 - das Sortieren und die Suche
• Kapitel 5 - Sortierend
• 5.1. Kombinatorische Eigenschaften von Versetzungen
• 5.1.1. Inversionen
• 5.1.2. Versetzungen eines Mehrsatzes
• 5.1.3. Läufe
• 5.1.4. Tableux und Involutions
• 5.2. Das innere Sortieren
• 5.2.1. Das Sortieren durch die Einfügung
• 5.2.2. Das Sortieren, indem es Wert gewesen

• 5.2.3. Das Sortieren durch die Auswahl
• 5.2.4. Das Sortieren durch das Mischen
• 5.2.5. Das Sortieren durch den Vertrieb
• 5.3. Optimum, das Sortiert
• 5.3.1. Minimaler Vergleich, der Sortiert
• 5.3.2. Minimaler Vergleich, der Sich Verschmilzt
• 5.3.3. Auswahl des minimalen Vergleichs
• 5.3.4. Netze, um Zu sortieren
• 5.4. Das Außensortieren
• 5.4.1. Mehrwegige sich verschmelzende und Ersatzauswahl
• 5.4.2. Die Polyphase-Verflechtung
• 5.4.3. Die Kaskadeverflechtung
• 5.4.4. Das Lesen des Bandes Umgekehrt
• 5.4.5. Die Schwingende Sorte
• 5.4.6. Praktische Rücksichten für das Band, das Sich Verschmilzt
• 5.4.7. Außenbasis, die Sortiert
• 5.4.8. Das Zwei-Bänder-Sortieren
• 5.4.9. Platten und Trommeln
• 5.5. Zusammenfassung, Geschichte und Bibliografie
• Kapitel 6 - Suchend
• 6.1. Folgende Suche
• 6.2. Suche vergleichsweise Schlüssel
• 6.2.1. Suche eines Bestellten Tisches
• 6.2.2. Binärer Baum, der Sucht
• 6.2.3. Erwogene Bäume
• 6.2.4. Mehrwegige Bäume
• 6.3. Digitalsuche
• 6.4. Hashing
• 6.5. Wiederauffindung auf Sekundären Schlüsseln
• Band 4A - Kombinatorische Algorithmen, Teil 1
• Kapitel 7 - Kombinatorische Suche
• 7.1. Nullen und
• 7.1.1. Boolean-Grundlagen
• 7.1.2. Boolean-Einschätzung
• 7.1.3. Bitwise-Tricks und Techniken
• 7.1.4. Binäre Entscheidungsdiagramme
• 7.2. Das Erzeugen Aller Möglichkeiten
• 7.2.1. Das Erzeugen Grundlegender Kombinatorischer Muster
• 7.2.1.1. Das Erzeugen aller N-Tupel
• 7.2.1.2. Das Erzeugen aller Versetzungen
• 7.2.1.3. Das Erzeugen aller Kombinationen
• 7.2.1.4. Das Erzeugen aller Teilungen
• 7.2.1.5. Das Erzeugen aller Satz-Teilungen
• 7.2.1.6. Das Erzeugen aller Bäume
• 7.2.1.7. Geschichte und weitere Verweisungen

Umriss von unveröffentlichten Abteilungen

• Band 4B, 4C...
• Kapitel 7 - Kombinatorische Suche (cont'd)
• 7.2. Das Erzeugen aller Möglichkeiten (cont'd)
• 7.2.2. Grundlegender Rückzug
• 7.2.2.1. Das Tanzen von Verbindungen
• 7.2.2.2. Satisfiability
• 7.2.3. Das effiziente Zurückverfolgen
• 7.3. Kürzeste Pfade
• 7.4. Graph-Algorithmen
• 7.4.1. Bestandteile und Traversal
• 7.4.2. Spezielle Klassen von Graphen
• 7.4.3. Expander-Graphen
• 7.4.4. Zufällige Graphen
• 7.5. Netzalgorithmen
• 7.5.1. Verschiedene Vertreter
• 7.5.2. Das Anweisungsproblem
• 7.5.3. Netz überflutet
• 7.5.4. Optimale Subbäume
• 7.5.5. Optimum, das zusammenpasst
• 7.5.6. Optimale Einrichtung
• 7.6. Unabhängigkeitstheorie
• 7.6.1. Unabhängigkeitsstrukturen
• 7.6.2. Effiziente matroid Algorithmen
• 7.7. Getrennte dynamische Programmierung
• 7.8. Branch-Bound-Techniken
• 7.9. Herkulische Aufgaben (auch bekannt als NP-hard Probleme)
• 7.10. Nahe Optimierung
• Kapitel 8 - Recursion
• Band 5 - Syntaktische Algorithmen (geschätzt 2020)
• Kapitel 9 - Lexikalische Abtastung (schließt auch Schnur-Suche und Datenkompression ein)
• Kapitel 10 - Syntaxanalyse von Techniken

Englische Ausgaben

Aktuelle Ausgaben

Das sind die aktuellen Ausgaben in der Ordnung durch die Volumen-Zahl:

• Band 1: Grundsätzliche Algorithmen. Die dritte Ausgabe (das Lesen, Massachusetts: Addison-Wesley, 1997), xx+650pp. Internationale Standardbuchnummer 0-201-89683-4
• Band 1, Bündel 1: MMIX - Ein RISC Computer für das Neue Millennium. (Addison-Wesley, am 14. Februar 2005) internationale Standardbuchnummer 0-201-85392-2 (wird in der vierten Ausgabe des Bands 1 sein)
• Band 2: Halbnumerische Algorithmen. Die dritte Ausgabe (das Lesen, Massachusetts: Addison-Wesley, 1997), xiv+762pp. Internationale Standardbuchnummer 0-201-89684-2
• Band 3: Das Sortieren und die Suche. Die zweite Ausgabe (das Lesen, Massachusetts: Addison-Wesley, 1998), xiv+780pp. + ausfaltbare Seite. Internationale Standardbuchnummer 0-201-89685-0
• Band 4A: Kombinatorische Algorithmen, Teil 1. Erstausgabe (das Lesen, Massachusetts: Addison-Wesley, 2011), xv+883pp. Internationale Standardbuchnummer 0-201-03804-8
• Die Kunst der Computerprogrammierung, Volumina 1-4A In Schachteln gepackter Satz 3. Ausgabe (das Lesen, Massachusetts: Addison-Wesley, 2011), 3168pp. Internationale Standardbuchnummer 0321751043

Vorherige Ausgaben

Ganze Volumina

Diese Volumina wurden durch neuere Ausgaben ersetzt und sind in der Ordnung durch das Datum.

• Band 1, Erstausgabe, 1968, xxi+634pp, internationale Standardbuchnummer 0-201-03801-3.
• Band 2, Erstausgabe, 1969, xi+624pp, internationale Standardbuchnummer 0-201-03802-1.
• Band 3, Erstausgabe, 1973, xi+723pp+centerfold, internationale Standardbuchnummer 0 201 03803 X
• Band 1, die zweite Ausgabe, 1973, xxi+634pp, internationale Standardbuchnummer 0-201-03809-9.
• Band 2, die zweite Ausgabe, 1981, xiii + 688pp, internationale Standardbuchnummer 0-201-03822-6.

Bündel

Bündel des Bands 4 0-4 wurden revidiert und als Band 4A veröffentlicht.

• Band 4, Bündel 0: Einführung in kombinatorische Algorithmen und Funktionen von Boolean, (Addison-Wesley Professional, am 28. April 2008) vi+240pp, internationale Standardbuchnummer 0-321-53496-4
• Band 4, Bündel 1: Tricks von Bitwise & Techniken; binäre Entscheidungsdiagramme (Addison-Wesley Professional, am 27. März 2009) viii+260pp, internationale Standardbuchnummer 0-321-58050-8
• Band 4, Bündel 2: Alle Tupel und Versetzungen, (Addison-Wesley, am 14. Februar 2005) v+127pp, internationale Standardbuchnummer 0-201-85393-0 erzeugend
• Band 4, Bündel 3: Das Erzeugen aller Kombinationen und Teilungen. (Addison-Wesley, am 26. Juli 2005) vi+150pp, internationale Standardbuchnummer 0-201-85394-9
• Band 4, Bündel 4: Alle Bäume — Geschichte der kombinatorischen Generation, (Addison-Wesley, am 6. Februar 2006) vi+120pp, internationale Standardbuchnummer 0-321-33570-8 erzeugend

Referenzen

</klein>

Kommentare

Links

• Übersicht von Themen (die persönliche Einstiegsseite von Knuth)
• Mündliches Geschichtsinterview mit Donald E. Knuth am Institut von Charles Babbage, der Universität Minnesotas, Minneapolis. Knuth bespricht das Softwarepatentieren, die strukturierte Programmierung, die Kollaboration und seine Entwicklung von TeX. Die mündliche Geschichte bespricht das Schreiben Der Kunst der Computerprogrammierung.
• "Robert W Floyd, In Memoriam", durch Donald E. Knuth - (auf dem Einfluss von Bob Floyd)
• Wer ist Bill Gosper? (auf dem Einfluss von Bill Gosper auf der 2. Ausgabe des Bands 2.)
• TAoCP und sein Einfluss der Informatik (Softpanorama)