Séminaire du 17 novembre 03, Loïck Lhote

Algorithmes polynomiaux pour le calcul numérique prouvé de constantes liées à l'Analyse Dynamique

Lorsqu'une constante n'admet pas de formule explicite, il est important de savoir l'approcher numériquement. Nous dirons qu'une constante est calculable en temps polynomial s'il existe un algorithme $A$ et un entier $r$ tels que $A$ calcule les $d$ premières décimales de la constante en $O(d^r)$ opérations arithmétiques.

Nous considérerons une classe de constantes qui ont un grand intérêt dans l'algorithmique des Systèmes Dynamiques. Ces constantes interviennent notemment dans l'analyse en moyenne des algorithmes euclidiens, dans l'analyse de structures de données comme les tries, en théorie de l'information, en cryptographie,... Leur unique point commun est d'être liée à la valeur propre dominante d'un outil classique en Analyse Dynamique : les opérateurs de transfert. Mais le calcul direct de la valeur propre dominante d'un opérateur de transfert est en général difficile. Pour l'approcher, nous présenterons une méthode générale, déjà utilisée par d'autres auteurs mais jusqu'à présent non-prouvée. Nous prouverons la convergence de cette méthode et expliciterons une borne supérieure sur sa complexité.

Finalement, nous appliquerons nos résultats à un sytème dynamique particulier, le système dynamique des fractions continues, pour obtenir des valeurs numériques prouvées de constantes importantes dans l'analyse de l'algorithme d'Euclide comme la constante de Hensley et la constante de Gauss-Kuz'min-Wirsing.