Loïck Lhôte (GREYC)

Depuis une dizaine d’années, le groupe de Caen a développé une méthode originale pour l’analyse des algorithmes qui calculent le pgcd de deux entiers. Cette méthode appelée Analyse Dynamique est un mélange d’outils classiques provenant de l’Analyse d’Algorithmes (par exemple les séries génératrices) et d’outils moins classiques en informatique (que sont les systèmes dynamiques). L’intérêt de l’Analyse dynamique est qu’elle permet d’analyser toute une famille de paramètres de toute une famille d’algorithmes. Les algorithmes ont de commun qu’ils utilisent à chaque étape une division particulière. Dans cet exposé, nous étudierons l’algorithme de Knuth et Schönhage dont la structure est complètement différente des précédents algorithmes. C’est un algorithme de type “Diviser pour Régner” pour lequel aucun résultat théorique n’était connu. Pour obtenir sa complexité en bits moyenne, il a donc fallu faire évoluer la méthodologie. Dans un premier temps, je m’attacherai à présenter l’algorithme. Ensuite, j’introduirai les points importants pour effectuer son analyse. Après, je parlerai des résultats intermédiaires et de la méthodologie pour les obtenir. Enfin je conclurai.

C’est un travail en commun avec Eda Cesaratto, Julien Clément, Benoît Daireaux, Véronique Maume-Deschamps et Brigitte Vallée.