Analyse dynamique d'algorithmes euclidiens et théorèmes limites
Institution:
Paris 7Disciplines:
Directors:
Abstract EN:
In this thesis, we study the asymptotic behaviour of the distribution of the total cost associated to the execution of fast euclidian algorithms. In the first chapter, we recall some dynamical properties of euclidian Systems and introduce the property of strong moments for an additif non-lattice cost function. We establish then, the strong diophantine cost condition and we prove it genericity. In the second chapter, using Dolgopyat-Me. Bourne techniques, we analyse perturbations of transfer operators associated to transformations of the good class. These results are used in the third chapter where we get estimations for the Levy generating function and we obtain that is quasi- exponentially decreasing. The last chapter is devoted to proving local imit theorems. The first theorem is without speed of convergence and relates ail costs having strong moments up to order three The diophantine condition able us to establish a local limit theorem with control of the speed o convergence. For smooth enough observales we attain the optimal speed.
Abstract FR:
Dans cette thèse, nous nous intéressons au comportement asymptotique des distributions de coûts totaux associés à des algorithmes d'Euclide de la classe rapide. Nous commençons le premier chapitre par des rappels sur les propriétés dynamiques des systèmes euclidiens et introduisons la propriété de moments forts pour les coûts additifs non-réseau. Nous établissons ensuite la condition de coût fortement diophantien et montrons sa généricité. Dans le deuxième chapitre, nous analysons, en adaptant des techniques de Dolgopyat-Melbourne des perturbations d'opérateurs de transfert associés à des systèmes de la bonne classe. Ces résultats sont utilisés dans le chapitre trois pour obtenir des estimations sur la série génératrice de Lévy où nous montrons sa quasi-décroissance exponentielle. Le dernier chapitre est consacré aux démonstrations des théorèmes de la limite locale. Le premier théorème est sans vitesse de convergence et concerne tous les coûts ayant des moments forts à l'ordre 3. La condition diophantienne nous permet ensuite d'établir un théorème local limite avec un contrôle de la vitesse de convergence. Pour des observables suffisamment régulières, nous obtenons une vitesse de convergence optimale