Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

TD d’algorithmique avanc´ ee TD 1 : recherche par rang Jean-Michel Dischler et

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. 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 ﬁgure explicative sera amplement suﬃsante. 4. Dans combien de comparaisons, le deuxi` eme plus grand ´ el´ ement de l’ensemble a-t-il ´ et´ e trouv´ e ˆ etre le 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 eﬃcace. 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 ? (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. TD d’algorithmique avanc´ ee Corrig´ e du 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). Maximum(A) max ←A[1] pour i ←2 ` a n faire si max ¡ A[i] alors max ←A[i] renvoyer max 2. Quelle est la complexit´ e de votre algorithme en nombre de comparaisons ? R´ eponse : n −1. 3. Montrez qu’il est optimal. Tout ´ el´ ement hormis le maximum doit avoir perdu une comparaison, sinon, on ne peut pas savoir qu’il n’est pas le maximum. Il y a n −1 tels ´ el´ ements. Tout algorithme de recherche du maximum doit donc faire au moins n −1 comparaisons. 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. Deuxi` eme-Plus-Grand(A) rang max ←1 pour i ←2 ` a n faire si A[rang max] ¡ A[i] alors rang max ←i si rang max ̸= 1 alors rang second ←1 sinon rang second ←2 pour i ←2 ` a n faire si i ̸= rang max et A[rang second] ¡ A[i] alors rang second ←i renvoyer A[rang second] 2. Quel est sa complexit´ e en nombre de comparaisons ? La recherche du maximum coˆ ute n −1 comparaisons. La boucle qui recherche le deuxi` eme plus grand ´ el´ ement une fois que le maximum a ´ et´ e trouv´ e eﬀectue n−2 comparaisons. D’o` u un coˆ ut total de 2n−3 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 ﬁgure explicative sera amplement suﬃsante. Les comparaisons sont organis´ ees comme dans un tournoi : – Dans une premi` ere phase, les valeurs sont compar´ ees par paires. Dans chaque paire, il y a bien sˆ ur un plus grand ´ el´ ement (le « vainqueur ») et un plus petit ´ el´ ement (le « vaincu »). – Dans la deuxi` eme phase, les valeurs qui ´ etaient plus grand ´ el´ ement de leur paire ` a la phase pr´ ec´ edente sont compar´ ees entres elles deux ` a deux. 1 – On r´ ep` ete ce processus jusqu’au moment o` u il n’y a plus qu’un plus grand ´ el´ ement. Ce proc´ ed´ e est illustr´ e par la ﬁgure 1. 3 1 3 5 9 9 9 8 5 5 2 6 8 9 4 A B C D Fig. 1 – M´ ethode du tournoi pour la d´ etermination du maximum : A : les ´ el´ ements sont compar´ es par paires ; B : les plus grands ´ el´ ements de la phase A sont compar´ es entre eux, par paires ; C : les ´ el´ ements « vainqueurs » ` a la phase B sont compar´ es entre eux ; D : il ne reste plus qu’un ´ el´ ement, c’est l’´ el´ ement maximal. 3 1 3 9 9 9 5 5 2 6 8 9 5 8 4 Fig. 2 – Le deuxi` eme plus grand ´ el´ ement a n´ ecessairement ´ et´ e battu par le plus grand ´ el´ ement (et que par lui). Il ﬁgure donc parmi les ´ el´ ements compar´ es ` a l’´ el´ ement maximal. Ces ´ el´ ements appa- raissent ici sur fond noir. 4. Dans combien de comparaisons, le deuxi` eme plus grand ´ el´ ement de l’ensemble a-t-il ´ et´ e trouv´ e ˆ etre le plus petit des deux ´ el´ ements compar´ es ? Le deuxi` eme plus grand n’est plus petit que devant le plus grand ´ el´ ement. Il n’a donc « perdu » que dans une comparaison, celle avec le plus grand ´ el´ ement. 5. Proposez un nouvel algorithme de recherche du deuxi` eme plus grand ´ el´ ement. Le deuxi` eme plus grand ´ el´ ement est donc un des ´ el´ ements qui ont ´ et´ e battus par le plus grand ´ el´ ement. L’algorithme a lieu en deux phases : (a) On recherche tout d’abord le plus grand ´ el´ ement suivant la m´ ethode du tournoi. (b) On obtient le deuxi` eme plus grand ´ el´ ement en recherchant l’´ el´ ement maximal parmi ceux qui ont ´ et´ e ´ elimin´ es du tournoi lors d’une comparaison avec l’´ el´ ement maximal. Voir la ﬁgure 2. 6. Quelle est sa complexit´ e en nombre de comparaisons ? La recherche de l’´ el´ ement maximal coˆ ute n −1 comparaisons, comme d’habitude. Ensuite la recherche du deuxi` eme plus grand ´ el´ ement nous coˆ ute m −1 comparaisons, o` u m est le nombre d’´ el´ ements ` a qui l’´ el´ ement maximal a ´ et´ e compar´ e. Dans le pire cas 1, m est ´ egal ` a la hauteur de l’arbre moins 1 (un arbre r´ eduit ` a sa racine ´ etant de hauteur un). Or un arbre binaire presque parfait ` a n feuilles est de hauteur ⌈log2 n⌉. D’o` u la complexit´ e : T(n) = n + ⌈log2 n⌉−2 Note : cet algorithme est optimal. 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. 1Quand n n’est pas une puissance de deux, la complexit´ e peut varier d’une comparaison suivant la place initiale dans l’arbre du maximum. 2 Maximum-et-Minimum(A) max ←A[1] pour i ←2 ` a n faire si max ¡ A[i] alors max ←A[i] min ←A[1] pour i ←2 ` a n faire si min ¿ A[i] alors min ←A[i] renvoyer max et min 2. Quelle est sa complexit´ e en nombre de comparaisons ? Cet algorithme eﬀectue 2n −2 comparaisons. 3. Proposez un algorithme plus eﬃcace. Indication : dans une premi` ere phase les ´ el´ ements sont compar´ es par paire. L’algorithme se d´ uploads/Science et Technologie/ pdfjoiner.pdf