vignette|Volumes 1 à 4B
The Art of Computer Programming (TAOCP) est une série de livres en plusieurs volumes sur la programmation informatique, écrits par Donald Knuth.
Historique Donald Knuth étant considéré comme un expert dans l'écriture de compilateurs, il commence à écrire un livre sur la conception de compilateurs en 1962. Il réalise rapidement qu'il devrait considérablement augmenter le domaine traité par son livre. En 1965, Knuth finit d'écrire le premier jet de ce qui devait être un volume unique composé de douze chapitres. Il s'agit d'un manuscrit de . Il suppose qu'une page dactylographiée correspondrait à cinq pages manuscrites. L'éditeur calcule un rapport d'une page manuscrite et demi pour chaque page dactylographiée. Le livre ferait donc . Le plan du livre est donc modifié pour comprendre sept volumes d'un ou deux chapitres chacun. Le a ensuite été divisé en 4A, 4B, 4C et peut-être même 4D.
En 1976, Knuth prépare la deuxième édition du , nécessitant d'être à nouveau mis en page. Mais le style de mise en page n'est plus disponible et le travail doit être refait.
En 1977, Knuth décide de passer quelques mois pour travailler sur un nouvel outil. Huit ans plus tard, il achève TeX, qui est depuis lors utilisé pour tous les volumes.
La célèbre offre d'« un dollar hexadécimal » en récompense de la correction de toute erreur découverte dans les volumes de TAOCP (présente dès la première édition du premier volume) contribue à créer un ouvrage de très grande qualité et continuellement mis à jour. Une autre caractéristique de cet ouvrage est la gradation de difficulté des exercices, qui vont du niveau « échauffement » aux problèmes de recherche encore non résolus.
Cet « art de la programmation » que promeut Knuth part d'un constat : plutôt que de bricoler en assembleur et de faire gagner quelques secondes au programme (une optimisation qui aurait son mérite mais qui ne serait ni universelle ni pérenne, car elle dépendrait trop de la machine sur laquelle tournerait l'algorithme), il vaut mieux prendre du recul sur le problème considéré et étudier les propriétés typiques de ses structures combinatoires via des outils mathématiques ad hoc (Knuth établit très souvent le comportement en moyenne en utilisant des techniques de séries génératrices). Cela permet de mieux affûter l'algorithme et d'obtenir de gigantesques gains d'efficacité. C'est également le sens de son aphorisme : .
Le premier volume s'ouvre par une section d'étude de ces outils (principalement combinatoires) destinés à l'analyse des algorithmes ; avec la collaboration de Ronald Graham et Oren Patashnik, Knuth a largement développé cette section sous forme d'un manuel de combinatoire intitulé Concrete Mathematics.
Contenu Volumes publiés Volume 1 - Fundamental Algorithms (troisième édition 1997) Chapitre 1 – Basic concepts Chapitre 2 – Information structures Volume 2 - Seminumerical Algorithms (troisième édition 1997) Chapitre 3 – Random numbers Chapitre 4 – Arithmetic Volume 3 - Sorting and Searching (deuxième édition, 1998) Chapitre 5 – Sorting techniques Chapitre 6 – Searching techniques Volume 4A - Combinatorial Algorithms, Part 1 (2011) Chapitre 7 – Combinatorial searching (partie 1) Volume 4B - Combinatorial Algorithms, Part 2 (2022) Chapitre 7 – Combinatorial searching (partie 2)
Volumes prévus Volumes 4C et 4D - Combinatorial Algorithms Chapitre 7 – Combinatorial searching Chapitre 8 – Recursion Volume 5 – Syntactic algorithms Chapitre 9 – Lexical scanning Chapitre 10 – Parsing techniques Volume 6 – Theory of languages Chapitre 11 – Mathematical linguistics Volume 7 – Compiler Chapitre 12 – Programming language translation
En 2022, sur les sept volumes initialement prévus, seuls l’entièreté des trois premiers volumes et les deux premiers tomes du quatrième volume ont été publiés. Le ou les autres tomes prévus pour le quatrième volume, Combinatorial Algorithms, sont en cours de rédaction, certaines parties étant disponibles en ligne pour relectureConsulter TAOCP.
Notes et références
Voir aussi
Articles connexes MMIX (architecture logicielle utilisée dans TAOCP) IBM 650
Liens externes
Naissance et influence de TAOCP
Catégorie:Livre d'informatique Catégorie:Programmation informatique Catégorie:Donald Knuth