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 8 Janvier 2013

Analyse des arbres digitaux de recherche pour une source générale

par Brigitte Vallée (GREYC, Caen)

Les arbres digitaux de recherche (dst) jouent un rôle essentiel dans les algorithmes de compression, du type Lempel-Ziv. Cette structure de données peut-être vue comme un hybride entre un arbre (binaire) de recherche (bst) et un arbre digital de type trie. L'analyse probabiliste de ses principaux paramètres (par exemple sa profondeur) s'avère donc complexe, même dans le cas où les mots sont produits par une source simple (sans mémoire ou chaine de Markov). Après les travaux fondateurs de Flajolet et Sedgewick vers 1985 (source sans mémoire), l'étude a été étendue par Jacquet, Louchard, Szpankowski et Tang à une chaine de Markov). Nous effectuons une telle analyse pour une source générale, en cherchant à étendre d'une part ces travaux fondateurs, et en les intégrant dans le point de vue général qu'a développé l'équipe dans l'étude des tries et des algorithmes de tri et de recherche.

Après avoir rappelé et comparé les trois structures de recherche (dst, bst, trie), et les principaux résultats connus sur leur analyse, j'expliquerai les principaux principes qui conduisent notre analyse.

C'est un travail commun avec Kanal Hun, et débuté avec Philippe Flajolet.

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