Algorithmique Exercice Max

Publié par

TD 2 Algorithmique Exercice 1: Max On veut calculer le nombre moyen d'affectations de l'algorithme naıf sur un tableau de n ele- ments. Soit Pn,k le nombre moyen 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 – 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, on a 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 nombre harmonique, Hn = 1 + 1/2 + . . .+ 1/n de l'ordre de ?(log n). Exercice 2: Min et Max 1.

  • tests d'appartenance en temps

  • compromis interessant entre espace necessaire

  • cout

  • temps necessaire pour selectionner

  • table ti de taille n2i


Publié le : mardi 19 juin 2012
Lecture(s) : 46
Source : di.ens.fr
Nombre de pages : 4
Voir plus Voir moins
NOM : PRENOM :
Date : Groupe :
Analyse:Feuilleder´eponsesduTP2 Extrema et bornes d’une fonction
. .
Onre´pondraauxquestionspos´eesaussiclairementquepossibledanslesespacespr´evus etonremettracettefeuilledere´ponsesenndeTP`alenseignantcharge´duTP.
Exercice 1.:iusstnavniseuqidncfoontisusuleelnuamojartnu,enersielleposs`edeesedunacchurPo bornesup´erieure,unminorant,uneborneinf´erieure,unmaximumglobal,unminimumglobal: 2 3 x7→ax+b ,x7→ −x ,x7→x ,exp,ln,cos,tan
1
Exercice 2.:Trouver les points critiques des fonctions suivantes et indiquer si ce sont les arguments de maxima ou minima locaux de la fonction : x f(x) = 58x ,f(x) = 2 x+ 1 3 f(x) =x3x+ 1, f(x) =x+ sinx
2
Exercice 4.:vlaolblaeldansmliniinmtuemrgmimutenuneutmnxaosspeds`ivsuteantcnosnoifseL indiqu´e(pourquoi?).Trouvercesdeuxextremaparlame´thodea`trois´etapes:
2 f(x) = 1xdans [2,1]
cosx f(x) =dans [0,2π] 2 + sinx f(x) =x(1x) dans [0.01,1]
3
Exercice 6.:Trouver le point de la droitey= 2x3 le plus proche de l’origine et calculer cette distance minimale.
Exercice 7.:ndioutol`eblroupe´Vsalreirrierchevrend.Repallcemederudoˆutedanl`emprobrelelse casou`lenclosestcettefoisdispose´enbordurederivi`eresachantquilnapasalorsbesoindelefermer lelongdelarivie`re.
4
Soyez le premier à déposer un commentaire !

17/1000 caractères maximum.