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 4 Novembre 2003

L'algorithme d'Euclide, hier et aujourd'hui : Un exemple d'analyse d'algorithmes

par Brigitte Vallée (GREYC, CNRS)

L'algorithme d'Euclide, qui calcule le pgcd de deux entiers, est un des algorithmes de base en arithmétique. C'est l'un des plus anciens algorithmes de notre histoire et sa structure est très simple. Comme c'est le cas pour tous les algorithmes, on cherche à analyser précisément son comportement et à répondre à des questions naturelles sur sa complexité "en moyenne": combien y-a-t-il d'itérations ? combien y-a-t-il de bits manipulés au total lors d'une exécution de l'algorithme? On se trouve alors confronté à de réelles difficultés, liées au fait que le déroulement de l'algorithme dépend de toute l'histoire précédente. C'est pourquoi l'analyse précise de son comportement n'a été établie que tout récemment, et fait appel à des méthodes mathématiques très variées, et pas toujours élémentaires....

J'exposerai en particulier un résultat très récent, obtenu en collaboration avec Viviane Baladi (Maths, Paris VII) qui montre que le nombre d'itérations et beaucoup de coûts naturels associés à l'algorithme suivent une loi qui est asymptotiquement gaussienne.

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