7.1 Analyses exactes
287
La valeur moyenne E
(d)
n [v] du paramètre v pour un trie à n clés s’exprime dans ce
modèle par
E
(d)
n [v] =
1
2 d
n
[z
n
]v
(d) (z) =
v
(d)
n
2 d
n
.
Afin de calculer les séries génératrices et valeurs moyennes associées à des
paramètres v de tries, nous allons utiliser la description récursive de ces paramètres.
Par exemple pour un paramètre additif (voir la section 1.3.2) le paramètre se décrit à
l’aide d’une fonction de péage appliquée à la racine, et en poursuivant récursivement
sur les sous-arbres s’ils existent. Il va ainsi être possible de calculer des fonctions
génératrices associées à diverses fonctions de péage.
Illustration Nous calculons quelques séries génératrices pour des paramètres
particuliers importants. Ces paramètres seront eux-mêmes utilisés par la suite pour
décrire et décomposer les paramètres de trie. Le résultat de ces calculs est rassemblé
dans la deuxième colonne de la table 7.1 (la troisième colonne sera explicitée en
section 7.1.2).
Le premier paramètre dans cette table est identiquement constant et égal à 1 pour
tout ensemble de mots ω (y compris l’ensemble vide). Ce paramètre est analogue
au péage utilisé pour l’expression de la taille d’un trie (v(ω) = 1, mais sans la
contrainte supplémentaire |ω| ≥ 2). Dans la formule (7.7), le nombre de sousensembles de taille n d’un ensemble à 2 d clés est
2 d
n
. Nous écrivons donc pour
le premier coût de la table 7.1
v
(d)
n =
ω⊂{0,1} d
|ω|=n
1 =
2 d
n
.
Par suite, la série génératrice s’écrit
v
(d) (z) =
2 d
n=0
2 d
n
z
n
= (1 + z)
2 d
.
D’autres séries génératrices, utilisées dans la suite, se calculent de manière
analogue et sont rassemblées dans la deuxième colonne de la table 7.1 .
Séries génératrices pour les tries Comme exemple d’utilisation du concept des
péages pour calculer les séries génératrices, considérons le péage γ associé à la
taille d’un trie. Celui-ci s’exprime à partir des paramètres de la table 7.1 :
γ (ω) = 1 − 1 {|ω|=0} − 1 {|ω|=1} .
287
La valeur moyenne E
(d)
n [v] du paramètre v pour un trie à n clés s’exprime dans ce
modèle par
E
(d)
n [v] =
1
2 d
n
[z
n
]v
(d) (z) =
v
(d)
n
2 d
n
.
Afin de calculer les séries génératrices et valeurs moyennes associées à des
paramètres v de tries, nous allons utiliser la description récursive de ces paramètres.
Par exemple pour un paramètre additif (voir la section 1.3.2) le paramètre se décrit à
l’aide d’une fonction de péage appliquée à la racine, et en poursuivant récursivement
sur les sous-arbres s’ils existent. Il va ainsi être possible de calculer des fonctions
génératrices associées à diverses fonctions de péage.
Illustration Nous calculons quelques séries génératrices pour des paramètres
particuliers importants. Ces paramètres seront eux-mêmes utilisés par la suite pour
décrire et décomposer les paramètres de trie. Le résultat de ces calculs est rassemblé
dans la deuxième colonne de la table 7.1 (la troisième colonne sera explicitée en
section 7.1.2).
Le premier paramètre dans cette table est identiquement constant et égal à 1 pour
tout ensemble de mots ω (y compris l’ensemble vide). Ce paramètre est analogue
au péage utilisé pour l’expression de la taille d’un trie (v(ω) = 1, mais sans la
contrainte supplémentaire |ω| ≥ 2). Dans la formule (7.7), le nombre de sousensembles de taille n d’un ensemble à 2 d clés est
2 d
n
. Nous écrivons donc pour
le premier coût de la table 7.1
v
(d)
n =
ω⊂{0,1} d
|ω|=n
1 =
2 d
n
.
Par suite, la série génératrice s’écrit
v
(d) (z) =
2 d
n=0
2 d
n
z
n
= (1 + z)
2 d
.
D’autres séries génératrices, utilisées dans la suite, se calculent de manière
analogue et sont rassemblées dans la deuxième colonne de la table 7.1 .
Séries génératrices pour les tries Comme exemple d’utilisation du concept des
péages pour calculer les séries génératrices, considérons le péage γ associé à la
taille d’un trie. Celui-ci s’exprime à partir des paramètres de la table 7.1 :
γ (ω) = 1 − 1 {|ω|=0} − 1 {|ω|=1} .