Mathieu Roux (GREYC et LMNO, Caen)

Une source est un mécanisme aléatoire qui produit des mots. On lui associe une série génératrice Λ( s ), fonction des propriétés probabilistes de la source. Celle-ci joue, via la transformée de Mellin, un rôle fondamental dans l’analyse des structures de données construites sur les mots de la source (en particulier trie et ABR), et donc les propriétés des algorithmes (de tri par exemple), agissant sur ces structures. La série Λ( s ) converge pour ℜ( s ) > 1 et a un pôle simple en s = 1, mais l’analyse en moyenne des structures de données est fondée sur la géométrie fine des pôles et les propriétés analytiques de Λ dans le demi-plan gauche ℜ( s ) ≤ 1.

Le comportement de la série Λ( s ) est souvent d’étude délicate, même dans le cas de sources simples. Ainsi, dans le cas des sources sans mémoire, la série Λ( s ) converge pour ℜ( s ) >1 et a un pôle simple en s = 1, mais l’analyse en moyenne des structures de données est fondée sur la géométrie fine des pôles de Λ dans le demi-plan gauche ℜ( s ) ≤ 1.

On traitera ici le cas d’un alphabet fini Σ = {1,…, r }, associé à la famille de probabilités ( p i ), pour lequel on mettra en évidence une géométrie étroitement liée aux propriétés arithmétiques de la famille α k , l = log p l ⁄ log p k. Je décrirai précisément cette région sans pôles, et montrerai comment sa forme dépend des propriétes d’approximation de la famille α. J’expliquerai aussi comment ces résultats permettent d’obtenir une asymptotique fine pour le comportement moyen des tries.

(Travail commun avec Philippe Flajolet et Brigitte Vallée.)