Accueil » Publications » Le Bulletin Vert » Matériaux pour une documentation » Algorithmes.
  APMEP   Algorithmes.

Article du bulletin 512

Adhérer ou faire un don

Paul Louis Hennequin

- 9 février 2015 -

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 x 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.

 Accueil   Plan du site   Haut de la page   Page précédente