108
3 Arbres, algorithmes et données
Fig. 3.34 L’arbre permettant de résoudre le conflit entre cinq stations souhaitant émettre au même
moment. Au premier tour, les stations S 3 et S 4 tirent Face et ne participent pas au tour suivant.
Les stations S 1 , S 2 et S 5 , qui ont tiré Pile au premier tour, participent au second tour ; elles tirent
toutes les trois Face et se retrouvent pour un nouveau tirage. À ce troisième tirage la station S 2
tire Face et les deux autres Pile ; le quatrième tour est donc entre S 1 et S 5 qui se départagent au
tirage suivant, S 1 tirant Pile et S 5 Face. La station S 1 est donc la première à émettre, suivie par
S 5 puis par S 2 . Ensuite, les stations S 3 et S 4 se départagent : elles tirent toutes deux Pile, puis de
nouveau Pile, et il faut encore un tirage pour les départager : S 3 tirant Face alors que S 4 a tiré
Pile, c’est S 4 qui émet ensuite, et S 3 est la dernière station à émettre. Le temps avant la première
émission, compté en nombre de tirages, est 4, le temps total pour résoudre les conflits est 7, et
l’ordre d’émission est S 1 , S 5 , S 2 , S 4 , S 3
Si nous associons à chaque station une suite de {Pile, Face } +∞ , i.e., une suite
de bits, le protocole en arbre revient simplement à construire un trie sur ces suites
de bits, et à permettre aux stations d’émettre suivant l’ordre induit par un parcours
préfixe du trie.
La profondeur de la feuille la plus à gauche du trie donne le temps écoulé avant
que la première station puisse commencer à émettre, compté en nombre de tours ;
l’ordre d’émission des stations est celui des étiquettes des feuilles dans le parcours
en ordre préfixe de l’arbre ; et le temps total de résolution de la collision, toujours
compté en nombre de tours, est égal au nombre de nœuds internes de l’arbre.
3.4.6 Échantillonnage adaptatif
Certaines applications informatiques, par exemple en bases de données ou en
administration de réseaux, conduisent au problème suivant, qui est un exemple
d’algorithme de « streaming » ou « comptage probabiliste » : comment évaluer
« rapidement » le nombre d’éléments distincts dans un ensemble avec répétitions ?
Nous ne voulons pas trier cet ensemble, ni faire beaucoup plus que le lire une seule
fois. Dans certaines applications, les données sont d’ailleurs lues « au vol » lors de
3 Arbres, algorithmes et données
Fig. 3.34 L’arbre permettant de résoudre le conflit entre cinq stations souhaitant émettre au même
moment. Au premier tour, les stations S 3 et S 4 tirent Face et ne participent pas au tour suivant.
Les stations S 1 , S 2 et S 5 , qui ont tiré Pile au premier tour, participent au second tour ; elles tirent
toutes les trois Face et se retrouvent pour un nouveau tirage. À ce troisième tirage la station S 2
tire Face et les deux autres Pile ; le quatrième tour est donc entre S 1 et S 5 qui se départagent au
tirage suivant, S 1 tirant Pile et S 5 Face. La station S 1 est donc la première à émettre, suivie par
S 5 puis par S 2 . Ensuite, les stations S 3 et S 4 se départagent : elles tirent toutes deux Pile, puis de
nouveau Pile, et il faut encore un tirage pour les départager : S 3 tirant Face alors que S 4 a tiré
Pile, c’est S 4 qui émet ensuite, et S 3 est la dernière station à émettre. Le temps avant la première
émission, compté en nombre de tirages, est 4, le temps total pour résoudre les conflits est 7, et
l’ordre d’émission est S 1 , S 5 , S 2 , S 4 , S 3
Si nous associons à chaque station une suite de {Pile, Face } +∞ , i.e., une suite
de bits, le protocole en arbre revient simplement à construire un trie sur ces suites
de bits, et à permettre aux stations d’émettre suivant l’ordre induit par un parcours
préfixe du trie.
La profondeur de la feuille la plus à gauche du trie donne le temps écoulé avant
que la première station puisse commencer à émettre, compté en nombre de tours ;
l’ordre d’émission des stations est celui des étiquettes des feuilles dans le parcours
en ordre préfixe de l’arbre ; et le temps total de résolution de la collision, toujours
compté en nombre de tours, est égal au nombre de nœuds internes de l’arbre.
3.4.6 Échantillonnage adaptatif
Certaines applications informatiques, par exemple en bases de données ou en
administration de réseaux, conduisent au problème suivant, qui est un exemple
d’algorithme de « streaming » ou « comptage probabiliste » : comment évaluer
« rapidement » le nombre d’éléments distincts dans un ensemble avec répétitions ?
Nous ne voulons pas trier cet ensemble, ni faire beaucoup plus que le lire une seule
fois. Dans certaines applications, les données sont d’ailleurs lues « au vol » lors de