The Art of Computer Programming. Donald E. Knuth. Addison-Wesley, 1997/2011.

Souvent cité, mais rarement lu. Et c’est vraiment dommage, parce que c’est d’une incroyable richesse. Contient d’innombrables pépites, jusque dans les corrections d’exercices (très nombreux). C’est dense, c’est vrai, et il faut parfois du temps pour digérer une seule page. Mais on ne regrettera pas le temps passé. Ceux qui s’arrêtent à la présence de code assembleur n’ont rien compris.

Algorithms, 4th Edition. Robert Sedgewick, Kevin Wayne. Addison-Wesley, 2011.

Le meilleur livre d’algorithmique selon moi. Illustrations magnifiques et exemples très nombreux. Code Java limpide. (Le choix de Java apparaît comme très pertinent au final.) Le site web donne accès à tout le code, mais aussi aux fichiers de données et même aux transparents de cours.

Attention : il s’agit là de la quatrième édition ; c’est important.

The Practice of Programming. Brian W. Kernighan, Rob Pike. Addison-Wesley, 1999.

L’achat de ce livre est justifié à lui seul par les trois dernières pages qui collectent une petite centaine de conseils en matière de programmation. On devrait les faire apprendre aux étudiants ; on devrait les appliquer nous-mêmes. Plus généralement, tout le livre est exceptionnel de recul et de pertinence sur la programmation.

Il y a par ailleurs un message implicite : le langage de programmation importe beaucoup moins qu’on ne le pense.

Computer Systems: A Programmer’s Perspective. Randal E. Bryant, David R. O’Hallaron. Pearson, 2011.

Tout ce que le programmeur doit savoir au sujet du matériel, du système, du compilateur, etc., pour mieux programmer. Probablement le seul livre dans lequel un chapitre entier est consacré à l’édition de liens.

Écrit par des programmeurs, pour les programmeurs.

Purely Functional Data Structures. Chris Okasaki. Cambridge University Press, 1998.

Avant tout un livre qui explique merveilleusement bien ce que sont les structures de données purement applicatives, leur intérêt, leur mise en œuvre et leur analyse de complexité, notamment en présence d’amortissement et d’évaluation paresseuse. Des tonnes de structures de données, dont certaines revisitées avec beaucoup d’élégance. Un exemple : les tas binomiaux. Code SML limpide, expliqué ligne par ligne.

Programming Pearls. Jon Bentley. Addison-Wesley, 1986.

N’a pas pris une seule ride. Plein de conseils pour mieux programmer. Le style est parfait, ainsi que les exemples. Quelques chapitres que j’ai particulièrement aimés : Writing Correct Programs, The Back of the Envelope, Sorting et *Heaps.

Comme indiqué dans la préface : This book is written for programmers.

Hacker’s Delight. Henry S. Warren. Addison-Wesley, 2003.

Des astuces arithmétiques par centaines, toutes plus savoureuses les unes que les plus autres. Si certaines sont de l’ordre de l’amusement uniquement (mais à ne pas dénier, du coup), beaucoup sont éminemment utiles en pratique. Ce livre explique par exemple comment votre compilateur se passe d’une division lorsque votre code divise par une constante.

Le site n’existe plus, malheureusement, mais est archivé ici.

Algorithms on Strings, Trees, and Sequences. Dan Gusfield. Cambridge University Press, 1997.

C’est essentiellement un livre d’algorithmique du texte, avec de nombreux algorithmes très bien expliqués (et prouvés !). Il y a toute une partie sur les arbres de suffixes, et notamment une excellente explication de l’algorithme d’Ukkonen (notoirement difficile à comprendre et à coder). Contient d’innombrables applications de ces algorithmes.

The Elements of Computing Systems. Noam Nisan, Shimon Schocken. MIT Press, 2008.

Quoi de mieux pour tout comprendre que de tout construire soi-même ? C’est le parti pris de ce livre, où le lecteur est invité à construire une machine, puis un assembleur, puis un compilateur, puis enfin un système d’exploitation. (Des interprètes sont fournis à tous les niveaux.) Même sans prendre le temps de faire soi-même toute cette construction, la lecture de ce livre vaut le coup. À dévorer de préférence d’une seule traite.

Un site accompagne le livre : www.nand2tetris.org