Ecole normale superieure Departement d'informatique

Description

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

Sujets

• Hypothèse

Informations

• Publié par: pefav
• Nombre de lectures: 52
• Langue: Français

Extrait

´ 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.P n,k le nombre de permutations ayantkamumixorpmdaorti(ePMDG.)visoiredegauche` 1. Montrerque n X P n,k Moy(n) =k . n! k=1 2. Montrerque le nombre de permutations ayantk´vDGfiiree:PM –P 1,1 = 1,P n,0 = 0, pourn≥1 etP n,k = 0 pourk > n. –P n,k = (n−1)P n−1,k +P n−1,k−1 , pourn≥2,k≥1. 3.Pourre´soudrecetterelationder´ecurrence,utiliserlase´riege´n´eratriceassoci´eeaux(P n,k ) k∈N et P k montrer que siG n (z) =P n,k z, alors pourn≥1, nous avons k≥0 G n (z) =z(z+ 1). . .(z+n−1). 0 ure que Moy(n) nombreharmonique 4. Enconcl =G n (1)/G n (1) et que Moy(n) =H n lenme`e-i 1 1 H n += 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