Ecole normale superieure Departement d'informatique
3
pages
Français
Documents
Obtenez un accès à la bibliothèque pour le consulter en ligne En savoir plus
Découvre YouScribe en t'inscrivant gratuitement
Découvre YouScribe en t'inscrivant gratuitement
3
pages
Français
Documents
Obtenez un accès à la bibliothèque pour le consulter en ligne En savoir plus
Ecole normale superieure 2010-2011 Departement d'informatique Algorithmique et Programmation TD n? 2 : Tris et hachage Exercice 1. Nous voulons calculer le nombre moyen d'affectations Moy(n) de l'algorithme naıf de recherche du maximum sur un tableau de n elements distincts. Soit Pn,k le nombre de permutations ayant k maximum provisoire de gauche a droite (MPGD). 1. Montrer que Moy(n) = n∑ k=1 k Pn,k n! . 2. Montrer que le nombre de permutations ayant k MPGD verifie : – P1,1 = 1, Pn,0 = 0, pour n ≥ 1 et Pn,k = 0 pour k > n. – Pn,k = (n? 1)Pn?1,k + Pn?1,k?1, pour n ≥ 2, k ≥ 1. 3. Pour resoudre cette relation de recurrence, utiliser la serie generatrice associee aux (Pn,k)k?N et montrer que si Gn(z) = ∑ k≥0 Pn,kz k, alors pour n ≥ 1, nous avons Gn(z) = z(z + 1) . . . (z + n? 1). 4. En conclure que Moy(n) = G?n(1)/Gn(1) et que Moy(n) = Hn le n-ieme nombre harmonique Hn = 1 + 1 2 + · · ·+ 1 n de l'ordre de ?(log n).
Voir
- tri rapide pour determiner
- duree de l'execution de l'algorithme
- procedure trier
- hypothese particuliere sur l'algorithme de pivotage
- hypothese
- algorithme naıf de recherche
´ Ecolenormalesup´erieure D´epartementd’informatique
Algorithmique et Programmation ◦ TD n2 : Tris et hachage
2010-2011
Exercice 1.Nous voulons calculer le nombre moyen d’affectations Moy(n) de l’algorithme na¨ıf de recherche du maximum sur un tableau dentcnitsidstneme´l´eitSos.Pn,kle nombre de permutations ayantkamumixorpmdaorti(ePMDG.)visoiredegauche` 1. Montrerque n X Pn,k Moy(n) =k . n! k=1 2. Montrerque le nombre de permutations ayantk´vDGfiiree:PM –P1,1= 1,Pn,0= 0, pourn≥1 etPn,k= 0 pourk > n. –Pn,k= (n−1)Pn−1,k+Pn−1,k−1, pourn≥2,k≥1. 3.Pourre´soudrecetterelationder´ecurrence,utiliserlase´riege´n´eratriceassoci´eeaux(Pn,k)k∈Net P k montrer que siGn(z) =Pn,kz, alors pourn≥1, nous avons k≥0 Gn(z) =z(z+ 1). . .(z+n−1). 0 ure que Moy(n) nombreharmonique 4. Enconcl =Gn(1)/Gn(1) et que Moy(n) =Hnlenme`e-i 1 1 Hn+= 1 +∙ ∙ ∙+ 2n de l’ordre de Θ(logn).
Exercice 2.uodrdipemrnie´etantevariirapdutritusnollenuresilcierexetsaou,nceDscanleerki`-eem ´el´ementd’unensembledensi’dnuce´l.eoNsu´el´ementsmunseleuqsnosoppusnnctiistdonss´ecluexetds a`deux.Nousconsid´eronsdansunpremiertemps,lafonctionSle´etcoinnresuivante :
FonctionS´electionner(t, i, j, k):e´elemtn // on suppose quek∈[1, n]. sii=jalors retournert[i] fin si p:=Pivoter(t, i, j) ; sik < p alors retournerrennoitcele´S(t, i, p, k) sinon retournerrS´electionne(t, p+ 1, j, k−p) fin si
o`ulafonctionPivoterretourne un entierp∈ {i+ 1, . . . , j−1}rteinagroe´mpteensesO(n) le tableau t[i..j] en deux sous-tableauxt[i..p] ett[p+ 1..ju’´nlee´]etsluqdeuenqcoelquntmet[i..puede`ssop]´enecl inf´erieureoue´gale`acelled’une´l´ementquelconquedet[p+ 1..j]. 1.Montrerquelaproc´edurerennoitcS´eleleneimrete´dki`-´eele´emudatemtn.ulbae 2.Monterquequesanshypoth`eseparticulie`resurl’algorithmedepivotage,lafonctionele´Sctionner 2 peutr´ealiserO(n) comparaisons. 3.Montrerquesil’algorithmedepivotagegarantitquelatailledusous-tableaudel’appelr´ecursifne d´epassepasαnou`α <nneerbmocedeapmoisrasdonafelcton1,lacomplexit´nioernnioctle´eSest O(n).
1
