7.4 Exercices
333
L’étude de séries bivariées par Jacquet et Régnier [141, 142] permet d’analyser
certains paramètres de trie comme la profondeur « moyenne » d’une feuille (correspondant à la longueur de cheminement externe divisée par le nombre de feuilles)
en distribution grâce par exemple au théorème classique des quasi-puissances
de Hwang [136, 137]. Mentionnons qu’il est possible d’utiliser des techniques
analytiques pour obtenir des résultats en distribution et étudier des paramètres plus
fins comme le profil des tries (voir les travaux de Park et al. [204]). Les tries et autres
variantes d’arbres digitaux ont été abondamment étudiés par quantité d’auteurs et
de méthodes. Nous pouvons citer les études pour étendre les analyses au cas d’une
source markovienne avec Jacquet et Szpankowski [143–145, 150], ou encore celles
utilisant plutôt une approche probabiliste avec Pittel [208], Devroye [55, 56, 59],
Louchard [166].
Cette bibliographie est loin d’être exhaustive, le lecteur se peut se référer à
l’article de synthèse de Flajolet [83] pour d’autres pistes.
Remarque 7.48 Si l’apparition de fluctuations est intrigante du point de vue de
l’analyse, il est relativement difficile de les observer en pratique dans les simulations. En effet, pour une source sans mémoire nous avons vu que ces fluctuations
apparaissent dans des cas très particuliers prenant en compte la nature arithmétique
des rapports des log p α (pour α symbole de l’alphabet).
Remarque 7.49 La méthode de Rice expliquée ici est sans doute la méthode la
plus simple pour accéder à l’asymptotique fine de l’espérance des paramètres de
tries. Nous avons présenté néanmoins le chemin alternatif faisant usage d’une
autre transformation intégrale : la transformée de Mellin (voir la monographie de
Flajolet et al. à ce sujet [100]). Cette transformée est un outil plus général bien
connu par exemple en théorie des nombres, et qui s’applique ici assez facilement
sur l’espérance dans le modèle de Poisson. Nous devons alors recourir à la
dépoissonisation analytique pour conclure dans le modèle usuel de Bernoulli [46]
(voir également l’article de Flajolet et Sedgewick [93]).
7.4 Exercices
7.1. Longueur de cheminement externe (modèle fini équiprobable) Calculer le polynôme
explicite et la valeur moyenne pour la longueur de cheminement externe dans le modèle fini des
clés avec d = 3.
7.2. Hauteur (modèle fini) Tracer un histogramme pour n = 10 et d = 8 donnant la probabilité
qu’un trie à n clés soit de hauteur h < k en utilisant l’expression explicite (7.10) donnant P
(d)
n (h ≤
k).
7.3. Coût de construction d’un trie Il s’agit d’étudier le nombre de comparaisons de symboles
pour construire un trie. Définir ce coût et l’exprimer en fonction de la longueur de cheminement
externe lce et de la taille (nombre de nœuds internes) d’un trie.
7.4. Taille du trie dans le modèle infini i.i.d. uniforme Appliquer la méthode avec transformée
de Mellin à l’étude asymptotique de la moyenne de la taille d’un trie (nombre de nœuds internes)
dans le modèle infini i.i.d. uniforme avec un alphabet binaire.
333
L’étude de séries bivariées par Jacquet et Régnier [141, 142] permet d’analyser
certains paramètres de trie comme la profondeur « moyenne » d’une feuille (correspondant à la longueur de cheminement externe divisée par le nombre de feuilles)
en distribution grâce par exemple au théorème classique des quasi-puissances
de Hwang [136, 137]. Mentionnons qu’il est possible d’utiliser des techniques
analytiques pour obtenir des résultats en distribution et étudier des paramètres plus
fins comme le profil des tries (voir les travaux de Park et al. [204]). Les tries et autres
variantes d’arbres digitaux ont été abondamment étudiés par quantité d’auteurs et
de méthodes. Nous pouvons citer les études pour étendre les analyses au cas d’une
source markovienne avec Jacquet et Szpankowski [143–145, 150], ou encore celles
utilisant plutôt une approche probabiliste avec Pittel [208], Devroye [55, 56, 59],
Louchard [166].
Cette bibliographie est loin d’être exhaustive, le lecteur se peut se référer à
l’article de synthèse de Flajolet [83] pour d’autres pistes.
Remarque 7.48 Si l’apparition de fluctuations est intrigante du point de vue de
l’analyse, il est relativement difficile de les observer en pratique dans les simulations. En effet, pour une source sans mémoire nous avons vu que ces fluctuations
apparaissent dans des cas très particuliers prenant en compte la nature arithmétique
des rapports des log p α (pour α symbole de l’alphabet).
Remarque 7.49 La méthode de Rice expliquée ici est sans doute la méthode la
plus simple pour accéder à l’asymptotique fine de l’espérance des paramètres de
tries. Nous avons présenté néanmoins le chemin alternatif faisant usage d’une
autre transformation intégrale : la transformée de Mellin (voir la monographie de
Flajolet et al. à ce sujet [100]). Cette transformée est un outil plus général bien
connu par exemple en théorie des nombres, et qui s’applique ici assez facilement
sur l’espérance dans le modèle de Poisson. Nous devons alors recourir à la
dépoissonisation analytique pour conclure dans le modèle usuel de Bernoulli [46]
(voir également l’article de Flajolet et Sedgewick [93]).
7.4 Exercices
7.1. Longueur de cheminement externe (modèle fini équiprobable) Calculer le polynôme
explicite et la valeur moyenne pour la longueur de cheminement externe dans le modèle fini des
clés avec d = 3.
7.2. Hauteur (modèle fini) Tracer un histogramme pour n = 10 et d = 8 donnant la probabilité
qu’un trie à n clés soit de hauteur h < k en utilisant l’expression explicite (7.10) donnant P
(d)
n (h ≤
k).
7.3. Coût de construction d’un trie Il s’agit d’étudier le nombre de comparaisons de symboles
pour construire un trie. Définir ce coût et l’exprimer en fonction de la longueur de cheminement
externe lce et de la taille (nombre de nœuds internes) d’un trie.
7.4. Taille du trie dans le modèle infini i.i.d. uniforme Appliquer la méthode avec transformée
de Mellin à l’étude asymptotique de la moyenne de la taille d’un trie (nombre de nœuds internes)
dans le modèle infini i.i.d. uniforme avec un alphabet binaire.