Sujet de TIPE

Maxime Guéry

Description

Niveau: Supérieur
Sujet de TIPE : Billard re tangulaire, fra tions ontinues et mots sturmiens Maxime Guéry Sous la dire tion de Damien Calaque 1

• eets


• appli ation de l'algèbre


• fra tion


• mathématique


• billard


• géométrie analytique


• fra tions

Sujets

• Hannover
• West Germany
• Coriolis
• Genève
• Mathématiques
• Billard
• Géométrie analytique

Informations

• Publié par: zauj
• Nombre de lectures: 53
• Langue: Français

Extrait

Resume
Dans ce memoire, on s’attachera a etudier a l’aide de methodes d’ana-
lyse combinatoire les parametres fondamentaux des tries su xes construits
sur des mots produits par une source dynamique. Apres avoir rappele les
principales de nitions et montre des resultats sur les tries classiques, on
etablira que ces parametres di erent peu entre un trie classique et un trie
su xe. Il en resulte une caracterisation precise de certains parametres des
tries su xes lies aux algorithmes classiques de compression.
1Parametres des arbres su xes dans le cas de
sources simples
Julien Fayolle
18 decembre 2003
14:46
1 Introduction
La structure d’arbre digital ou de trie est une structure de donnee qui permet
de gerer e cacemen t la recherche d’un mot dans un ensemble de mots (en
moyenne en temps log n si on a n mots dans l’ensemble). Pour ce faire, on classe
les mots de l’ensemble de depart dans les feuilles d’un arbre suivant leurs lettres
successives et on recherche un mot dans cette structure en le regardant lettre
par lettre, comme on le ferait pour rechercher la de nition d’un mot dans un
dictionnaire.
C’est sur un type de structure de donnee lie au trie, le trie su xe , que
l’on base certains algorithmes essentiels pour l’informatique : les algorithmes
de compression de donnees. Cette structure de trie su xe ou arbre des su xes
sera essentielle dans ce memoire. Une comprehension des mecanismes mis en
jeu permet de mieux evaluer les performances de la structure des tries su xes
et la complexite des algorithmes qui utilisent cette de donnee. La
principale di cult e de l’analyse des tries su xes tient en la correlation d’un
motif : la presence averee d’un motif a un instant va renseigner sur l’apparition
ulterieure de ce m^eme motif.
Dans ce memoire, on commencera par de nir les notions qui jalonneront
l’etude menee, ainsi que les parametres pertinents pour l’etude d’un arbre. Apres
avoir pris conscience du lien profond entre trie et trie su xe, et mis en avant le
fonctionnement de l’algorithme de compression le plus classique, on introduira
un modele simpli e de sources dynamiques. Le squelette de ce rapport a vocation
a s’adapter a des modeles plus compliques de sources (sources markoviennes,
modeles a densite, ...).
Ce memoire se fonde sur l’intuition d’une forte ressemblance asymptotique
entre les parametres des tries classiques et ceux des tries su xes. On va dans
un premier temps rappeler les resultats sur certains parametres des tries; on
introduira, a cet e et, l’outil puissant qu’est la transformee de Mellin pour
determiner le comportement asymptotique de ces parametres. Le corps de ce
memoire consiste a extraire le comportement asymptotique des parametres que
20 1
0 1 0 1
00.. 10..
01 10
110.. 111..010..
10
0110.. 0111..
Fig. 1 { Exemple de trie sur 2 lettres
l’on etudie dans le cas d’un trie su xe a l’aide d’outils issus de l’analyse com-
plexe; puis a evaluer la di erence de ces parametres pour un arbre digital et
pour un trie su xe. L’etude complete n’est menee que pour le parametre de
la longueur de cheminement, mais les methodes pour obtenir des resultats sur
d’autres parametres sont identiques et une extension est en vue.
Les methodes utilisees dans ce memoire font intervenir des series generatrices,
des outils d’analyse complexe et des sources dynamiques de base; mais en
prevision de resultats ulterieurs, une annexe sur des sources dynamiques plus
generales est incluse.
1.1 Notions de base sur les tries
1De nition 1 Les tries ou arbres digitaux sont de nis sur un ensemble de
mots in nis X de l’alphabet M =fa ; a ; :::; a g par :1 2 n
8
>; si jXj = 0;<
trie(X) = si jXj = 1;
>:
h ; trie(Xna ); :::; trie(Xna )i sinon:1 n
Xn est de ni comme le sous-ensemble des mots de X commen cant par la lettre
auxquels on a retire la lettre .
Les mots X sont stockes dans les feuilles (n uds sans ls) du trie.
1Ce mot est un melange entre tree (arbre) et retrieve (recuperer) car le trie est une structure
de donnee e cace pour la gestion d’un dictionnaire, et en particulier pour retrouver un mot.
3