|
GREYC
|
|
GREYC
|
Une large partie de ma thèse est consacrée à l'analyse probabiliste asymptotique d'algorithmes au sein des réseaux. Dans ce domaine, les objets combinatoires manipulés restent trop complexes pour pouvoir appliquer directement des techniques, maintenant classiques (comportement d'une série génératrice au voisinage de son pôle "dominant"). Pour autant, l'analyse en moyenne des processus de réduction (dans des modèles divers) me paraît extrêmement intéressante aussi bien par les méthodes qui y seraient développées, réutilisables pour l'analyse des algorithmes arithmétiques en général, que par l'enjeu de ce type de résultats sur les applications pratiques (par exemple en cryptographie). En effet, les algorithmes de réduction se comportent en pratique considérablement mieux que ce que laissent espérer les bornes connues dans le pire des cas (pour le nombre d'itérations, comme pour la qualité de la base de sortie). On pourrait d'une part compléter mes résultats dans le modèle {\em uniforme} et d'autre part, chercher les résultats analogues dans d'autres modèles. En la matière, des échanges réguliers ont lieu avec PHILIPPE FLAJOLET, RICHARD BRENT, BRIGITTE VALLÉE et ANANTOLY ZHIGLJAVSKY, notamment grâce à un projet de collaboration entre les universités d'Oxford, de Cardiff, de Caen et le projet Algo de l'INRIA.
Actuellement, je travaille en collaboration avec BRIGITTE VALLÉE, sur une nouvelle méthode (provenant de l'étude des systèmes dynamiques) pour l'étude en moyenne ou en distribution des algorithmes de réduction. Connu sous le nom d'analyse dynamique , cette approche originale nous a déjà permis d'exhiber la complexité en moyenne réaliste (en nombre d'opérations élémentaires sur les bits) de l'algorithme d'Euclide et ses multiples variantes.
L'analyse dynamique permettrait d'évaluer plus précisément la complexité en moyenne des algorithmes de réduction et peut-être dans le cadre de modèles aléatoires plus proches des applications.
