TD d’algorithmique avanc´ee
TD 4 : recherche de l’´el´ement majoritaire
Jean-Michel Dischler et Fr´ed´eric Vivien
Nous nous int´eressons `a un tableau A de n ´el´ements, n ´etant suppos´e ˆetre une puissance de deux. Nous
supposons ´egalement que la seule op´eration `a notre disposition nous permet de v´erifier si deux ´el´ements sont
ou non ´egaux. Un ´el´ement x de A est dit majoritaire si et seulement si A contient strictement plus de n/2
occurrences de x. Nous nous int´eresserons `a la complexit´e au pire.
Publicité
Algorithme na¨ıf
1. ´Ecrivez un algorithme qui calcule le nombre d’occurrences d’une valeur x pr´esentes entre les indices i
et j d’un tableau A.
2. Quelle est la complexit´e de cet algorithme ?
3. Au moyen de l’algorithme pr´ec´edent, ´ecrivez un algorithme Majoritaire qui v´erifie si un tableau A
contient un ´el´ement majoritaire.
4. Quelle est la complexit´e de cet algorithme ?
Publicité
Premier algorithme « diviser pour r´egner »
1. Proposez un algorithme Majoritaire construit suivant le paradigme « diviser pour r´egner ». Cet
algorithme divisera en deux le tableau A sur lequel il travaille. Il renverra le couple (Vrai, x) si le
tableau A contient un ´el´ement majoritaire (x ´etant cet ´el´ement) et renverra le couple (Faux, 0) si le
tableau A ne contient pas d’´el´ement majoritaire.
2. Quelle est la complexit´e de cet algorithme ?
Deuxi`eme algorithme « diviser pour r´egner »
Publicité
1. ´Ecrivez un algorithme construit suivant le paradigme « diviser pour r´egner », prenant en entr´ee un
tableau A —qu’il divisera en deux— et poss´edant la propri´et´e suivante :
– soit cet algorithme nous garantit que le tableau A ne contient pas d’´el´ement majoritaire ;
– soit cet algorithme nous renvoie un ´el´ement x et un entier cx > n/2 tels que x apparaisse au plus cx
fois dans A et que tout autre ´el´ement de A apparaisse au plus n − cx fois dans A.
2. Quelle est la complexit´e de cet algorithme ?
3. `A partir de l’algorithme pr´ec´edent, ´ecrivez un algorithme Majoritaire qui v´erifie si un tableau A
Publicité
contient un ´el´ement majoritaire.
4. Quelle est la complexit´e de cet algorithme ?