Retour à l'index du GREYC

Séminaire Algorithmique

Site du CNRS

Séminaire Algorithmique

Le séminaire a lieu le mardi à 11 h 45 (sauf modification exceptionnelle), au campus Côte de Nacre, bâtiment Sciences 3, salle S3 351, 3ème étage.

Résumé du séminaire du Mardi 27 Mai 2008

Première analyse des algorithmes rapides du pgcd

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

GREYC
Campus Côte de Nacre, boulevard du Maréchal Juin
BP 5186
14032 Caen Cedex
FAX : +33 (0)2 31 56 73 30
http://www.greyc.fr