Remerciez-le!

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

Pdfjoiner TD d ? algorithmique avanc ?ee TD recherche par rang Jean-Michel Dischler et Fr ?ed ?eric Vivien Recherche du maximum Concevez un algorithme de recherche du maximum dans un ensemble a n ?el ?ements vous disposez en tout et pour tout d ? une fonc

TD d ? algorithmique avanc ?ee TD recherche par rang Jean-Michel Dischler et Fr ?ed ?eric Vivien Recherche du maximum 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 Quelle est la complexit ?e de votre algorithme en nombre de comparaisons Montrez qu ? il est optimal Recherche du deuxieme plus grand ?el ?ement Nous supposerons ici que l ? ensemble consid ?er ?e ne contient pas deux fois la m eme valeur Proposez un algorithme simple de recherche du deuxieme plus grand ?el ?ement Quel est sa complexit ?e en nombre de comparaisons 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 Dans combien de comparaisons le deuxieme plus grand ?el ?ement de l ? ensemble a-t-il ?et ?e trouv ?e etre le plus petit des deux ?el ?ements compar ?es Proposez un nouvel algorithme de recherche du deuxieme plus grand ?el ?ement 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 Proposez un algorithme na ? f de recherche du maximum et du minimum d ? un ensemble de n ?el ?ements Quelle est sa complexit ?e en nombre de comparaisons Proposez un algorithme plus e ?cace Indication dans une premi ere phase les ?el ?ements sont compar ?es par paire Quelle est sa complexit ?e en nombre de comparaisons 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 CTD d ? algorithmique avanc ?ee Corrig ?e du TD recherche par rang Jean- Michel Dischler et Fr ?ed ?eric Vivien Recherche du maximum 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 pour i a n faire si max ? A i alors max A i renvoyer max Quelle est la complexit ?e de votre algorithme