The Art of Computer Programming

The Art of Computer Programming

The Art of Computer Programming (TAOCP) est une série de livres en plusieurs volumes sur la programmation informatique, écrits par Donald Knuth. Seuls les trois premiers ont été publiés en entier, le premier tome du quatrième volume étant paru début 2011 :

  • Volume 1, Fundamental Algorithms (troisième édition 1997);
  • Volume 2, Seminumerical Algorithms (troisième édition 1997);
  • Volume 3, Sorting and Searching (seconde édition, 1998);
  • Volume 4A, Enumeration and Backtracking (2011);

Les deux autres tomes prévus pour le quatrième volume, Combinatorial Algorithms, sont en cours de rédaction. Certaines parties sont d'ailleurs disponibles sur la page de TAOCP. Au total, sept volumes sont prévus.

Sommaire

Histoire

Donald Knuth étant considéré expert dans l'écriture de compilateurs, il commença à écrire un livre sur la conception de compilateurs en 1962. Il réalisa 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'agissait d'un manuscrit de 3 000 pages. Il supposait qu'une page dactylographiée correspondrait à cinq pages manuscrites. L'éditeur calcula un rapport d'une page manuscrite et demi pour chaque page dactylographiée. Le livre ferait donc 2 000 pages. Le plan du livre fut donc modifié pour comprendre sept volumes d'un ou deux chapitres chacun. Le volume 4 a ensuite été divisé en 4A, 4B, 4C et peut-être même 4D.

En 1976, Knuth prépara la seconde édition du volume 2, nécessitant d'être à nouveau mis en page. Mais le style de mise en page n'était plus disponible et le travail devait être refait. En 1977, Knuth décida de passer quelques mois pour travailler sur un nouvel outil. Huit ans plus tard, il avait achevé TeX, qui est depuis lors utilisé pour tous les volumes.

La célèbre offre de récompense d'« un dollar hexadécimal » en récompense de la correction de toute erreur découverte dans les livres (présente dès la première édition du premier volume), contribua à 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 non encore résolus.

Cet Art de Programmer que promeut Knuth consiste en le message suivant : plutôt que de hacker en assembleur et de faire gagner quelques secondes au programme (ce serait une optimisation qui a son mérite mais qui n'est pas universelle ni pérenne car elle dépend trop de la machine sur lequel tournera l'algorithme), il vaut mieux prendre du recul sur le problème considéré, en extraire les structures combinatoires en jeu, étudier via les outils mathématiques ad hoc les propriétés typiques de ces structures (Knuth établit très souvent le comportement en moyenne en utilisant des techniques de séries génératrices), ce qui permet au final de mieux affûter l'algorithme à utiliser, et d'avoir ainsi de gigantesques gains d'efficacité. C'est également là le sens qu'il faut donner à son aphorisme « L'optimisation prématurée est la source de tous les maux (ou presque) en programmation ».

Annexes

Articles connexes

  • MMIX (architecture logicielle utilisée dans TAOCP)

Liens externes


Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article The Art of Computer Programming de Wikipédia en français (auteurs)

Игры ⚽ Поможем решить контрольную работу

Regardez d'autres dictionnaires:

  • The Art of Computer Programming — [ [http://www cs faculty.stanford.edu/ uno/taocp.html The Art of Computer Programming ] ] is a comprehensive monograph written by Donald Knuth that covers many kinds of programming algorithms and their analysis. Knuth began the project, which was …   Wikipedia

  • 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.… …   Deutsch Wikipedia

  • The art of computer programming — The Art of Computer Programming, en abrégé TAOCP, est une série de livres en plusieurs volumes sur la programmation informatique, écrits par Donald Knuth. Actuellement, seuls les trois premiers ont été publiés : Volume 1, Fundamental… …   Wikipédia en Français

  • The Art of Computer Programming — (literalmente El arte de programar computadoras en español) es una extensa monografía escrita por Donald Knuth que cubre los algoritmos de programación y su análisis. Knuth inició el proyecto en 1962, originalmente concebido como un solo libro de …   Wikipedia Español

  • Computer programming — Programming redirects here. For other uses, see Programming (disambiguation). Software development process Activities and steps …   Wikipedia

  • The Art Institute of California — San Francisco — This article describes the Art Institute of California San Francisco, which should not be confused with the unaffiliated San Francisco Art Institute. Infobox University name = The Art Institute of California San Francisco motto = established… …   Wikipedia

  • Computer Modern — Category Serif Classification Didone Designer(s) Donald Kn …   Wikipedia

  • The Complexity of Songs — was an article published by Donald Knuth, an example of an in joke in computer science, namely, in computational complexity theory. The article capitalizes on the tendency of popular songs to evolve from long and content rich ballads to highly… …   Wikipedia

  • Computer program — A computer program (also software, or just a program) is a sequence of instructions written to perform a specified task with a computer.[1] A computer requires programs to function, typically executing the program s instructions in a central… …   Wikipedia

  • Computer-Algebra — Die Computeralgebra ist das Teilgebiet der Mathematik, das sich mit der symbolischen Manipulation algebraischer Ausdrücke beschäftigt. Inhaltsverzeichnis 1 Zweck 2 Effiziente exakte Arithmetik mit ganzen Zahlen 3 Effiziente exakte Arithmetik mit… …   Deutsch Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”