Algorithmique Exercice Max

pages

Français

Documents

Lire un extrait

Obtenez un accès à la bibliothèque pour le consulter en ligne En savoir plus

Découvre YouScribe et accède à tout notre catalogue !

Je m'inscris

Découvre YouScribe et accède à tout notre catalogue !

Je m'inscris

pages

Français

Documents

Lire un extrait

Obtenez un accès à la bibliothèque pour le consulter en ligne En savoir plus

Publié par

pefav

Nombre de lectures

Langue

Français

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

Voir

Publié par

pefav

Langue

Français

NOM : PRENOM :

Date : Groupe :

Analyse:Feuilleder´eponsesduTP2 Extrema et bornes d’une fonction

. .

Onre´pondraauxquestionspos´eesaussiclairementquepossibledanslesespacespr´evus etonremettracettefeuilledere´ponsesenﬁndeTP`al’enseignantcharge´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

Voir