Philippe Flajolet (INRIA Rocquencourt)

L'arbre digital de l'informatique transparents

A tout ensemble fini de mots sur un alphabet fixé, on peut associer un arbre fini, dit ''arbre digital'' ou ''trie'', obtenu en identifiant chaque mot avec une branche et en ne retenant que les préfixes qui permettent de discriminer les mots de manière minimale. L'arbre digital apparaît en informatique comme structure de données dans la gestion de dictionnaires, dans la conception de protocoles de communication, et l'une de ses variantes joue un rôle essentiel dans les algorithmes de compression sans perte parmi les plus utilisés. On présentera ici les principales méthodes introduites en combinatoire analytique et analyse d'algorithmes pour quantifier les caractéristiques probabilistes de l'arbre aléatoire induit par divers modèles de génération de mots. Ces méthodes incluent la transformation de Mellin, l'analyse de singulariés, la méthode du col et la ''dépoissonisation analytique'', ainsi que, dans certains cas, la théorie des opérateurs de transfert.