Brigitte Vallée (GREYC)

C’est une idée tout à fait naturelle de considérer un algorithme et l’ensemble de ses données comme un système dynamique. Le temps (discret) se confond alors avec le nombre d’itérations de l’algorithme. Les principaux outils classiques des systèmes dynamiques, tel l’opérateur de Ruelle, permettent alors de décrire l’évolution du système au cours du temps.

L’analyse d’un algorithme cherche à décrire le comportement “moyen” d’un algorithme. Les méthodes classiques d’analyse en moyenne sont maintenant bien établies, et beaucoup reposent sur l’outil essentiel que sont les séries génératrices.

Pourtant, dans le cas de certains algorithmes, ces méthodes ne peuvent s’appliquer, car la distribution des données évolue de manière trop complexe au cours de l’algorithme pour pouvoir être traduite dans le formalisme des séries génératrices. C’est ce qui se passe pour des algorithmes à mémoire non bornée, où le cours de l’algorithme dépend de toute l’histoire précédente. Mais alors, l’opérateur de Ruelle lié au système dynamique prend le relais des séries génératrices; après une généralisation naturelle et adéquate, il peut être d’ailleurs considéré comme un opérateur générateur au-dessus des séries génératrices.

Après avoir rappelé le cadre de l’analyse en moyenne d’algorithmes et celui des systèmes dynamiques, je donnerai quelques exemples de résultats très récents qui peuvent être obtenus grâce à ce nouveau formalisme, dans deux domaines algorithmiques particuliers: les algorithmes arithmétiques et les algorithmes de la théorie de l’information.

En particulier, en arithmétique, je décrirai des nouveaux résultats concernant l’analyse d’une classe d’algorithmes de type Euclide, qui contient le pgcd binaire et des algorithmes qui calculent le symbole de Jacobi [Vallée 98, 99, Bourdon et Vallée 99]. Dans le contexte de la théorie de l’information, je ferai l’analyse d’une structure d’arbre digital très général (le trie) qui sert à implémenter les dictionnaires et qui est fortement utilisée dans les algorithmes de compression [Clément, Flajolet, Vallée 99].