Tout le monde s’accorde à dire que The Art of Computer Programming, l’œuvre encyclopédique de Don Knuth, est une contribution majeure au domaine de l’informatique. Pourtant, force est de constater que beaucoup d’enseignants, de chercheurs et de programmeurs ne connaissent que très superficiellement le contenu de TAOCP. J’aimerais donner ici quelques raisons de s’y plonger ou de s’y replonger.

[Les numéros de pages ci-dessous se réfèrent aux dernières éditions parues à la date de décembre 2022.]

  • Une œuvre personnelle. Beaucoup d’ouvrages scientifiques sont totalement impersonnels, et les livres d’informatique n’y font pas exception. Quelle que soit la qualité de leur contenu, ils ne laissent pas transparaître la personnalité ou l’avis de leurs auteurs. Dans TAOCP, au contraire, Knuth nous livre des réflexions et des anecdotes personnelles — toutefois sans utiliser « I » mais plutôt « the author ».

    Deux exemples : Au tout début de la section 2.3 sur les arbres (volume 1 page 308), Knuth nous explique avoir sérieusement considéré de dessiner les arbres du bas vers le haut, c’est-à-dire avec la racine en bas, avant de finalement y renoncer au bout de deux ans. Dans le volume 4B, au tout début de la section 7.2.2.2, Knuth nous donne son avis sur P=NP.

  • L’œuvre d’un programmeur. Knuth est un programmeur. C’est bien connu de tous, car on lui doit notamment TeX, mais aussi The Stanford GraphBase ou encore de nombreux programmes disponibles sur sa page Mais c’est surtout une évidence à la lecture de TAOCP. Là où beaucoup d’auteurs se contenteraient d’algorithmes informels, ou de pseudo-code tout aussi informel, Knuth discute en profondeur la représentation des données et les détails d’implémentation. Et on ne peut douter qu’il a effectivement codé et exécuté tous ces programmes quand on voit l’immense quantité de chiffres et d’illustrations résultant de calculs qui sont donnés dans TAOCP.

    Un exemple : Le nombre de façons de paver l’échiquier avec des monominos, dominos et triominos, à savoir 92 109 458 286 284 989 468 604 (volume 4A page 252).

  • Jubilation. Il n’est pas rare de trouver les mots fun ou encore ta da! dans TAOCP. Partout, on sent la jubilation de l’auteur, et le plaisir qu’il prend à nous présenter une idée, une astuce de programmation, la solution d’un problème ou encore les ressources (temps de calcul, quantité de mémoire) qui ont été nécessaires. Ce n’est pas sans rapport avec le point précédent : le plaisir que l’on perçoit dans TAOCP est souvent lié à la satisfaction d’avoir pu écrire un programme pour résoudre un problème — même si on ressent aussi à d’autres endroits une jubilation purement mathématique.

    Exemple : Knuth calcule le nombre d’entrées dans un cache (pendant le calcul d’un ZDD) et fait remarquer avec un point d’exclamation qu’il s’agit d’un nombre de Fibonacci.

  • La compilation du savoir. L’informatique est une discipline jeune, qui ne bénéficie pas de siècles de décantation et d’organisation de ses concepts, contrairement aux mathématiques et à la physique par exemple. Dès lors, il est important que certains s’attellent à la tâche effrayante consistant à ingérer, ordonner et présenter la multitude de définitions et de résultats.

    Un exemple : Combien d’informaticiens ont compris que les arbres et les arbres binaires ne sont pas la même chose ? On peut difficilement leur en vouloir, tant la chose est mal présentée dans l’immense majorité des livres. C’est pourtant magnifiquement expliqué dans TAOCP volume 1 section 2.3 (page 312).

  • Qualité de la bibliographie. Les références bibliographiques sont pour la plupart présentées en fin de sections, dans un paragraphe Historical notes, même si d’autres sont données au fil de l’eau et dans les solutions des exercices. Ces notes démontrent un travail bibliographique titanesque, quasi exhaustif, devant lequel on ne peut être qu’admiratif. On apprécie en particulier le soin que Knuth met à toujours revenir à la source, en citant en premier lieu les travaux les plus anciens.

    Un exemple : La solution du très joli « problème des ménages » (vol. 4B, exercice 14 page 125) contient pas moins de huit références bibliographiques.

  • Rigueur. Knuth est connu pour offrir 2,56$ (un dollar hexadécimal !) à toute personne trouvant une erreur dans TAOCP — et c’est d’ailleurs rappelé dans la préface de chacun des volumes. Certes, ces récompenses ne sont créditées que sur un compte à la banque de San Serriffe mais c’est dire tout de même l’exigence que Knuth s’impose.

  • Typographie. Qu’on aime ou pas les polices Computer Modern, on ne peut que s’incliner devant la qualité typographique de TAOCP. C’est bien simple : si on a la moindre question de typographie anglo-saxonne, il suffit d’ouvrir TAOCP et d’y chercher la réponse.

    À ce propos, mentionnons que Knuth est l’un des trois auteurs de Mathematical Writing, des notes très complètes sur l’écriture scientifique, issues d’un cours à Stanford.

  • Qualité de l’index. Le soin apporté aux indexes dans TAOCP est admirable. Le volume 4B ne fait “que” 700 pages, mais son index fait 40 pages !

    Les auteurs cités dans TAOCP, en particulier, apparaissent dans les indexes avec leur nom complet, écrit dans l’orthographe latine mais aussi dans l’orthographe d’origine : arabe, cyrillique, japonais, etc.

  • Une quantité incroyable d’information. TAOCP est une œuvre dense, c’est indéniable. De fait, elle constitue une mine incroyable pour des travaux dirigés et pratiques, des sujets d’examens, des oraux, etc. La quantité d’exercices, en particulier, est sidérante. Et la quantité d’information cachée dans les solutions des exercices est tout aussi impressionnante.

    Un exemple : L’algorithme du lièvre et de la tortue n’est qu’un simple exercice au tout début du volume 2 (exercice 6 page 7). Et sa solution est beaucoup plus subtile qu’il n’y paraît.

  • Illustrations. Si on ne recommanderait pas forcément l’outil qui est derrière, à savoir MetaPost, on est obligé de reconnaître que les illustrations dans TAOCP sont nombreuses et très soignées, et représentent un travail colossal.

    Un exemple : Les diagrammes de décision binaire (BDD) de la section 7.1.4 (volume 4A page 202) ou encore l’appendice E du volume 4B.