Algorithmique Avanc´eeexercices: "Divide and Conquer"Exercice 11.Coder l"algorithme de recherche MinMax "divide and conquer" vu au cours.
Donner avotre programme le comportement suivant :-Lecture d"un entiern.-G´en´eration un tableau denentiers al´eatoires entre 0 et 100.-Impression du min et le max.2.Comparer les vitesses d"ex´ecutions pour diff´erents ordres de grandeur den, en utilisantla fonctiontime1de linux.3.Suivre la mˆeme d´emarche pour l" algorithme de tri rapide "Quicksort".Exercice 2Trouver un algorithme direct pour MinMax qui exploite le fait qu"on calcule le Min et le Maxen mˆeme temps.Montrer que sa complexit´e moyenne est32n.Donner la complexit´e dans le pire des cas et dans le meilleur cas.Exercice 3Prouver (de fa¸con th´eorique) que la proc´edure partition (dans l"algorithme quicksort) fonc-tionne.Que se passe-t-il si on n"utilise pas des ´egalit´es strictes?G´en´eraliser cette proc´edure si le pivot n"est pas le premier nombre de la suite.Exercice 4Comparer les performances des impl´ementations r´ecursives et it´eratives de quicksort.Exercice 5Impl´ementer la version deselectavec le choix des pivots bas´e sur la m´ediane des m´edianes.Exercice 6Montrer les deux points suivants :nl-l-1l≤ ?nl? ≤nl?12?12?12···?12?12?????log2n?n??···???= 11Pour en savoir plus sur la fonctiontime, utilisez les pages de manuels :man time(depuis la console).1
