Retour à l'index du GREYC

Séminaire Algorithmique

Site du CNRS

Séminaire Algorithmique

Le séminaire a lieu le mardi à 11 h 45 (sauf modification exceptionnelle), au campus Côte de Nacre, bâtiment Sciences 3, salle S3 351, 3ème étage.

Résumé du séminaire du Mardi 25 Mai 2010

Tries et sources sans mémoire: de l'arithmétique à l'analyse

par 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 (pi), 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 pl ⁄ log pk. 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.)

GREYC
Campus Côte de Nacre, boulevard du Maréchal Juin
BP 5186
14032 Caen Cedex
FAX : +33 (0)2 31 56 73 30
http://www.greyc.fr