Cet ouvrage fait partie de la bibliothèque YouScribe
Obtenez un accès à la bibliothèque pour le lire en ligne
En savoir plus

Ecole normale superieure Departement d'informatique

3 pages
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).

  • 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


Voir plus Voir moins
´ 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