TD d’algorithmique avanc´ee
TD 1 : recherche par rang
Jean-Michel Dischler et Fr´ed´eric Vivien
Recherche du maximum
1. Concevez un algorithme de recherche du maximum dans un ensemble `a n ´el´ements (vous disposez en
tout et pour tout d’une fonction de comparaison).
2. Quelle est la complexit´e de votre algorithme en nombre de comparaisons ?
3. Montrez qu’il est optimal.
Publicité
Recherche du deuxi`eme plus grand ´el´ement
Nous supposerons ici que l’ensemble consid´er´e ne contient pas deux fois la mˆeme valeur.
1. Proposez un algorithme simple de recherche du deuxi`eme plus grand ´el´ement.
2. Quel est sa complexit´e en nombre de comparaisons ?
3. R´ecrivez votre algorithme de recherche du maximum sous la forme d’un tournoi (de tennis, de foot,
de p´etanque ou de tout autre sport). Il n’est pas n´ecessaire de formaliser l’algorithme ici, une figure
explicative sera amplement suffisante.
4. Dans combien de comparaisons, le deuxi`eme plus grand ´el´ement de l’ensemble a-t-il ´et´e trouv´e ˆetre le
Publicité
plus petit des deux ´el´ements compar´es ?
5. Proposez un nouvel algorithme de recherche du deuxi`eme plus grand ´el´ement.
6. Quelle est sa complexit´e en nombre de comparaisons ?
Recherche du maximum et du minimum
Nous supposerons ici que l’ensemble consid´er´e ne contient pas deux fois la mˆeme valeur.
1. Proposez un algorithme na¨ıf de recherche du maximum et du minimum d’un ensemble de n ´el´ements.
2. Quelle est sa complexit´e en nombre de comparaisons ?
3. Proposez un algorithme plus efficace.
Publicité
Indication : dans une premi`ere phase les ´el´ements sont compar´es par paire.
4. Quelle est sa complexit´e en nombre de comparaisons ?
5. Montrez que cet algorithme est optimal.
Indication : on appelle unit´e d’information :
– l’information « l’´el´ement x ne peut pas ˆetre le plus grand ´el´ement » ;
– l’information « l’´el´ement x ne peut pas ˆetre le plus petit ´el´ement ».
(a) Quel est le nombre minimal d’unit´es d’information qu’un algorithme de recherche du maximum
et du minimum doit produire pour nous garantir la validit´e de son r´esultat ?
Publicité
(b) Combien d’unit´es d’information sont produites par la comparaison de deux ´el´ements (distinguez
des cas, suivant que l’on a ou non des unit´es d’informations sur ces valeurs).
(c) Concluez.