Algorithmique Exercice Max

Description

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

Informations

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

Extrait

NOM : PRENOM :

Date : Groupe :

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

. .

Onre´pondraauxquestionspos´eesaussiclairementquepossibledanslesespacespr´evus etonremettracettefeuilledere´ponsesenfindeTP`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

1