106
3 Arbres, algorithmes et données
3.4.4 Algorithme des buveurs de bière
Cet algorithme, aussi connu sous le nom plus « politiquement correct » d’élection
de leader, permet de décider, parmi un groupe de n personnes parties au café, qui
paiera la tournée générale. Il fonctionne ainsi : chacun tire à pile ou face ; si tous
tirent Face l’algorithme échoue ; sinon le perdant (celui qui aura à payer la tournée)
est choisi, suivant la même procédure, parmi les personnes qui ont tiré Pile (il y en
a au plus n − 1). Cf. la présentation de ce problème par Prodinger [217].
C’est un problème classique qui se retrouve par exemple en algorithmique
répartie : choisir symétriquement (de façon que chacun ait la même probabilité
d’être choisi) un « leader », i.e., une entité parmi n. Le processus de choix, très
simple, s’exprime de façon récursive :
Chaque personne choisit aléatoirement un bit Pile (P) ou Face (F), indépendamment des
autres. Si tous tirent Face, l’algorithme de choix échoue ; si une seule personne choisit
Pile, c’est elle qui est retenue ; sinon les personnes qui ont tiré Face sont éliminées et
celles qui ont tiré Pile prennent part au tirage suivant.
Si à chaque personne est associée la suite (finie) de bits qu’elle a tirée, que nous
pouvons aussi voir comme une clé, l’algorithme revient à construire (fictivement) un
trie sur ces clés, et à retenir la personne correspondant à la feuille de la branche P ∗
du trie, i.e., la branche correspondant au mot P P . . . . Ce choix est fait au bout d’un
nombre d’essais égal à la longueur de cette branche ; il échoue si elle est absente.
Notons que l’algorithme termine presque sûrement en un temps fini.
La probabilité que l’algorithme choisisse un payeur est la probabilité que la
feuille la plus à gauche corresponde à une clé dont le préfixe permettant de la
distinguer des autres clés est P . . . P , et le temps de résolution, compté en nombre
de tours, est égal à la profondeur de cette feuille (figure 3.33).
Fig. 3.33 Partant de cinq
personnes P 1 , . . . , P 5 ,
l’algorithme des buveurs de
bière détermine qui paiera.
Au premier tour, P 3 et P 4
tirent Face et ne participent
donc pas aux tours suivants ;
puis P 2 tire Face et sort à son
tour ; enfin P 1 tire Pile et P 5
Face. Il a fallu trois tours
pour déterminer que c’est P 1
qui paie
3 Arbres, algorithmes et données
3.4.4 Algorithme des buveurs de bière
Cet algorithme, aussi connu sous le nom plus « politiquement correct » d’élection
de leader, permet de décider, parmi un groupe de n personnes parties au café, qui
paiera la tournée générale. Il fonctionne ainsi : chacun tire à pile ou face ; si tous
tirent Face l’algorithme échoue ; sinon le perdant (celui qui aura à payer la tournée)
est choisi, suivant la même procédure, parmi les personnes qui ont tiré Pile (il y en
a au plus n − 1). Cf. la présentation de ce problème par Prodinger [217].
C’est un problème classique qui se retrouve par exemple en algorithmique
répartie : choisir symétriquement (de façon que chacun ait la même probabilité
d’être choisi) un « leader », i.e., une entité parmi n. Le processus de choix, très
simple, s’exprime de façon récursive :
Chaque personne choisit aléatoirement un bit Pile (P) ou Face (F), indépendamment des
autres. Si tous tirent Face, l’algorithme de choix échoue ; si une seule personne choisit
Pile, c’est elle qui est retenue ; sinon les personnes qui ont tiré Face sont éliminées et
celles qui ont tiré Pile prennent part au tirage suivant.
Si à chaque personne est associée la suite (finie) de bits qu’elle a tirée, que nous
pouvons aussi voir comme une clé, l’algorithme revient à construire (fictivement) un
trie sur ces clés, et à retenir la personne correspondant à la feuille de la branche P ∗
du trie, i.e., la branche correspondant au mot P P . . . . Ce choix est fait au bout d’un
nombre d’essais égal à la longueur de cette branche ; il échoue si elle est absente.
Notons que l’algorithme termine presque sûrement en un temps fini.
La probabilité que l’algorithme choisisse un payeur est la probabilité que la
feuille la plus à gauche corresponde à une clé dont le préfixe permettant de la
distinguer des autres clés est P . . . P , et le temps de résolution, compté en nombre
de tours, est égal à la profondeur de cette feuille (figure 3.33).
Fig. 3.33 Partant de cinq
personnes P 1 , . . . , P 5 ,
l’algorithme des buveurs de
bière détermine qui paiera.
Au premier tour, P 3 et P 4
tirent Face et ne participent
donc pas aux tours suivants ;
puis P 2 tire Face et sort à son
tour ; enfin P 1 tire Pile et P 5
Face. Il a fallu trois tours
pour déterminer que c’est P 1
qui paie