Bulletin Vert n°512
janvier — février 2015

Algorithmes

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.

 

Les Journées Nationales
L’APMEP

Publications
Ressources

Actualités et Informations
Base de ressources bibliographiques

 

Les Régionales de l’APMEP