Algorithmique 2: exo d'introduction au coût en moyenne

De Ensiwiki
Aller à : navigation, rechercher
AttentionCette page est utilisée dans l'enseignement d'Algorithmique 2. Vos corrections et vos suggestions d'exercice sont les bienvenues. Mais, merci d'en discuter avant.


Cette page est une introduction aux techniques d'analyse de coût en moyenne par une série de questions "élémentaires". Il est conseillé de travailler sur les réponses données ici, même quand vous avez trouvé la réponse. Il faut traiter les questions dans l'ordre.

type Tab is array(Integer range <>) of Element ;

Dans la suite, on travaille sur un tableau T de type Tab donné ci-dessus. On suppose que le type Element est muni d'un ordre total et que son cardinal noté k est très grand, voire infini dénombrable. Concrètement, on note n la valeur de T'Length et on suppose n \leq k. Pour simplifier la rédaction des analyses, on supposera que T'First=1 (et donc que T'Last vaut n).

Echauffement sur la fonction Max

On considère la fonction Max ci-dessous calculant l'élément maximum de T, sous l'hypothèse que n \geq 1. On cherche à calculer A_n le nombre moyen d'affectations (hors initialisation) de la variable Res dans cet algorithme, en supposant que les tous tableaux possibles de taille n sont équiprobables.

Source de la fonction Max

function Max(T: in Tab) return Element is
   -- requiert T'Length > 0 
   Res: Element := T(T'First) ;
begin
   for I in T'First+1..T'Last loop
      if Res < T(I) then
         Res := T(I) ;
      end if ;
   end loop ;
   return Res ;
end ;

Question: Êtes-vous d'accord avec le raisonnement suivant ?

Soient a et b deux éléments quelconques du tableau. La probabilité que a < b est 1/2. Dans la boucle de la fonction Max, la probabilité de l'affectation de Res est donc 1/2. Il y a n-1 tours de boucle, donc

A_n = \frac{n-1}{2}

Proba que le dernier élément d'une suite soit un maximum strict

On suppose ici n \geq 1. Soit S une suite de n éléments de Element choisie aléatoirement (e.g. de manière équiprobable dans \mathrm{Element}^n). On appelle p_{n,k} la probabilité que le dernier élément de S soit le maximum strict de S (e.g. aucun autre élément de S ne lui est égal).

Question: que vaut p_{3,4} ?

Question: lorsque Element est fini, pouvez-vous encadrer p_{n,k} ?

Sous l'hypothèse n \leq k, montrez que

p_{n,k} = \frac{1}{n} - \epsilon avec \epsilon \in \left[0, \frac{1}{k}\right]

Question: lorsque Element est infini dénombrable, que vaut p_{n,k} ?

Retour sur la fonction Max

Donner une borne asympotique en \Theta de A_n.


Tri à bulles

On considère la fonction BubbleSort ci-dessous qui effectue le tri à bulles du tableau T. On cherche à calculer le nombre moyen d'appels à la procédure auxiliaire Swap en fonction de n.

Source de la procédure BubbleSort

procedure Swap(X,Y: in out Element) is
   Aux: Element := X ;
begin
   X:=Y ;  
   Y:=Aux ;
end ;

procedure BubbleSort(T: in out Tab) is
   Swapped: Boolean ;
   I: Natural := T'Last ;
begin
   loop
      Swapped:=False ;
      for J in T'First..I-1 loop
        if T(J+1) < T(J) then
           Swap(T(J),T(J+1)) ;
           Swapped := True ;
        end if ;
      end loop ;
      exit when not Swapped ;
      I:=I-1 ;
   end loop ;
end ;

QCM sur le tri à bulles

Indiquez pour chacune des analyses ci-dessous si elles sont correctes ou incorrectes:

1. On se restreint d'abord au cas où les éléments de T sont 2 à 2 distincts. Il existe donc une unique permutation qui permet de trier le tableau. On va calculer le nombre moyen B_n d'appels à Swap sous l'hypothèse que chacune des permutations permettant de trier le tableau T est équiprobable.

Si T représente la valeur initiale du tableau (avec translation des indices dans 1..n pour simplifier), alors soit X défini par

X = \left\{ (i,j)~|~ 1 \leq i < j \leq n \,\,\mathrm{et}\,\, T(i) > T(j) \right\}

Trivialement, le nombre d'appels à Swap est exactement card(X).

Donc, B_n correspond à la valeur moyenne de card(X), d'où

B_n = \frac{n(n-1)}{4}.
incorrecte
correcte
L'analyse est correcte mais demande d'être plus justifiée. Tout d'abord, il faut montrer que le nombre d'appels à Swap est bien card(X) qui représente le nombre d'éléments initialement inversés. Il faut remarquer ici que deux éléments initialement inversés vont nécessairement être permutés par l'algo et ils le sont au plus une fois. Par ailleurs, seul les éléments initialement inversés sont permutés.

Ensuite, il faut justifier le calcul de la valeur moyenne de card(X). Considérons i,j fixés avec 1 \leq i < j \leq n. On raisonne par symétrie. Parmi les n! permutations possibles du tableau, il y en a la moitié telle que T(i)< T(j) et l'autre moitié telle que T(i) > T(j). Donc la valeur moyenne de card(X) vaut:
\begin{array}{rl} & 1/2 * card (\{ (i,j)~|~ 1 \leq i < j \leq n \})\\ = & 1/2 * \sum_{j=2}^{n}{j-1}\\ = & 1/2 * n(n-1)/2 \end{array}

2. On cherche maintenant à majorer C_n, le nombre moyen d'appels à Swap en supposant que tous les tableaux possibles de taille n sont équiprobables (avec des éléments dans T pas forcément distincts).

Pour commencer, on remarque que la boucle for interne effectue le calcul de maximum de la tranche T(T'First..I) (en plaçant le maximum dans T(I)). En reprenant l'analyse de Max précédente, on trouve que le nombre moyen d'appels à Swap dans la boucle interne est majoré par A_I=O(\mathrm{ln}\,I) (majoré, car on bénéficie sans doute de l'optimisation du test à Swapped).

On en déduit que

C_n \leq \sum_{i=2}^n A_i

Or,

\sum_{i=2}^n\mathrm{ln}\,i \leq \int_2^{n+1}\mathrm{ln}\,x.dx

En intégrant par partie, on trouve

\int \mathrm{ln}\,x.dx = (x.\mathrm{ln}\,x) - x

On en déduit,

C_n = O(n.\log\,n)
incorrecte
Tout d'abord, ce résultat semble en contradiction avec le résultat obtenu pour B_n: mais, c'est pas vraiment un argument car les hypothèses ne sont pas exactement les mêmes.

Ensuite, le tableau T étant modifié à chaque tour de boucle externe, l'hypothèse de distribution uniforme de la tranche T(1..I) dans l'analyse de Max n'est à priori pas vraie ici. Ceci dit, ce n'est en fait pas un problème, car on peut argumenter que la tranche est mieux triée qu'une tranche aléatoire et que dans ce cas, en supposant qu'elle est aléatoire, on fait bien une surestimation du nombre d'appels à Swap (cf. raisonnement précédent sur card(X)).

Plus fondamentalement, si on peut donc s'inspirer de la méthode utilisée pour Max, le résultat ne s'applique pas tel quel, car dans la recherche du maximum, l'appel à Swap s'effectue quand on ne change pas de maximum alors que la modification de Res s'effectue au changement de maximum.

En dehors de ce dernier problème, le reste des calculs semble correcte :)

Bref, si on surestime correctement le nombre d'appels à Swap via cette méthode, on retombe sur un coût quadratique.
correcte

Votre pointage est 0 / 0


Tri par insertion

On considère la procédure InsertionSort qui fait le tri par insertion du tableau T. Dans cette procédure, on appelle décalage l'exécution de la ligne "T(J):=T(J+1)" (cf. commentaire correspondant dans le code).

Source de la procédure InsertionSort

procedure InsertionSort(T: in out Tab) is
   J: Integer;
   E: Element ;
begin
   for I in reverse T'First..T'Last-1 loop
     -- INVARIANT T(I+1..T'Last) trié.
     E:=T(I) ;
     -- on insère T(I) à sa place dans T(I+1..T'Last) trié.
     J:=I ;
     while J < T'Last and then T(J+1) < E loop
         T(J):=T(J+1) ; -- décalage
         J:=J+1 ;
     end loop ;
     T(J):=E ;
   end loop ;
end ;

Étude nombre de comparaisons sur Element dans InsertionSort

Pour un T donné, soit N_d le nombre de décalages dans la procédure InsertionSort ci-dessus.

Question: Pouvez-vous donner un encadrement du nombre N_c de comparaisons en fonction de N_d et n ?

Nombre moyen de comparaisons sur Element dans InsertionSort

On suppose maintenant que les éléments de T sont 2 à 2 distincts. Soit D_n le nombre moyen de comparaisons sur Element dans InsertionSort sous l'hypothèse que chacune des permutations permettant de trier le tableau T est équiprobable.

Question: Pouvez-vous donner un encadrement exact (e.g. pas une approximation asymptotique) de D_n ?

Indication: Comparez N_d et card(X) introduit dans l'analyse de B_n (cf. BubbleSort)

Permutation aléatoire par "recherche de la collection complète"

Étant donné une constante entière N, on considère ici le problème d'engendrer une permutation de 1..N au hasard de manière à ce que les N! permutations soient équiprobables.

On considère ici l'algorithme de "recherche de la collection complète" (voir code ci-dessous). L'étude de son coût moyen permet de répondre à la question suivante:

Supposons que la chocoterie Wonka place, dans chacune de ses tablettes de chocolat (ici le nombre de tablettes est supposé infini bien sûr), un exemplaire d'une image parmi N possibles. Supposons aussi que dans chaque tablette, chacune des N images a la même probabilité d'apparition (e.g. 1/N). Combien de tablettes de chocolat faut-il acheter en moyenne pour avoir la collection complète des N images (en supposant qu'il est interdit de s'échanger les images en double avec d'autres gens) ?

Implémentation par "recherche de la collection complète"

On représente ici une permutation comme un tableau de Indice dans Indice (dont les éléments sont 2 à 2 distincts). Sous l'hypothèse que Random effectue un tirage uniforme dans Indice, la procédure RandomPermut génère une permutation aléatoire S de manière équiprobable.

subtype Indice is Positive range 1..N ;
type Permut is array(Indice) of Indice ;
   
package My_Random is new Ada.Numerics.Discrete_Random(Indice) ;
use My_Random ;
G : Generator ;
   
procedure RandomPermut(S: out Permut) is
  PasVu: array(Indice) of Boolean := (others => True) ;
begin
  for I in Indice loop
    Tirage: loop
      S(I):=Random(G) ;
      exit Tirage when PasVu(S(I)) ;
    end loop Tirage ;
    PasVu(S(I)) := False ;
  end loop ;
end ;


Analyse

On veut compter le nombre d'appels à Random en fonction de N (en supposant N \geq 2):

  1. Quel est ce nombre dans le meilleur cas ?
  2. Quel est ce nombre dans le pire cas ?
  3. Montrer que ce nombre dans le cas moyen est majoré par N \times (1 + \mathrm{ln}\,N).