Dans cette thèse, nous nous intéressons au comportement asymptotique des distributions de coûts associés à des algorithmes d'Euclide de la classe rapide. Nous commençons dans un 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 applications de la bonne classe. Ces résultats sont utilisés dans le troisième chapitre pour obtenir des estimations sur la fonction génératrice des moments où nous montrons sa quasi-décroissance exponentielle. <br /><br />Le dernier chapitre est consacré aux démonstrations de téorèmes de la limite locale. Le premier théorème est sans vitesse de convergence et concerne tous les coùts non-réseau ayant des moments forts à l'ordre trois. La condition diphantienne nous permet ensuite d'établir un théorème de la limite locale avec contrôle de la vitesse de convergence. Pour des observables suffisament régulières, nous obtenons une vitesse de convergence optimale.

l'objet de cette thèse est la mise en évidence de procédés <em>systématiques</em> pour déterminer <em>automatiquement</em> le coût moyen d'un algorithme. Ces procédés s'appliquent en général aux schémas de <em>descente</em> dans des structures de données <em>décomposables</em>, ce qui permet de modéliser une vaste classe de problèmes. Cette thèse s'intéresse plus précisément à la première phase de l'analyse d'un algorithme, l'<em>analyse algébrique</em>, qui traduit le programme en objets mathématiques, tandis que la seconde phase extrait de ces objets les informations désirées sur le coût moyen. Nous définissons un langage de spécification pour définir des structures de données décomposables et des procédures de descente sur celles-ci. Lorsque l'on utilise comme objets mathématiques des séries génératrices (de dénombrement pour les données, de coût pour les procédures), nous montrons que les algorithmes décrits dans ce langage se traduisent <em>directement</em> en systèmes d'équations pour les séries génératrices associées, et de surcroît par des règles <em>simples</em>. À partir de ces équations, nous pouvons ensuite déterminer en temps polynomial le coût moyen exact pour une valeur fixée de la taille des données. On pourra aussi utiliser ces équations pour calculer par <em>analyse asymptotique</em>le coût moyen lorsque la taille des données tend vers l'infini, puisque l'on sait par ailleurs que le coût moyen asymptotique est directement lié au comportement des séries génératrices au voisinage de leurs singularités. Ainsi nous montrons qu'à une classe donnée d'algorithmes correspond une classe bien définie de séries génératrices, et par conséquent une certaine classe de formules pour le coût moyen asymptotique. Ces règles d'analyse algébrique ont été incorporées dans un système d'analyse automatique d'algorithmes, Lambda-Upsilon-Omega, qui s'est avéré être un outil très utile pour l'expérimentation et la recherche.

Pour une base fixée, les entiers ellipséphiques (c'est-à-dire les entiers dont l'écriture n'utilise que certains chiffres) et les palindromes forment des sous ensembles éparses des entiers, ensembles définis par des conditions digitales. Nous étudions si ces ensembles ont des propriétés multiplicatives similaires à celles des entiers.<br>Nous évaluons d'abord les grands moments de la série génératrice des entiers ellipséphiques. Comme application, nous en déduisons l'existence d'un 0 < c < 1 tel que pour tout entier k, une infinité d'entiers ellipséphiques n possédant un diviseur p^k de l'ordre de n^c, p désignant un nombre premier. De plus, le nombre de tels entiers est de l'ordre de grandeur attendu.<br>Nous établissons ensuite un résultat de crible où les modules possédant un nombre anormalement grand de diviseurs sont écartés du terme d'erreur. Nous en déduisons l'existence d'une proportion positive d'entiers ellipséphiques friables c'est-à-dire possédant tous leurs facteurs premiers majorés par n^c, pour une constante c < 1 fixée.<br>Nous montrons enfin à l'aide de techniques élémentaires comment réduire l'étude de la série génératrice des palindromes à une série proche de celle des entiers ellipséphiques ce qui permet d'étudier la répartition des palindromes dans les progressions arithmétiques et ainsi d'obtenir une majoration de l'ordre de grandeur attendu du nombre de palindromes premiers. Nous en déduisons en particulier l'existence d'une infinité de palindromes possédant en base 10 au plus 372 facteurs premiers (comptés avec multiplicité).

L'étude de certaines variables aléatoires, comme les paramètres additifs sur les arbres hyperquaternaires de points, ou encore le nombre de maxima au sein d'un ensemble de n points indépendants, et uniformément distribués dans [0,1]^d font apparaître des suites particulières, les sommes harmoniques multiples (SHM), extensions des nombres harmoniques classiques à des multi-indices.<br /><br />Nos travaux visant à appliquer des méthodes symboliques pour l'étude de ces variables aléatoires, nous remplaçons l'utilisation de multi-indices par des codages sur des alphabets distincts, et nous appuyons alors sur des résultats importants en combinatoire des mots pour les appliquer à nos suites de SHM, et aux fonctions polylogarithmes, qui sont des variantes des génératrices ordinaires des SHM. Dans les cas convergents, les deux objets convergent (respectivement lorsque z tend vers 1 et lorsque N tend vers l'infini) vers la même limite, appelée polyzêta. Pour les cas divergents, l'utilisation de séries génératrices non commutatives nous permet d'établir un théorème ``à l'Abel'', faisant apparaître une limite commune. Ce théorème permet de donner une forme explicite aux constantes d'Euler généralisées associées à des SHM divergentes et ainsi d'obtenir un algorithme très efficace pour calculer leur développement asymptotique.<br /><br />Finalement, nous proposons des applications des sommes harmoniques dans le domaine des structures de données multidimensionnelles, pour lesquelles notre approche donne naissance à des calculs exacts, qui peuvent par la suite être aisément évalués asymptotiquement.