Algorithmique Avancée -- Contrôle Terminal

Exercice 1 (8 pts)

Exercice 2 (12 pts.)

Recherche du k-ième plus petit élément d'un tableau A non trié de n éléments indexés de 1 à n.

2.1

Écrivez un algorithme Pivoter(A, inf, sup) qui ré-ordonne les éléments du sous-tableau A[inf..sup] autour du pivot A[inf] : tous les éléments plus petits que le pivot se retrouvent à sa gauche, et tous les éléments plus grands à sa droite. Cet algorithme doit renvoyer la position finale du pivot. Il ne doit pas utiliser de tableau annexe.
Solutions

Simple, surtout pour ceux qui ont vu l'algorithme Tri Rapide (Quicksort) et se rappellent comment ça marche. 1).

Un de ses ingrédients (le principal?) est la fonction suivante vue l'année dernière :

Procédure Pivot (A[p..r])
  x <- A[p]; i <- p; j <- r;
  tant que i < j faire
      tant que A[j] > x faire j <- j - 1;
      tant que A[i] =< x faire i <- i + 1;
      échanger A[i], A[j];
  renvoyer j;
 

Il y a bien d'autres manières de faire la même chose, dont certaines équivalentes en complexité de calcul mais pas forcément en effets de bord (ils ne laissent pas tous les éléments du tableau aux mêmes positions).

Il est aussi possible de réaliser le travail plus bêtement. Par exemple :

Procédure PivotCher (A[p..r])
   x <- A[p]; i <- p 
   pour k de i+1 à j faire
     si A[k] < x alors
       t <- A[k]
       pour r de k à i par pas de -1
           A[r] <- A[r-1]
       fin pour
           A[i] <- t
     fin si
  fin pour
  

Que fait cet algorithme?

  1. Il stock le pivot, A[p], dans x
  2. Il parcourt le tableau de gauche à droite et
    1. s'il trouve un élément plus petit que x,
      1. il le sort du tableau
      2. il décale d'une position à droite tous les éléments du pivot (pivot compris) jusqu'à l'emplacement de l'élément trouvé
      3. il met l'élément dans la position jusqu'alors occupée par le pivot, et
      4. il ajuste le pointeur du pivot (+1)

Il fait beaucoup de décalage inutiles : inutiles car le tableau n'est pas trié! Il suffit de répartir les éléments de part et d'autre.

Une variante de l'algorithme donnée en premier, basé sur les remarques d'un camarade de classe, est la suivante :

 Procédure Pivot (A[p..r])
   x <- A[p]; i <- p; j <- r
   tant que i < j faire
     si A[i]>A[i+1] faire
         échanger A[i] et A[i+1]
         i <- i+1
     sinon
         échanger A[i+1] et A[j]
         j <- j - 1
     fin si
  fin tant que
  renvoyer i

Cet algorithme se résume ainsi :

  • si le pivot rencontre plus petit que lui, il le dépasse (et ajuste son adresse)
  • s'il rencontre plus grand, il l'envoie dans le tas “plus grand et vu” et avance un pas-encore-vu, tant qu'il y en a.
L'important est que les premier et dernier algorithmes ne font pas plus de n=r-p échanges (réaffectations de position) tandis que PivotCher déplace beaucoup plus d'éléments (si A[p] est le maximum de A[p..r], par exemple, mais pas seulement dans ce cas). PivotCher a une complexité qui peut être, dans certains cas, proportionnelle à n2 et non seulement à n

2.2 Quelle est la complexité de cet algorithme?

Comme nous avons vu, l'algorithme (mais pas PivotCher) parcourt le tableau une fois, et ne fait que un test et un changement de pointeur à chaque pas. Sa complexité est donc O(n).

2.3 Diviser pour Régner

Ecrivez un algorithme de type diviser pour régner qui cherche le k-ième plus petit élément d'un tableau A. Précisez l'appel initial.

Muni de Pivot (A[p..q]) une solution serait

Cherche (A[p..q],k)
  si k>(q-p+1) renvoyer erreur
  l <- Pivot(A[p..q])
  si l = k renvoyer A[l]
  sinon
      si l < k renvoyer Cherche(A[l+1..q],k-l)
      sinon renvoyer Cherche(A[p..l-1],k)
      fin si
  fin si

L'appel initial est Cherche(A[1..n],k).

Pivot(A[p..q]) retourne l, la position de l'élément qui est plus grand que l-1 éléments (à sa gauche) et plus petit (ou égal à) tous les autres, à sa droite. Si k = l, le k-ième plus petit est trouvé. Sinon, de deux choses l'une :

  • soit l est plus grand que k est le k-ième plus petit figure parmi les l-1 plus petits que A[l], donc on appelle Cherche(A[p..l-1], k)
  • soit l est plus petit que k, il faut donc chercher le (k-l)-ième plus petit parmi les plus grands que A[l] qui sont A[l+1..q] : on appelle Cherche(A[l+1..q], k-l).

2.4 Quelle récurrence définit la complexité de cet algorithme?

Chaque appel récursif fait appel à Pivot(A[i..j]), O(n=j-i), et autrement ne fait qu'un test ou deux, et un seul appel récursif au plus. Dans le schéma “a*f(n/b)”, a=1, mais b peut être proche de 1 : il se peut qu'on divise très peu à chaque appel.

2.5 Quelle est la complexité au pire?

Dans quelle situation cette complexité est-elle atteinte?

Au pire, on réduit la taille du sous-tableau de seulement un élément à chaque appel, et ce tant qu'on peut sans diminuer k' : c'est le cas où les éléments était triés par ordre décroissant initialement. On appellera

  1. Cherche(A[p..q], k) qui renverra q
  2. Cherche(A[p..q-1], k) qui renverra q-1
  3. etc.

Soit n-1 appels récursifs avec coûts dégressifs n-2, n-3, … \sum_{i=1}^{n-1} (i-1) \approx \frac{n^2 - n}{2} \rightarrow O\left(n^2\right)

2.6 Quelle est la complexité en moyenne?

Justifiez votre réponse.
1) Je suis dans le premier cas mais, hélas, pas le deuxième
 
m1ilc/algoplus_ct.txt · Dernière modification: 2010/05/19 07:50 par suitable
 
Sauf mention contraire, le contenu de ce wiki est placé sous la licence suivante :CC Attribution-Noncommercial-Share Alike 3.0 Unported
Recent changes RSS feed Donate Powered by PHP Valid XHTML 1.0 Valid CSS Driven by DokuWiki