7.1 Analyses exactes
283
Fig. 7.1 Pour un alphabet binaire A = {0, 1}, le trie binaire correspondant à l’ensemble ω =
{0010101†, 010101†, 001101†, 1000101†, 1010011†} un ensemble de 5 mots. Le symbole † est
un symbole de terminaison (ici inutile car aucun mot n’est préfixe d’un autre). L’arbre trie(ω)
a pour taille (pour un trie c’est le nombre nœuds internes de l’arbre) S(ω) = 6, pour hauteur
h(ω) = 4, et pour longueur de cheminement externe (ω) = 16. Comme à la section 1.2.7, les
lettres sont dessinées « sur » les arêtes
Enfin pour un paramètre α d’arbre et un trie associé à un ensemble de mots ω
trie(ω), nous écrirons afin de simplifier les notations
α(ω) := α(trie(ω)),
en sous-entendant que le paramètre α est calculé sur le trie construit à partir de ω.
7.1 Analyses exactes
Comme souvent en combinatoire analytique, l’analyse s’effectue en deux étapes.
Dans un premier temps, il est possible de calculer des expressions exactes de
valeurs moyennes de paramètres. Cependant ces résultats sont parfois difficilement
interprétables et il est nécessaire dans un deuxième temps d’effectuer une analyse
asymptotique pour mieux évaluer les ordres de grandeur. Dans cette section, nous
commençons par présenter les principaux paramètres à analyser (taille, longueur
de cheminement et hauteur) avant de réaliser leur analyse exacte dans différents
modèles probabilistes pour les clefs.
Nous serons amenés au cours cette section à définir et manipuler différents types
de séries : séries ordinaires, séries exponentielles, séries dites poissonisées ou encore
séries de Dirichlet.
Paramètres des tries Le point de départ des analyses de tries réside dans la
définition récursive des paramètres étudiés. Pour un ensemble ω de clés, rappelons
que si |ω| = 1, le trie est réduit à une feuille et si |ω| = 0, l’arbre est
vide. Nous décrivons ici les principaux paramètres : taille, hauteur, longueur de
cheminement externe (illustrés sur l’exemple de la figure 7.1). Les définitions
283
Fig. 7.1 Pour un alphabet binaire A = {0, 1}, le trie binaire correspondant à l’ensemble ω =
{0010101†, 010101†, 001101†, 1000101†, 1010011†} un ensemble de 5 mots. Le symbole † est
un symbole de terminaison (ici inutile car aucun mot n’est préfixe d’un autre). L’arbre trie(ω)
a pour taille (pour un trie c’est le nombre nœuds internes de l’arbre) S(ω) = 6, pour hauteur
h(ω) = 4, et pour longueur de cheminement externe (ω) = 16. Comme à la section 1.2.7, les
lettres sont dessinées « sur » les arêtes
Enfin pour un paramètre α d’arbre et un trie associé à un ensemble de mots ω
trie(ω), nous écrirons afin de simplifier les notations
α(ω) := α(trie(ω)),
en sous-entendant que le paramètre α est calculé sur le trie construit à partir de ω.
7.1 Analyses exactes
Comme souvent en combinatoire analytique, l’analyse s’effectue en deux étapes.
Dans un premier temps, il est possible de calculer des expressions exactes de
valeurs moyennes de paramètres. Cependant ces résultats sont parfois difficilement
interprétables et il est nécessaire dans un deuxième temps d’effectuer une analyse
asymptotique pour mieux évaluer les ordres de grandeur. Dans cette section, nous
commençons par présenter les principaux paramètres à analyser (taille, longueur
de cheminement et hauteur) avant de réaliser leur analyse exacte dans différents
modèles probabilistes pour les clefs.
Nous serons amenés au cours cette section à définir et manipuler différents types
de séries : séries ordinaires, séries exponentielles, séries dites poissonisées ou encore
séries de Dirichlet.
Paramètres des tries Le point de départ des analyses de tries réside dans la
définition récursive des paramètres étudiés. Pour un ensemble ω de clés, rappelons
que si |ω| = 1, le trie est réduit à une feuille et si |ω| = 0, l’arbre est
vide. Nous décrivons ici les principaux paramètres : taille, hauteur, longueur de
cheminement externe (illustrés sur l’exemple de la figure 7.1). Les définitions