Université de La RéunionMardi 12 Juin 2001

DEUG $2^{\grave{e}me}$ Année - Tronc A - MIAS 2 et MASS 2
Examen d'informatique - Session de Juin
Durée : 2 heures - Sans documents.

Répondre uniquement dans les cadres prévus à cet effet

Exercice 1 : Multiplication de deux entiers (4 pts)
On se pose le problème de calculer de manière efficace le produit de deux entiers sans utiliser la multiplication. Pour ce faire, nous allons utiliser deux programmes Pascal différents :

Approche naïve

function fois(m, n : integer) : integer;
begin
   if (n = 0) then fois := 0
   else if (n = 1) then fois := m
   else fois := fois(m, n - 1) + m;
end;

Exercice 1.1 : Calculer la complexité en nombre d'additions de cette fonction.

Approche ``Diviser pour régner''

function produit(m, n : integer) : integer;
var f : integer;
begin
   if (n = 0) then produit := 0
   else if (n = 1) then produit := m
   else
      begin
         f := produit (m, n div 2);
         if ((n mod 2) = 0) then produit := f + f
         else produit := f + f + m
      end;
end;

Afin de calculer la complexité en nombre d'additions $p(n)$ de la fonction produit, nous allons encadrer $p(n)$ par deux suites $\alpha (n)$ et $\beta (n)$ (i.e $\alpha (n) \leq p(n) \leq \beta(n),\; \forall n \in \mathbb{N}$) de la forme $f(n) = f(\lfloor \frac{n}{2} \rfloor) + constante$. Exercice 1.2 : Définir les deux suites $\alpha$ et $\beta$.





Exercice 1.3 : Calculer la complexité de la fonction produit en utilisant $\alpha$ et$\beta$.





Exercice 2 : Le tri rapide (``quicksort'') (4 pts)
Le tri rapide est fondé sur le paradigme ``diviser pour régner'' et a été inventé par C.A.R. Hoare en 1962. Son principe de fonctionnement est le suivant : étant donné un tableau, on choisit un élément noté $x$ dans celui-ci et on répartit les autres éléments en deux sous-ensembles - ceux qui sont inférieurs à $x$ et ceux qui lui sont supérieurs ou égaux. On applique ce même processus à ces deux sous-ensembles, récursivement. Lorsqu'un sous-ensemble a moins de 2 éléments, ce n'est pas la peine de le trier, ce qui arrête la récursion.

Programme Pascal associé :

type tableau = array [1..N] of integer;
procedure Trier(var t : tableau; i, j : integer);
begin
   if (i < j) then
   begin
      Decouper(t, i, j, k); Trier(t, i, k - 1); Trier(t, k + 1, j);
   end;
end;

La procédure Decouper garantit, qu'après exécution, pour le tableau $t[a_i, \ldots, a_{k - 1}, a_k, a_{k + 1}, \ldots, a_j]$, l'élément de rang $k$ vérifie : $max(a_i, \ldots, a_{k - 1}) < a_k \leq min(a_{k + 1}, \ldots, a_j)$. La complexité en temps de Decouper est exactement égale à la taille du tableau t, soit $j-i+1$ pour notre exemple. Les performances du tri rapide dépendent directement de la manière dont le découpage est réalisé.

Le pire ces cas survient, pour le tri rapide, lorsque le découpage produit un sous-tableau de taille 1 et un autre sous-tableau de taille $n - 1$.

Exercice 2.1 : Supposons que ce pire des cas survienne à chaque étape de l'algorithme, déterminer la complexité de la procedure Trier.
NB : On utilisera une relation de récurrence de la forme $c(n) = a.c(n - 1) + f(n)$.

Le meilleur des cas, pour le tri rapide, survient lorsque le découpage produit deux sous-tableaux de tailles identiques et égales à $\frac{n}{2}$.

Exercice 2.2 : Supposons que le meilleur des cas survienne à chaque étape de l'algorithme, déterminer la complexité de la procedure Trier.
NB : On utilisera une relation de récurrence de la forme $c(n)= a.c(\lfloor \frac{n}{2} \rfloor) + b.c(\lceil \frac{n}{2} \rceil) + f(n)$.