par Donald E. Knuth
traduit de l’anglais par Patrick Cégielski.

co-publication par CSLI Publications et la SMF, 2011
388 pages en 15,5 × 23, prix : 32 €, ISBN : 978-1-57586-622-2

David Knuth fut et reste un des pionniers de l’algorithmique et de la programmation, ayant créé une partie importante du vocabulaire (« analyse des algorithmes », « problème NP-complet », …), des notions nouvelles (grammaires à attributs), et le logiciel de traitement de texte TEx. Bien que ses oeuvres aient fait l’objet de nombreuses éditions, elles n’étaient pas encore traduites en français.

L’informatique est une science jeune, comparée, par exemple, aux mathématiques.

Néanmoins elle est suffisamment ancienne, et a suffisamment évolué depuis ses débuts, pour faire l’objet d’une étude historique.

Laissant à d’autres (cités en bibliographie) l’histoire des progrès techniques des machines, ce livre étudie plus précisément l’histoire de l’algorithmique et de la programmation.

Ce volume réunit : une préface de l’auteur, une préface du traducteur, et quinze articles, de longueur très inégale (de 1 à 97 pages), écrits ou co-écrits par Knuth entre 1962 et 2000 ; ils ne sont pas classés selon la chronologie de leur rédaction, mais plutôt selon celle des sujets abordés.

Leurs titres sont :

• 1. Algorithmes babyloniens anciens.
• 2. Algorithmes, mathématiques modernes et informatique.
• 3. Le premier programme informatique de Von Neumann.
• 4. Les premiers développements des langages de programmation.
• 5. Une histoire de la conception des compilateurs.
• 6. Découper un paragraphe en lignes.
• 7. La genèse des grammaires à attributs.
• 8. Algorithme et programme ; information et données.
• 9. Programmation et informatique.
• 10. Forme normale de Backus contre Forme de Backus-Naur.
• 11. Grand omicron, grand omega et grand théta.
• 12. Une proposition de terminologie.
• 13. Postcriptum sur les problèmes NP-difficiles.
• 14. L’art de programmer les ordinateurs.
• 15. Origine de l’expression « analyse des algorithmes ».

Chaque chapitre ou presque comprend une bibliographie abondante ; beaucoup bénéficient d’un addendum où est évoquée l’évolution du sujet traité depuis la date d’écriture.

L’ouvrage est complété par un Index.

Ce livre devrait faire date dans l’histoire des sciences. Il dépasse le cadre de l’informatique pour chercher les racines de l’algorithmique aussi bien chez les Babyloniens que chez les Arabes ou les copistes médiévaux.

Outre les historiens, le lectorat visé comprend tous les informaticiens, professionnels ou amateurs, donc une part importante des enseignants et étudiants en mathématiques.

L’auteur s’appuie sur une vaste documentation incluant des manuscrits non publiés.

Dans le monumental chapitre 4, il traduit un même algorithme en 20 langages, dont certains jamais implémentés sur machine, avec commentaires ligne par ligne : il fait ainsi vivre l’évolution de la programmation. Si la lecture de certains textes, qui entrent dans les détails techniques de la programmation, demande une bonne connaissance du vocabulaire spécialisé, d’autres sont purement factuels, avec souvent des traits d’humour.

La rédaction est toujours très claire. L’accent est mis sur la différence entre modes de pensée mathématiques et informatiques, ainsi qu’entre algorithmique (qualifiée d’abstraite) et programmation (concrète). Celle-ci est présentée sous le double visage de Science et d’Art, car incluant des choix esthétiques et des émotions.

La double casquette de l’auteur, à la fois historien de l’informatique et acteur de son développement, n’est pas sans poser quelques problèmes d’objectivité ; ainsi les 97 pages du chapitre 6 peuvent être perçues comme une promotion du logiciel TEX ; elles n’en sont pas moins éclairantes sur la complexité (inattendue par le profane) des problèmes de typographie, et sur les moyens mis en œuvre pour les résoudre.

Pour être honnête je me dois de signaler l’abondance de fautes d’orthographe et de français ; le traducteur, qui a participé au choix des articles et à leur révision, et a complété la bibliographie, domine mieux la syntaxe des langages informatiques que celle du français (ah ! l’accord des participes !) Mais le lecteur a cette supériorité sur l’ordinateur de corriger facilement chacun de ces « bugs ».