334
7 Arbres digitaux
7.5. Élection de leader Analyser la probabilité d’échec de l’algorithme standard d’élection
d’un leader (survenant si à un tour du processus tout le monde tire 1) tel que présenté dans la
section 3.4.4.
7.6. PATRICIA trie
– Expliquer dans le modèle fini équiprobable avec un alphabet binaire, pourquoi la série
génératrice cumulée associée au nombre de nœuds internes d’un trie PATRICIA est
v
(d) (z) =
2 d
n=2
(n − 1)
n
2 d
z
n .
(Indication : en fait cela n’a rien à voir avec les tries. Expliquer pourquoi un trie PATRICIA sur
un alphabet binaire contenant n mots distincts possède exactement n − 1 nœuds internes.)
– Montrer ensuite que le péage pour compter les nœuds binaires d’un trie (et donc le nombre de
nœuds internes d’un trie PATRICIA) s’écrit :
γ
(d) = 1 {|ω\0|} × 1 {|ω\1|} .
Trouver l’expression de la série génératrice cumulée correspondante. Vérifier que l’on retrouve
bien l’expression précédente (au besoin à l’aide d’un logiciel de calcul formel).
7.7. Nœuds unaires d’un trie Exprimer le péage permettant de calculer le nombre de nœuds
unaire d’un trie (en s’aidant au besoin de la question précédente) et analyser le nombre de nœuds
unaires d’un trie dans le modèle fini équiprobable avec alphabet binaire.
7.8. PATRICIA trie Cet exercice se place dans le modèle infini i.i.d. uniforme avec alphabet
binaire. Montrer que les récurrences pour l’espérance de la longueur de cheminement d’un trie
L
(t)
n et d’un trie PATRICIA L
(p)
n pour n mots s’écrivent respectivement
L
(t)
n = n + 2
n
k=0
k
n
2 n L
(t)
k , k ≥ 2, L
(t)
0 = L
(t)
1 = 0,
et
L
(p)
n = n
1 −
1
2 n−1
+ 2
n
k=0
k
n
2 n L
(p)
k , k ≥ 2, L
(p)
0 = L
(p)
1 = 0.
Indication : un sous-trie de n mots possède un sous-trie vide avec probabilité 1/2 n−1 .
Montrer par récurrence qu’on a
L
(t)
n − L
(p) = n.
Remarque. Bien sûr une approche moins élémentaire (par séries génératrices et utilisant les péages)
aboutit au même résultat.
7.9. Opérations ensemblistes Écrire les algorithmes qui réalisent l’intersection et la fusion de
deux tries.
Remarque : l’approche par « algèbre de coûts » peut servir à analyser le coût de ces opérations
(voir [97]).
7.10. Paramètres additifs des b-tries Étendre les analyses exactes dans le cas des b-tries pour
la longueur de cheminement dans les modèles fini équiprobable et infini i.i.d. uniforme.
7.11. Hauteur des b-tries
Calculer dans le cas du modèle infini i.i.d uniforme pour un alphabet de cardinal b, la fonction
de Dirichlet associée λ(s) =
w∈A ∗ p s
w .
7 Arbres digitaux
7.5. Élection de leader Analyser la probabilité d’échec de l’algorithme standard d’élection
d’un leader (survenant si à un tour du processus tout le monde tire 1) tel que présenté dans la
section 3.4.4.
7.6. PATRICIA trie
– Expliquer dans le modèle fini équiprobable avec un alphabet binaire, pourquoi la série
génératrice cumulée associée au nombre de nœuds internes d’un trie PATRICIA est
v
(d) (z) =
2 d
n=2
(n − 1)
n
2 d
z
n .
(Indication : en fait cela n’a rien à voir avec les tries. Expliquer pourquoi un trie PATRICIA sur
un alphabet binaire contenant n mots distincts possède exactement n − 1 nœuds internes.)
– Montrer ensuite que le péage pour compter les nœuds binaires d’un trie (et donc le nombre de
nœuds internes d’un trie PATRICIA) s’écrit :
γ
(d) = 1 {|ω\0|} × 1 {|ω\1|} .
Trouver l’expression de la série génératrice cumulée correspondante. Vérifier que l’on retrouve
bien l’expression précédente (au besoin à l’aide d’un logiciel de calcul formel).
7.7. Nœuds unaires d’un trie Exprimer le péage permettant de calculer le nombre de nœuds
unaire d’un trie (en s’aidant au besoin de la question précédente) et analyser le nombre de nœuds
unaires d’un trie dans le modèle fini équiprobable avec alphabet binaire.
7.8. PATRICIA trie Cet exercice se place dans le modèle infini i.i.d. uniforme avec alphabet
binaire. Montrer que les récurrences pour l’espérance de la longueur de cheminement d’un trie
L
(t)
n et d’un trie PATRICIA L
(p)
n pour n mots s’écrivent respectivement
L
(t)
n = n + 2
n
k=0
k
n
2 n L
(t)
k , k ≥ 2, L
(t)
0 = L
(t)
1 = 0,
et
L
(p)
n = n
1 −
1
2 n−1
+ 2
n
k=0
k
n
2 n L
(p)
k , k ≥ 2, L
(p)
0 = L
(p)
1 = 0.
Indication : un sous-trie de n mots possède un sous-trie vide avec probabilité 1/2 n−1 .
Montrer par récurrence qu’on a
L
(t)
n − L
(p) = n.
Remarque. Bien sûr une approche moins élémentaire (par séries génératrices et utilisant les péages)
aboutit au même résultat.
7.9. Opérations ensemblistes Écrire les algorithmes qui réalisent l’intersection et la fusion de
deux tries.
Remarque : l’approche par « algèbre de coûts » peut servir à analyser le coût de ces opérations
(voir [97]).
7.10. Paramètres additifs des b-tries Étendre les analyses exactes dans le cas des b-tries pour
la longueur de cheminement dans les modèles fini équiprobable et infini i.i.d. uniforme.
7.11. Hauteur des b-tries
Calculer dans le cas du modèle infini i.i.d uniforme pour un alphabet de cardinal b, la fonction
de Dirichlet associée λ(s) =
w∈A ∗ p s
w .