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 13 Novembre 2007

Analyse d'Algorithmes et Systèmes Dynamiques: l'exemple des algorithmes d'Euclide

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

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