FAYOLLE Julien

毕业博士
科研组 : SPIRAL
离开日期 : 2006-3-3
https://lip6.fr/Julien.Fayolle

责任导师 : Michèle SORIA

Compression de données sans perte et combinatoire analytique

Résumé : Cette thèse est centrée autour de l’étude de deux algorithmes de compression de données sans perte. L’algorithme de Lempel et Ziv (LZ’77) est basé sur une structure de données sur les textes appelée arbre des suffixes. Nous analysons certains paramètres des arbres des suffixes en montrant, `a l’aide des méthodes de la combinatoire analytique (séries génératrices, combinatoire, analyse complexe et probabilités), qu’ils sont asymptotiquement assez proches de ceux des tries. Or nous connaissons bien ceux des tries ; nous déterminons donc le comportement asymptotique de la moyenne de la taille, de la longueur de cheminement et de la profondeur typique des arbres des suffixes pour des textes engendrés sous des modèles sans mémoire et markovien. Nous obtenons aussi un résultat sur la variance de la taille et de la longueur de cheminement des tries. Enfin, nous analysons un algorithme récent de compression de données sans perte qui utilise les anti-dictionnaires. Mots-clés : Combinatoire analytique, compression de données, théorie de l’information, analyse d’algorithmes, tries, arbres des suffixes.

答辩 : 2006-3-2

评委会 :

HOFRI Micha, rapporteur
MARCKERT Jean-François, rapporteur
SZPANKOWSKI Wojciech, rapporteur
CARBONE Alessandra, examinateur
FLAJOLET Philippe, directeur de thèse
SORIA Michèle, directrice de thèse
VALLÉE Brigitte, invitée.

离开日期 : 2006-3-3

2006 刊物

Mentions légales
网站导航