Cet ouvrage et des milliers d'autres font partie de la bibliothèque YouScribe
Obtenez un accès à la bibliothèque pour les lire en ligne
En savoir plus

Partagez cette publication

´ Ecolenormalesup´erieure D´epartementdinformatique
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´vDGiree:PM P1,1= 1,Pn,0= 0, pourn1 etPn,k= 0 pourk > n. Pn,k= (n1)Pn1,k+Pn1,k1, pourn2,k1. 3.Pourre´soudrecetterelationder´ecurrence,utiliserlase´riege´n´eratriceassoci´eeaux(Pn,k)kNet P k montrer que siGn(z) =Pn,kz, alors pourn1, nous avons k0 Gn(z) =z(z+ 1). . .(z+n1). 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´ementdunensembledensidnuce´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, kp) fin si
o`ulafonctionPivoterretourne un entierp∈ {i+ 1, . . . , j1}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`acelledune´l´ementquelconquedet[p+ 1..j]. 1.Montrerquelaproc´edurerennoitcS´eleleneimrete´dki`-´eele´emudatemtn.ulbae 2.Monterquequesanshypoth`eseparticulie`resurlalgorithmedepivotage,lafonctionele´Sctionner 2 peutr´ealiserO(n) comparaisons. 3.Montrerquesilalgorithmedepivotagegarantitquelatailledusous-tableaudelappelr´ecursifne d´epassepasαnou`α <nneerbmocedeapmoisrasdonafelcton1,lacomplexit´nioernnioctle´eSest O(n).
1
Un pour Un
Permettre à tous d'accéder à la lecture
Pour chaque accès à la bibliothèque, YouScribe donne un accès à une personne dans le besoin