|
GREYC
|
|
GREYC
|
Il s'agit de considérer l'agorithme à analyser comme un système dynamique. On caractérise alors l'ensemble des transformations intervenant lors d'une itération. Lorsque cette démarche est concluante, ce sont les propriétés analytiques de ces transformations élémentaires (plus exactement, les prolongements des transformations réciproques) qui déterminent la complexité en moyenne de l'algorithme. Ce raisonnement, introduit par Brigitte Vallée pour les algorithmes travaillant avec des entrées discrètes, utilise naturellement les outils classiques des systèmes dynamiques tels que les opérateurs de transferts.
L'algorithme d'Euclide est un algorithme qui calcule le pgcd de deux entiers par une suite de divisions euclidiennes. Il s'agit
d'un des plus anciens algorithmes travaillant sur les nombres entiers qui constitue par ailleurs "la brique de base" de
nombreuses applications en calcul formel ou en cryptographie.
Pour autant, l'analyse en moyenne et en distribution de cet algorithme n'a vu le jour que tres récemment (par exemple, une
conjecture demontrée en 1994 par Hensley). Tous les résultats connus jusqu' a présent concernent le nombre moyen
d'opérations arithmétiques effectuées.
En collaboration avec Brigitte Vallée, nous avons introduis un cadre général pour l'analyse en moyenne de l'algorithme d'Euclide (et de ses
variantes). Nous avons obtenu de nouveaux résulats concernant la complexité moyenne mesurée de manière rèaliste, i.e., faisant
intervenir le nombre d'opèrations èlèmentaires sur les bits.
Notre mèthode s'appuie sur l'ètude des transformations èlèmentaires de l'intervalle [0,1] utilisèes par un algorithme de type
Euclidien. Les propriètès analytiques de cet ensemble de transformations sont synthètisèes dans un opèrateur dont l'ètude
dètermine le comportement en moyenne de l'algorithme.
Ces résultats ont fait l'objet d'un article accepté au congrès ICALP'2000 (à parître en LNCS).
