par Donald E. Knuth
articles choisis et traduits par Patrick Cégielski

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 œuvres aient fait l’objet de nombreuses éditions, elles n’étaient pas encore traduites en français.

co-publication par CSLI Publications et la SMF, 2011
510 pages en 15,5 × 23, prix : 32 €, .ISBN 978-1-57586-620-8

Ce volume, complémentaire du précédent, comporte une préface de l’auteur, une du traducteur et dix-sept chapitres :

• 1. L’informatique et ses rapports avec les mathématiques
  Une discipline à part entière.
• 2 Mathématiques et informatique ; faire face au fini
  Des entiers si grands qu’il faut les manipuler spécifiquement.
• 3 Les algorithmes
  Ne pas se contenter du premier qui vient à l’esprit.
• 4. Les problèmes récréatifs sont-ils utiles ?
  Se plonger immédiatement dans un problème réel ou s’initier peu à peu par des problèmes réels de moins en moins édulcorés.
• 5. Analyse mathématique des algorithmes
  Les aspects techniques de l’analyse quantitative.
• 6. Les dangers de l’informatique théorique
  Même si les entiers sont très grands, ils ne le sont pas suffisamment pour être garantis par les propriétés asymptotiques du modèle.
• 7. L’analyse des algorithmes
  Mieux qu’Euclide pour le PGCD !.
• 8. Notes sur le contournement des instructions goto
  Le passage à la programmation structurée des années 70.
• 9. Programmation structurée avec des instructions goto
  Obtenir des programmes plus efficaces tout en restant lisibles.
• 10. Les liens valsants
  Une méthode réutilisable d’un problème à certains autres.
• 11.Analyse syntaxique descendante
  Le cours d’une école d’été.
• 12. Sur la traduction des langages de gauche à droite
  Les grammaires LR(k) : engendrer un algorithme d’analyse lexicale efficace.
• 13. Sémantique des langages algébriques
  Les grammaires à attributs.
• 14. Sondage linéaire et graphes
  Un problème posé par Philippe Flageolet.
• 15. Recherche rapide de motifs dans les textes
  Le célèbre algorithme KMR.
• 16. Problèmes de mots simples dans les algèbres universelles
  Comment on peut automatiser les exercices d’algèbre y compris à la main.
• 17. Permutations, matrices et tableaux de Young généralisés
  L’algorithme RSK.

Huit pages d’index permettent de retrouver un auteur ou un concept. Les bibliographies qui couvrent le dernier demi-siècle ont été entièrement revues et complétées.

Chaque article comporte une bibliographie et a fait l’objet d’une mise à jour.

L’auteur entraîne avec enthousiasme le lecteur dans les détails d’exemples éclairants et n’hésite pas à manifester son humour : « Il existe de nombreux exemples où les avancées théoriques ont en fait étouffé le développement de la programmation des ordinateurs … J’espère cependant qu’en montrant le revers de la médaille, je ne porterai aucun préjudice à la vente des livres que j’écris. »

La parution de ces traductions arrive à point nommé pour la mise en place d’éléments d’algorithmique dans les programmes des lycées et pour contribuer à la formation des enseignants.