Tout était pourtant parti d'un bon sentiment (comme souvent) : j'avais voulu illustrer la notion de complexité algorithmique par l'exemple de l'algorithme d'Euclide (plus grand commun dénominateur), dont on sait depuis le XIXe siècle que son le nombre de divisions qu'il nécessite est au plus linéaire en la taille des nombres en cause. Wikipédia et d'autres sites évoquent les travaux de Gabriel Lamé en 1844 ou « vers 1845 », sans plus de précision, ou une vague référence aux Comptes-rendus de l'Académie des Sciences.

Voulant d'une part vérifier ces allégations, d'autre part rendre à l'auteur d'une découverte ce qui lui est dû, j'ai voulu retrouver la publication de Gabriel Lamé. Vous me direz, c'est simple, les Comptes-rendus de l'Académie des Sciences (ou les CRAS, comme les scientifiques français les appelent souvent) sont sur Gallica, et Gallica offre maintenant la recherche en texte plein, telle un vulgaire Google Book Search. (Je sais que je vais faire hurler certains, mais je considère que la recherche en texte plein est une fonctionnalité très importante et très utile.)

Force m'a été de constater que ce n'était pas aussi simple. Déjà, il faut convaincre Gallica que je veux les CRAS, et non des extraits ponctuels de ceux-ci, ou des mentions de ceux-ci dans d'autres textes. Ensuite, il fallait retrouver Gabriel Lamé. La frustration montant, j'ai laissé tomber et j'ai fait ce que j'aurais dû faire depuis le début : sortir le Knuth (je veux dire par là sa grande œuvre, The Art of Computer Programming), volume seminumerical algorithms. qui — comment aurait-on pu en douter — comprend une section entière sur l'algorithme d'Euclide, avec une bibliographie précise, comportant notamment les numéros de volume et de pages où trouver l'article de Lamé dans les CRAS.

Cette anecdote n'a guère d'intérêt si on ne peut pas en tirer quelques traits généraux dépassant l'exposition narcissique d'une vie somme tout assez insignifiante. Quelles leçons donc tirer de cet épisode ?

  1. Toute personne touchant de près ou de loin à l'algorithmique doit avoir une édition du Knuth sous la main. C'est tellement vrai que sur les 4 volumes que j'ai dans mon bureau, les collègues m'en ont emprunté 2 (certains de mes collègues de laboratoire lisant mon blog, ceci doit donc être interprété comme un rappel subtil que ces ouvrages sont appelés à regagner leur étagère un jour, et que je préfère une propriété de vivacité bornée à une propriété de vivacité tout court).

  2. Quand on fait une référence à un travail, on le cite précisément. Renvoyer le lecteur vers des travaux « publiés vers 1945 » ou dans un périodique aussi volumineux que les CRAS ne l'aide guère à retrouver le travail en question. Il en est de même lorsque l'on cite à l'appui d'un fait mathématique, surtout laissé implicite, un ouvrage épais comme Algebra de Serge Lang : ça a à peu près la même utilité que répondre « observe l'Univers » à quelqu'un qui demande comment installer une imprimante sur un Mac.

  3. Le moteur de recherche de Gallica ne semble pas encore très satisfaisant. Sa fonctionnalité plein texte me semble moins bien fonctionner que celle de Google.

J'en profite au passage pour rendre hommage à Donald Knuth. Pour ceux qui ignoreraient de qui il s'agit : Donald Knuth est un professeur émérite d'informatique à l'Université Stanford, en Californie. Il est l'auteur de plusieurs découvertes importantes dans le domaine de l'algorithmique. Cependant, il est plus largement connu comme l'auteur d'un ouvrage de référence très important sur ce sujet, à savoir The Art of Computer Programming, qu'il essaye de compléter avant sa mort.

Donald Knuth est très méticuleux ; ainsi, il cite toujours précisément les travaux qu'il évoque. Mécontent des techniques de typographie mathématique utilisées à l'époque où il a commencé la rédaction de son ouvrage, il a écrit son propre système de mise en page (TeX) et dessiné ses propres polices de caractères (Computer Modern), réalisées à l'aide de son propre système de tracé (METAFONT). Ce système et ces polices, sous des avatars plus modernes (pdfLaTeX etc.) sont devenus le standard pour la plupart des chercheurs en mathématiques, informatique, et pour une bonne partie des physiciens ; ils sont également utilisés dans d'autres domaines du savoir.

J'ai eu l'occasion de voir Donald Knuth exposer, et je l'ai trouvé là encore très clair et méticuleux. Je lui souhaite une longue vie.

(Et quand j'aurai le temps, je rajouterai les références bibliographiques aux articles correspondants sur Wikipédia.)


Allez, une petite référence BibTeX :

@Article{Lame_CRAS_1844,

author = {Gabriel Lamé},

title = {Note sur la limite du nombre des divisions dans la recherche du plus grand commun diviseur entre deux nombres entiers},

journal = {Compte rendu des séances de l'Académie des Sciences},

year = 1844,

language = {langfrench},

pages = {867--870},

volume = 19,

number = 18,

url = {http://gallica.bnf.fr/ark:/12148/bpt6k2978z/f867}

}