Brigitte Vallée (GREYC)

L’algorithme d’Euclide est, selon Knuth lui-même, le grand-père de tous les algorithmes. Bien qu’il soit universellement utilisé, sa complexité fine est encore mal connue. En particulier, il est essentiel de bien analyser son nombre d’itérations, l’évolution des restes, la taille des quotients, puisque ces paramètres décrivent précisément la complexité fine de l’algorithme, qui est sa complexité en bits. De plus, l’algorithme d’Euclide ‘‘classique’’ admet de nombreuses variantes, selon les divisions qu’on utilise. Citons l’algorithme binaire, l’algorithme qui travaille avec les bits les moins significatifs, l’algorithme rapide de Knuth et Schonhage,…

La plupart des questions naturelles sur le comportement probabiliste de tous ces algorithmes sont restées ouvertes jusqu’à une date très récente.

Tous les résultats les plus récents sont obtenus par la même méthode générale, introduite par le groupe de Caen et ses collaborateurs(trices). C’est la méthode d’analyse dynamique, qui voit un algorithme comme un système dynamique. Comme d’habitude en analyse d’algorithmes, on considère aussi les fonctions génératrices, qui sont alors, dans ce cadre, elles-mêmes engendrées par l’opérateur de transfert du système dynamique sous-jacent. Même si les différents algorithmes d’Euclide donnent lieu à des systèmes dynamiques dont la géométrie est vraiment différente, une telle méthode est un outil très puissant qui permet de résoudre (presque) toutes les questions concernant l’analyse de ces algorithmes.