7.1 Analyses exactes
285
les relations suivantes :
χ k (ω) =
χ 0 (ω) = 1 {|ω|≤1}
si k = 0,
χ k−1 (ω \ 0) χ k−1 (ω \ 1) sinon.
(7.6)
Ce paramètre évalué en moyenne (avec un modèle probabiliste sur ω) donne
accès à la probabilité qu’un trie soit de hauteur inférieure ou égale à k. En effet,
la probabilité d’un événement est égale à l’espérance de son indicatrice. Dans un
modèle probabiliste donné, nous avons pour la hauteur h d’un trie
P(h ≤ k) = E[χ k ].
Les expressions précédentes pour les paramètres se prêtent de manière élégante
à une approche qui utilise les séries génératrices, dite par « algèbre de coûts »
(appellation provenant d’un article de Flajolet et al. [97] dont s’inspirent grandement
les sections suivantes).
7.1.1 Approche symbolique (modèle fini équiprobable)
Dans le modèle fini équiprobable (définition 2.16 dans la section 2.3.1), la longueur
des clés est d et l’univers des clés est donc B (d) = {0, 1} d . Dans ce modèle, le
nombre de clés vérifie nécessairement n ≤ 2 d . La figure 7.2 représente l’ensemble
des tries binaires construits sur B (3) . Comme plusieurs sous-ensembles de B (3)
donnent lieu à la même forme de trie, nous indiquons au dessus de chaque forme
d’arbre le nombre de sous-ensembles correspondants.
Remarque 7.1 Pour d = 0, l’univers des clés est constitué uniquement du mot
vide ε et les seuls ensembles possibles sont ω = {ε} et ω = ∅, qui correspondent
respectivement à un trie réduit à une feuille (étiquetée par ε) et au trie vide.
Séries génératrices Nous commençons par définir un type de série génératrice
adapté au modèle fini équiprobable.
Définition 7.2 La série génératrice cumulée d’un paramètre v pour les mots de
longueur d est notée v (d) (z). Elle est définie par
v
(d) (z) =
2 d
n=0
v
(d)
n z
n , où v
(d)
n =
ω⊂{0,1} d
|ω|=n
v(ω).
(7.7)
285
les relations suivantes :
χ k (ω) =
χ 0 (ω) = 1 {|ω|≤1}
si k = 0,
χ k−1 (ω \ 0) χ k−1 (ω \ 1) sinon.
(7.6)
Ce paramètre évalué en moyenne (avec un modèle probabiliste sur ω) donne
accès à la probabilité qu’un trie soit de hauteur inférieure ou égale à k. En effet,
la probabilité d’un événement est égale à l’espérance de son indicatrice. Dans un
modèle probabiliste donné, nous avons pour la hauteur h d’un trie
P(h ≤ k) = E[χ k ].
Les expressions précédentes pour les paramètres se prêtent de manière élégante
à une approche qui utilise les séries génératrices, dite par « algèbre de coûts »
(appellation provenant d’un article de Flajolet et al. [97] dont s’inspirent grandement
les sections suivantes).
7.1.1 Approche symbolique (modèle fini équiprobable)
Dans le modèle fini équiprobable (définition 2.16 dans la section 2.3.1), la longueur
des clés est d et l’univers des clés est donc B (d) = {0, 1} d . Dans ce modèle, le
nombre de clés vérifie nécessairement n ≤ 2 d . La figure 7.2 représente l’ensemble
des tries binaires construits sur B (3) . Comme plusieurs sous-ensembles de B (3)
donnent lieu à la même forme de trie, nous indiquons au dessus de chaque forme
d’arbre le nombre de sous-ensembles correspondants.
Remarque 7.1 Pour d = 0, l’univers des clés est constitué uniquement du mot
vide ε et les seuls ensembles possibles sont ω = {ε} et ω = ∅, qui correspondent
respectivement à un trie réduit à une feuille (étiquetée par ε) et au trie vide.
Séries génératrices Nous commençons par définir un type de série génératrice
adapté au modèle fini équiprobable.
Définition 7.2 La série génératrice cumulée d’un paramètre v pour les mots de
longueur d est notée v (d) (z). Elle est définie par
v
(d) (z) =
2 d
n=0
v
(d)
n z
n , où v
(d)
n =
ω⊂{0,1} d
|ω|=n
v(ω).
(7.7)