Fractions continues, algorithmes de comparaison et constantes de structure fine

Partons de problèmes très simples de comparaison de fractions issus du célèbre mémoire HAKMEM (algorithmes de fractions continues) et de la géométrie algorithmique (calcul robuste de l'orientation de triangles). L'analyse de complexité conduit naturellement à des incursions (légères) dans une variété surprenante de domaines. On croisera ainsi les systèmes dynamiques (dynamique symbolique), la théorie élémentaire des nombres (fractions continues), les fonctions spéciales (valeurs zeta multiples), l'analyse fonctionnelle (opérateurs de transfert), l'analyse numérique basique (accéleration de convergence), et enfin l'analyse complexe (hypothèse de Riemann). Tous ces domaines contribuent {\em in fine\/} à une caractérisation précise de la complexité des algorithmes étudiés, tant en moyenne qu'en distribution. (Travail en cours avec Brigitte Vallée, Caen)