L'art de la programmation informatique -The Art of Computer Programming
Auteur | Donald Knuth |
---|---|
Pays | États Unis |
Langue | Anglais |
Genre |
Monographie de non-fiction |
Éditeur | Addison-Wesley |
Date de publication |
1968– (le livre est encore incomplet) |
Type de support | Imprimer ( Couverture rigide ) |
ISBN | 0-201-03801-3 |
519 | |
Classe LC | QA76.75 |
The Art of Computer Programming ( TAOCP ) est une monographie complèteécrite par l' informaticien Donald Knuth qui couvre de nombreux types d' algorithmes de programmation et leur analyse .
Knuth a commencé le projet, conçu à l'origine comme un livre unique avec douze chapitres, en 1962. Les trois premiers volumes de ce qui devait alors être un ensemble de sept volumes ont été publiés en 1968, 1969 et 1973. Le travail a commencé sérieusement sur Volume 4 en 1973, mais a été suspendu en 1977 pour des travaux de composition induits par la deuxième édition du volume 2. La rédaction de la copie finale du volume 4A a commencé à la main en 2001, et le premier pré-fascicule en ligne, 2A, est paru plus tard en 2001 Le premier tome publié du Volume 4 est apparu en livre de poche sous le nom de Fascicule 2 en 2005. Le Volume 4A relié, combinant le Volume 4, Fascicule 0–4, a été publié en 2011. Le Volume 4, Fascicule 6 (« Satisfiabilité ») a été publié en décembre. 2015 ; Le volume 4, Fascicule 5 (« Mathematical Preliminaries Redux ; Backtracking ; Dancing Links ») est sorti en novembre 2019.
Les fascicules 5 et 6 devraient constituer les deux premiers tiers du volume 4B. Knuth n'a annoncé aucune date estimée pour la sortie du volume 4B, bien que sa méthode utilisée pour le volume 4A consiste à publier le volume cartonné quelque temps après la sortie des fascicules de poche qu'il contient. Les estimations à court terme des éditeurs placent la date de sortie à mai ou juin 2019, ce qui s'est avéré incorrect.
Histoire
Après avoir remporté une bourse Westinghouse Talent Search , Knuth s'est inscrit au Case Institute of Technology (maintenant Case Western Reserve University ), où sa performance était si exceptionnelle que la faculté a voté pour lui attribuer une maîtrise en sciences à l'issue de son baccalauréat. Pendant ses vacances d'été, Knuth a été embauché par la Burroughs Corporation pour écrire des compilateurs , gagnant plus pendant ses mois d'été que les professeurs titulaires pendant une année entière. De tels exploits ont fait de Knuth un sujet de discussion au sein du département de mathématiques, qui comprenait Richard S. Varga .
En janvier 1962, alors qu'il était étudiant diplômé au département de mathématiques de Caltech, Knuth a été approché par Addison-Wesley pour écrire un livre sur la conception de compilateurs, et il a proposé une portée plus large. Il a proposé une liste de 12 titres de chapitre le même jour. Au cours de l'été 1962, il a travaillé sur un compilateur FORTRAN pour UNIVAC. Pendant ce temps, il a également proposé une analyse mathématique du sondage linéaire , qui l'a convaincu de présenter le matériel avec une approche quantitative. Après avoir obtenu son doctorat en juin 1963, il a commencé à travailler sur son manuscrit, dont il a terminé sa première ébauche en juin 1965, à3000 pages manuscrites. Il avait supposé qu'environ cinq pages écrites à la main se traduiraient en une page imprimée, mais son éditeur a dit à la place qu'environ 1+1 ⁄ 2 pages manuscrites traduites en une page imprimée. Cela signifiait qu'il avait environ2000 pages imprimées de matériel, ce qui correspond étroitement à la taille des trois premiers volumes publiés. L'éditeur était nerveux à l'idée d'accepter un tel projet d'un étudiant diplômé. À ce stade, Knuth a reçu le soutien de Richard S. Varga, qui était le conseiller scientifique de l'éditeur. Varga rendait visite à Olga Taussky-Todd et John Todd à Caltech . Avec l'approbation enthousiaste de Varga, l'éditeur a accepté les plans élargis de Knuth. Dans sa version augmentée, le livre serait publié en sept volumes, chacun avec seulement un ou deux chapitres. En raison de la croissance du chapitre 7, qui comptait moins de 100 pages du manuscrit de 1965, par vol. 4A p. vi, le plan pour le volume 4 a depuis été étendu pour inclure les volumes 4A, 4B, 4C, 4D, et peut-être plus.
En 1976, Knuth a préparé une deuxième édition du volume 2, exigeant qu'il soit à nouveau composé , mais le style de caractère utilisé dans la première édition (appelé hot type ) n'était plus disponible. En 1977, il décide de passer du temps à créer quelque chose de plus approprié. Huit ans plus tard, il revient avec T E X , qui est actuellement utilisé pour tous les volumes.
L'offre d'un chèque de récompense Knuth d'une valeur de "un dollar hexadécimal" (100 HEX base 16 cents, en décimal , est de 2,56 $) pour toutes les erreurs trouvées, et la correction de ces erreurs dans les impressions suivantes, a contribué à la finition très soignée et encore la nature faisant autorité de l'ouvrage, longtemps après sa première publication. Une autre caractéristique des volumes est la variation de la difficulté des exercices. Knuth a même une échelle de difficulté numérique pour évaluer ces exercices, variant de 0 à 50, où 0 est trivial et 50 est une question ouverte dans la recherche contemporaine.
La dédicace de Knuth se lit comme suit :
Cette série de livres est affectueusement dédiée
à l' ordinateur Type 650 une fois installé au
Case Institute of Technology ,
avec qui j'ai passé de nombreuses soirées agréables.
Langage d'assemblage dans le livre
Tous les exemples dans les livres utilisent un langage appelé " langage d'assemblage MIX ", qui s'exécute sur l'ordinateur MIX hypothétique. Actuellement, l'ordinateur MIX est remplacé par l' ordinateur MMIX , qui est une version RISC . Des logiciels tels que GNU MDK existent pour fournir une émulation de l'architecture MIX. Knuth considère l'utilisation du langage d'assemblage nécessaire pour évaluer la vitesse et l'utilisation de la mémoire des algorithmes.
Réponse critique
Knuth a reçu le prix Turing 1974 "pour ses contributions majeures à l' analyse des algorithmes […], et en particulier pour ses contributions à 'l'art de la programmation informatique' à travers ses livres bien connus dans une série continue portant ce titre." American Scientist a inclus ce travail parmi les "100 livres environ qui ont façonné un siècle de science", se référant au vingtième siècle, et au sein de la communauté informatique, il est considéré comme le premier et toujours le meilleur traitement complet de son sujet. Les couvertures de la troisième édition du volume 1 citent Bill Gates disant : « Si vous pensez que vous êtes un très bon programmeur… lisez (Knuth) Art of Computer Programming … Vous devriez certainement m'envoyer un CV si vous pouvez tout lire. " Le New York Times l'a qualifié de « traité définissant la profession ».
Volumes
Complété
- Volume 1 – Algorithmes fondamentaux
- Chapitre 1 – Concepts de base
- Chapitre 2 – Structures informationnelles
- Volume 2 – Algorithmes semi-numériques
- Chapitre 3 – Nombres aléatoires
- Chapitre 4 – Arithmétique
- Volume 3 – Tri et recherche
- Volume 4A – Algorithmes
combinatoires
- Chapitre 7 – Recherche combinatoire (partie 1)
Prévu
- Volume 4B... – Algorithmes combinatoires (chapitres 7 & 8 publiés en plusieurs sous-volumes)
- Chapitre 7 – Recherche combinatoire (suite)
- Chapitre 8 – Récursivité
- Volume 5 – Algorithmes syntaxiques
- Chapitre 9 – Analyse lexicale (comprend également la recherche de chaînes et la compression de données )
- Chapitre 10 – Techniques d' analyse
- Volume 6 – La théorie des langages sans contexte
- Volume 7 – Techniques de compilation
Aperçu des chapitres
Complété
Volume 1 – Algorithmes fondamentaux
- Chapitre 1 – Concepts de base
- 1.1. Algorithmes
- 1.2. Préliminaires mathématiques
- 1.2.1. Induction mathematique
- 1.2.2. Nombres, puissances et logarithmes
- 1.2.3. Sommes et produits
- 1.2.4. Fonctions entières et théorie des nombres élémentaires
- 1.2.5. Permutations et factorielles
- 1.2.6. Coefficients binomiaux
- 1.2.7. Numéros d'harmoniques
- 1.2.8. Nombres de Fibonacci
- 1.2.9. Génération de fonctions
- 1.2.10. Analyse d'un algorithme
- 1.2.11. Représentations asymptotiques
- 1.2.11.1. La notation O
- 1.2.11.2. Formule de sommation d'Euler
- 1.2.11.3. Quelques calculs asymptotiques
- 1.3 MMIX ( MIX dans la copie cartonnée mais mis à jour par le fascicule 1)
- 1.3.1. Description de MMIX
- 1.3.2. Le langage assembleur MMIX
- 1.3.3. Applications aux permutations
- 1.4. Quelques techniques de programmation fondamentales
- 1.4.1. Sous-programmes
- 1.4.2. Coroutines
- 1.4.3. Routines d'interprétation
- 1.4.3.1. Un simulateur de MIX
- 1.4.3.2. Routines de suivi
- 1.4.4. Entrée et sortie
- 1.4.5. Histoire et bibliographie
- Chapitre 2 – Structures informationnelles
- 2.1. introduction
- 2.2. Listes linéaires
- 2.2.1. Piles, files d'attente et demandes
- 2.2.2. Allocation séquentielle
- 2.2.3. Allocation liée ( tri topologique )
- 2.2.4. Listes circulaires
- 2.2.5. Listes doublement chaînées
- 2.2.6. Tableaux et listes orthogonales
- 2.3. Des arbres
- 2.3.1. Traverser les arbres binaires
- 2.3.2. Arbre binaire Représentation des arbres
- 2.3.3. Autres représentations des arbres
- 2.3.4. Propriétés mathématiques de base des arbres
- 2.3.4.1. Arbres gratuits
- 2.3.4.2. Arbres orientés
- 2.3.4.3. Le "lemme de l'infini"
- 2.3.4.4. Dénombrement des arbres
- 2.3.4.5. Longueur du trajet
- 2.3.4.6. Histoire et bibliographie
- 2.3.5. Listes et collecte des ordures ménagères
- 2.4. Structures multiliées
- 2.5. Allocation de stockage dynamique
- 2.6. Histoire et bibliographie
Volume 2 – Algorithmes semi-numériques
- Chapitre 3 – Nombres aléatoires
- 3.1. introduction
- 3.2. Génération de nombres aléatoires uniformes
- 3.2.1. La méthode linéaire congruente
- 3.2.1.1. Choix du module
- 3.2.1.2. Choix du multiplicateur
- 3.2.1.3. Puissance
- 3.2.2. Autres méthodes
- 3.2.1. La méthode linéaire congruente
- 3.3. Tests statistiques
- 3.3.1. Procédures de test générales pour l'étude de données aléatoires
- 3.3.2. Tests empiriques
- 3.3.3. Tests théoriques
- 3.3.4. Le test spectral
- 3.4. Autres types de quantités aléatoires
- 3.4.1. Distributions numériques
- 3.4.2. Échantillonnage aléatoire et brassage
- 3.5. Qu'est-ce qu'une séquence aléatoire ?
- 3.6. Sommaire
- Chapitre 4 – Arithmétique
- 4.1. Systèmes de numérotation positionnelle
- 4.2. Arithmétique à virgule
flottante
- 4.2.1. Calculs en simple précision
- 4.2.2. Précision de l'arithmétique à virgule flottante
- 4.2.3. Calculs en double précision
- 4.2.4. Distribution des nombres à virgule flottante
- 4.3. Arithmétique à précision multiple
- 4.3.1. Les algorithmes classiques
- 4.3.2. Arithmétique modulaire
- 4.3.3. À quelle vitesse pouvons-nous multiplier?
- 4.4. Radix Conversion
- 4.5. Arithmétique
rationnelle
- 4.5.1. Fractions
- 4.5.2. Le plus grand diviseur commun
- 4.5.3. Analyse de l'algorithme d' Euclide
- 4.5.4. Prise en compte des nombres premiers
- 4.6. Arithmétique
polynomiale
- 4.6.1. Division des polynômes
- 4.6.2. Factorisation de polynômes
- 4.6.3. Évaluation des puissances ( exponentiation de la chaîne d'addition )
- 4.6.4. Évaluation des polynômes
- 4.7. Manipulation de la série de puissance
Volume 3 – Tri et recherche
- Chapitre 5 – Tri
- 5.1. Propriétés combinatoires des permutations
- 5.1.1. Inversions
- 5.1.2. Permutations d'un multi-ensemble
- 5.1.3. Courses
- 5.1.4. Tableaux et involutions
- 5.2. Tri interne
- 5.2.1. Tri par insertion
- 5.2.2. Trier en échangeant
- 5.2.3. Tri par sélection
- 5.2.4. Trier par fusion
- 5.2.5. Tri par distribution
- 5.3. Tri optimal
- 5.3.1. Tri par comparaison minimale
- 5.3.2. Fusion de comparaison minimale
- 5.3.3. Sélection de comparaison minimale
- 5.3.4. Réseaux de tri
- 5.4. Tri externe
- 5.4.1. Fusion multivoie et sélection de remplacement
- 5.4.2. La fusion polyphasée
- 5.4.3. La fusion en cascade
- 5.4.4. Lecture de la bande à l'envers
- 5.4.5. Le tri oscillant
- 5.4.6. Considérations pratiques pour la fusion de bandes
- 5.4.7. Tri par base externe
- 5.4.8. Tri à deux bandes
- 5.4.9. Disques et Tambours
- 5.5. Résumé, histoire et bibliographie
- 5.1. Propriétés combinatoires des permutations
- Chapitre 6 – Recherche
Volume 4A – Algorithmes combinatoires, partie 1
- Chapitre 7 – Recherche combinatoire
- 7.1. Des zéros et des uns
- 7.1.1. Bases booléennes
- 7.1.2. Évaluation booléenne
- 7.1.3. Astuces et techniques au niveau du bit
- 7.1.4. Diagrammes de décision binaire
- 7.2. Générer toutes les possibilités
- 7.2.1. Génération de motifs combinatoires de base
- 7.2.1.1. Génération de tous les n- uplets
- 7.2.1.2. Générer toutes les permutations
- 7.2.1.3. Générer toutes les combinaisons
- 7.2.1.4. Génération de toutes les partitions
- 7.2.1.5. Génération de toutes les partitions définies
- 7.2.1.6. Générer tous les arbres
- 7.2.1.7. Histoire et autres références
- 7.2.1. Génération de motifs combinatoires de base
- 7.1. Des zéros et des uns
Prévu
Volume 4B, 4C, 4D – Algorithmes combinatoires
- Chapitre 7 – Recherche combinatoire (suite)
- 7.2. Générer toutes les possibilités (suite)
- 7.2.2. Backtrack programmation (publié dans le Fascicule 5)
- 7.2.2.1. Liens de danse (publié dans le Fascicule 5)
- 7.2.2.2. Satisfaction (publié dans le Fascicule 6)
- 7.2.2.3. Satisfaction des contraintes
- 7.2.2.4. Sentiers et cycles hamiltoniens (ébauche en ligne dans le pré-fascicule 8A)
- 7.2.2.5. Les cliques
- 7.2.2.6. Covers ( couverture Vertex , Set problème de couverture , couverture exacte , couverture Clique )
- 7.2.2.7. Carrés
- 7.2.2.8. Un pot-pourri de puzzles (ébauche en ligne dans le pré-fascicule 9B) (comprend l'invariant numérique parfait )
- 7.2.2.9. Estimation des coûts de retour en arrière (chapitre 6 des « Articles sélectionnés sur l'analyse des algorithmes » et Fascicule 5, pp 44-47, sous le titre « Estimations du temps d'exécution »)
- 7.2.3. Génération de modèles inéquivalents (comprend une discussion sur le théorème d'énumération de Pólya ) (voir « Techniques de rejet des isomorphes », Ch 4 de « Algorithmes de classification pour les codes et les conceptions » par Kaski et Östergård)
- 7.2.2. Backtrack programmation (publié dans le Fascicule 5)
- 7.3. Chemins les plus courts
- 7.4. Algorithmes de graphes
- 7.4.1. Composants et parcours
- 7.4.2. Classes spéciales de graphiques
- 7.4.3. Graphes d'expansion
- 7.4.4. Graphiques aléatoires
- 7.5. Graphiques et optimisation
- 7.5.1. Appariement bipartite (y compris correspondance de cardinalité maximale , Problème de mariage stable , Mariages Stables )
- 7.5.2. Le problème d'affectation
- 7.5.3. Flux réseau
- 7.5.4. Sous-arbres optimaux
- 7.5.5. Correspondance optimale
- 7.5.6. Commandes optimales
- 7.6. Théorie de l'indépendance
- 7.6.1. Structures d'indépendance
- 7.6.2. Efficaces matroïdes algorithmes
- 7.7. Programmation dynamique discrète (voir aussi Méthode de la matrice de transfert )
- 7.8. Techniques de branchement et de liaison
- 7.9. Tâches herculéennes (alias problèmes NP-difficiles )
- 7.10. Quasi-optimisation
- 7.2. Générer toutes les possibilités (suite)
- Chapitre 8 – Récursivité (chapitre 22 de « Articles sélectionnés sur l'analyse des algorithmes »)
Volume 5 – Algorithmes syntaxiques
- Chapitre 9 – Analyse lexicale (comprend également la recherche de chaînes et la compression de données)
- Chapitre 10 – Techniques d' analyse
Volume 6 – La théorie des langages sans contexte
Volume 7 – Techniques de compilation
éditions anglaises
Éditions actuelles
Voici les éditions courantes classées par numéro de tome :
-
L'Art de la Programmation Informatique, Coffret Volumes 1-4A . Troisième édition (Reading, Massachusetts : Addison-Wesley, 2011), 3168pp. ISBN 978-0-321-75104-1 , 0-321-75104-3
- Tome 1 : Algorithmes fondamentaux . Troisième édition (Reading, Massachusetts : Addison-Wesley, 1997), xx+650pp. ISBN 978-0-201-89683-1 , 0-201-89683-4 . Errata : [1] (2011-01-08), [2] (2020-03-26, 27e impression ). Additif : [3] (2011).
- Tome 2 : Algorithmes semi-numériques . Troisième édition (Reading, Massachusetts : Addison-Wesley, 1997), xiv+762pp. ISBN 978-0-201-89684-8 , 0-201-89684-2 . Errata : [4] (2011-01-08), [5] (2020-03-26, 26e impression). Addenda : [6] (2011).
- Volume 3 : Tri et recherche . Deuxième édition (Reading, Massachusetts : Addison-Wesley, 1998), xiv+780pp.+foldout. ISBN 978-0-201-89685-5 , 0-201-89685-0 . Errata : [7] (2011-01-08), [8] (2020-03-26, 27e impression). Addenda : [9] (2011).
- Volume 4A : Algorithmes combinatoires, partie 1 . Première édition (Reading, Massachusetts : Addison-Wesley, 2011), xv+883pp. ISBN 978-0-201-03804-0 , 0-201-03804-8 . Errata : [10] (2020-03-26, ? impression).
- Volume 1, Fascicule 1 : MMIX – Un ordinateur RISC pour le nouveau millénaire . (Addison-Wesley, 2005-02-14) ISBN 0-201-85392-2 . Errata : [11] (2020-03-16) (sera dans la quatrième édition du volume 1)
- Volume 4, Fascicule 5 : Mathématiques préliminaires Redux ; Retour en arrière ; Liens de danse . (Addison-Wesley, 2019-11-22) xiii+382pp, ISBN 978-0-13-467179-6 . Errata : [12] (2020-03-27) (fera partie du volume 4B)
- Volume 4, Fascicule 6 : Satisfaction . (Addison-Wesley, 2015-12-08) xiii+310pp, ISBN 978-0-13-439760-3 . Errata : [13] (2020-03-26) (fera partie du volume 4B)
Éditions précédentes
Volumes complets
Ces volumes ont été remplacés par des éditions plus récentes et sont classés par date.
- Tome 1 : Algorithmes fondamentaux . Première édition, 1968, xxi+634pp, ISBN 0-201-03801-3 .
- Tome 2 : Algorithmes semi-numériques . Première édition, 1969, xi+624pp, ISBN 0-201-03802-1 .
- Volume 3 : Tri et recherche . Première édition, 1973, xi+723pp+foldout, ISBN 0-201-03803-X . Errata : [14] .
- Tome 1 : Algorithmes fondamentaux . Deuxième édition, 1973, xxi+634pp, ISBN 0-201-03809-9 . Errata : [15] .
- Tome 2 : Algorithmes semi-numériques . Deuxième édition, 1981, xiii+ 688pp, ISBN 0-201-03822-6 . Errata : [16] .
- L'art de la programmation informatique, coffrets volumes 1-3 . Deuxième édition (Reading, Massachusetts : Addison-Wesley, 1998), pp. ISBN 978-0-201-48541-7 , 0-201-48541-9
Fascicule
Les fascicules 0-4 du tome 4 ont été révisés et publiés en tant que tome 4A :
- Volume 4, Fascicule 0 : Introduction aux algorithmes combinatoires et aux fonctions booléennes . (Addison-Wesley Professional, 2008-04-28) vi+240pp, ISBN 0-321-53496-4 . Errata : [17] (2011-01-01).
- Volume 4, Fascicule 1 : Astuces et techniques au niveau des bits ; Diagrammes de décision binaire . (Addison-Wesley Professional, 2009-03-27) viii+260pp, ISBN 0-321-58050-8 . Errata : [18] (2011-01-01).
- Volume 4, Fascicule 2 : Génération de tous les tuples et permutations . (Addison-Wesley, 2005-02-14) v+127pp, ISBN 0-201-85393-0 . Errata : [19] (2011-01-01).
- Volume 4, Fascicule 3 : Génération de toutes les combinaisons et partitions . (Addison-Wesley, 2005-07-26) vi+150pp, ISBN 0-201-85394-9 . Errata : [20] (2011-01-01).
- Volume 4, Fascicule 4 : Génération de tous les arbres ; Histoire de la génération combinatoire . (Addison-Wesley, 2006-02-06) vi+120pp, ISBN 0-321-33570-8 . Errata : [21] (2011-01-01).
Les fascicules 5-6 du tome 4 feront partie du tome 4B :
- Volume 4, Fascicule 5 : Mathématiques préliminaires Redux ; Retour en arrière ; Liens de danse . (Addison-Wesley, 2019-11-22) xiii+382pp, ISBN 978-0-13-467179-6 . Errata : [22] (2020-03-27)
- Volume 4, Fascicule 6 : Satisfaction . (Addison-Wesley, 2015-12-08) xiii+310pp, ISBN 978-0-13-439760-3 . Errata : [23] (2020-03-26)
Pré-fascicule
Les pré-fascicules 5A, 5B et 5C du Volume 4 ont été révisés et publiés en tant que fascicule 5.
Le pré-fascicule 6A du tome 4 a été révisé et publié en tant que fascicule 6.
- Volume 4, Pré-fascicule 8A : Chemins et cycles hamiltoniens
- Volume 4, Pré-fascicule 9B : Un pot-pourri de puzzles
Voir également
Les références
Remarques
Citations
Sources
- Slater, Robert (1987). Portraits au silicium . MIT Appuyez sur . ISBN 0-262-19262-4.
- Shasha, Dennis ; Lazère, Cathy (1995). Out of Their Minds: Les vies et les découvertes de 15 grands informaticiens . Copernic. ISBN 0-387-97992-1.
Liens externes
- Aperçu des sujets (page d'accueil personnelle de Knuth)
- Entretien d'histoire orale avec Donald E. Knuth au Charles Babbage Institute , Université du Minnesota, Minneapolis. Knuth discute des brevets logiciels, de la programmation structurée , de la collaboration et de son développement de TeX . L'histoire orale traite de l'écriture de L'art de la programmation informatique .
- "Robert W Floyd, In Memoriam", de Donald E. Knuth - (sur l'influence de Bob Floyd )
- TAoCP et son influence sur l'informatique (Softpanorama)