Cet ouvrage fait partie de la bibliothèque YouScribe
Obtenez un accès à la bibliothèque pour le lire en ligne
En savoir plus

Algorithmique Exercice Max

4 pages
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 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
Un pour Un
Permettre à tous d'accéder à la lecture
Pour chaque accès à la bibliothèque, YouScribe donne un accès à une personne dans le besoin