Journée-séminaire de combinatoire

(équipe CALIN du LIPN, université Paris-Nord, Villetaneuse)

Le 03 janvier 2012 à 13h30 en B311, Brigitte Chauvin nous parlera de : Chaînes de Markov à mémoire variable et tries des suffixes

Résumé : Dans un premier temps, on expliquera comment on produit des mots, au sens d'une source dynamique probabiliste, avec une source ``VLMC'' (Variable Length Markov Chain). Puis, pour une famille de sources VLMC associées à un ``peigne infini'', on construira le trie des suffixes correspondant. On trouvera l'asymptotique de sa hauteur et de son niveau de saturation, qui ne sont pas toujours logarithmiques. On fera le lien entre ce comportement asymptotique et les propriétés de mélange de la source.

 [Slides.pdf]


Dernière modification : mercredi 28 décembre 2011 Valid HTML 4.01! Valid CSS! Contact : Cyril.Banderier at lipn.univ-paris13.fr