Ecole normale superieure Departement d'informatique

Publié par

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


Publié le : mardi 19 juin 2012
Lecture(s) : 51
Tags :
Source : di.ens.fr
Nombre de pages : 3
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
Onconsid`erelalgorithmedechoixdupivotsuivant: D´ecouperletableauenbn/5cblocks{B1, . . . , Bbn/5c}tnrselemsee´stl;usauplnts(estaeneml´´enqcide 4)neserontpasconside´r´esdanslasuitedelalgorithme; D´eterminerles´el´ementsm´ediansmkdesBk,k∈ {1, . . . ,bn/5c}; ´ – Utiliserla fonctionSelectionnerlemelr´imentereurd´porerdotdenb(n+5)/10cde la listem1, . . . , mbn/5c; (sibn/5cestpair,l´eldnledeaietlasistee´elmelem´ntnemelestitce´nnom1, . . . , mbn/5c).
4.Montrerquelepivotchoisieststrictementsupe´rieur`aaumoins3b(n5)/10centsde´el´emtet estinfe´rieurou´egala`aumoins3b(n5)/10ceme´le´entsdtduirnd´e.Eopruqeeun75, le sous tableaudelappelr´ecursifestdetailleauplus´egale`a3n/4.
Onconside`realorslafonction´eSrennioctlesuivante :
Fonction´eleSnnerctio(t, i, j, kleme):´etn siji74 alors Trier(t, i, j) ; retournerle´le´mentdordrekdet; sinon pourq`1aedb(ji)/5cfaire m(q) :=Mide´na(t,5(q1) +i,5(q1) +i+ 4) fin pour r:=S´rentionelec(m,1,b(ji)/5c,b(ji+ 5)/10c) p:=Partition(t, i, j, r) sik < p alors retournerernnSele´oitc(t, i, p, k) sinon retournerle´eSrennoitc(t, p+ 1, j, kp) fin si fin si
Laproce´dureTrierest un algorithme de tri quelconque. La fonction´edianMgnarfeolemenedtruinlt´3dunelistede5e´l´ements.Laproce´durePartitionlbatuae´eorrseleganiten prenantt[r;] comme pivot apr`essonex´ecution,un´el´ementquelconquedeT(i..pruei´uoelagea`e]aunecl´einf´ert[r],´euneml´ten quelconque det[p+ 1..jstnemetcueire´pu`areaune]stricl´et[r].
5.D´emontrerlavalidit´edelafonctionr´Sletiecneon. 6.Montrerquelacomplexit´edelafonctionSnnretcoie´elestO(n).
Exercice 3. ´ 1.Ecrireunalgorithmenaı¨fquicalculeleminimumetlemaximumsuruntableauden´etl´ementse donnersacomplexit´edanslepirecas. 2.Uneid´eepouram´eliorerlalgorithmeestderegrouperparpairesles´el´ements`acomparer,demani`ere `adiminuerensuitelenombredecomparaisons`aeectuer.De´crireunalgorithmefonctionnantselon ceprincipeetanalysersacomplexite´. 3.Montrerloptimalite´duntelalgorithmeenfournissantuneborneinf´erieuresurlenombrede comparaisonsa`eectuer. Indication :delm´ethodeOnalresilituarruopadversaire. SoitA´exeen´urcoaue,oP.muminnodenurudsunulaitquuvrorigomethtemuimelmelemixa de´roulementdelalgorithme,onappelle: novice(N)un´el´ementquinajamaissubidecomparaisons, gagnant(G)une´l´ementquiae´te´compar´eaumoinsunefoisetatoujourse´t´esup´erieuraux ´ele´mentsauxquelsila´et´ecompar´e,
2
Soyez le premier à déposer un commentaire !

17/1000 caractères maximum.