\chapterimage{shadok}

\chapter{Complexité}
\Pasc



\section{Premières définitions}

Nous  étudierons  la  complexité   uniquement  en  tant  que  succession
d'opérations élémentaires, ou, plus formellement:

\begin{definition}
Soit un algorithme $A$ et un argument $a$.

La  complexité de  A pour  $a$  est le  nombre de  fois que  l'opération
élémentaire choisie au  préalable est exécutée lors de  l'exécution de A
pour l'argument $a$. On la notera $K_A(a)$.

\end{definition}

Par exemple, pour le calcul d'une factorielle:


\begin{algo}
\FUNC{facto}{%
\pfarg{n}{entier naturel}}{entier naturel}
\BEGIN
\IF{n=0}
\RETURN{1}
\ELSE
\RETURN{n*facto(n-1)}
\ENDIF
\END
\end{algo}


Clairement,           pour           $n          \geqslant           1$,
$K_{\verb+facto+}(n)=1+K_{\verb+facto+}(n-1)$.

On a donc une progression arithmétique. Or $K_{\verb+facto+}(0)=0$ donc,
pour tout entier naturel $n$, $K_{\verb+facto+}(n)=n$.



\begin{definition}
Deux fonctions  $f$ et  $g$ de  $\bbn^*$ dans $\bbr$  ont même  ordre de
grandeur asymptotique si, et seulement si,

\[\exists k\in  \bbr^*_+,\ \exists  k' \in \bbr^*_+,  \ \exists  n_0 \in
\bbn^*,\  \forall n  \in  \bbn^*,\ n>n_0  \Longrightarrow  k \cdot  g(n)
\leqslant f(n) \leqslant k' \cdot g(n) \]

On notera $f=\Theta(g)$ qui se lit \og \textit{f est en grand théta de g}\fg{}.
\end{definition}

Ici, la complexité de \verb+facto+ est en $\Theta(n)$...



On classe souvent les algorithmes selon leur complexité:

\begin{itemize}
\item logarithmique en $\Theta(\log_2(n))$;
\item linéaire en $\Theta(n)$;
\item quasi-linéaire en $\Theta(n\log_2(n))$;
\item quadratique en $\Theta(n^2)$;
\item polynomiale en $\Theta(n^k)$ avec $k\in\bbn^*$;
\item exponentielle en $\Theta(\lambda^n)$ avec $\lambda>1$.
\end{itemize}

Il va être  primordial d'évaluer la complexité d'un  algorithme, même si
c'est  un problème  souvent compliqué  auquel  on ne  peut pas  répondre
précisément  et qui  dépend de  la machine  utilisée (c'est  pourquoi on
utilise des ordres de grandeur).

Par exemple, si on veut  calculer le déterminant d'une matrice de taille
30 à l'aide de la définition:

$$\det A=\displaystyle\sum_{\sigma\in S_{30}}\varepsilon(\sigma)\cdot a_{1
  \sigma(1)}\cdot a_{2 \sigma(2)}\cdots a_{30 \sigma(30)}$$

Il s'agit de la somme de $30!\approx 2,65\cdot 10^{32}$ termes de 25 facteurs. En supposant que
le processeur soit capable de calculer 10 milliards de ces termes par
secondes, cela nous prendra quand même environ huit mille milliards de siècles...


On ne s'intéressera qu'aux opérations arithmétiques basiques et on négligera les
opérations d'écriture ou  de lecture en mémoire (ce  qui se vérifie dans
la pratique). De plus,  il faudra bien parler d'opérations arithmétiques
basiques (par  exemple l'addition de deux  nombres de 10  chiffres ou de
deux nombres de 100 chiffres n'est pas effectuée de la même façon!).

On vérifie aussi expérimentalement que les temps de
calcul de deux machines  sont grosso modo proportionnels, ce coefficient
étant  \og absorbé\fg{} par  les coefficients  du $\Theta$.  Nos calculs
seront donc ainsi indépendants de la machine utilisée.


Enfin,  il  s'avèrera parfois  difficile  de  calculer exactement  cette
complexité dans les méandres  des différents tests. On distinguera alors
une \textit{complexité  dans le pire des cas}  et une \textit{complexité
  moyenne} ou \textit{statistique}.

On s'intéressera  le plus souvent à  la complexité dans le  pire des cas
car elle est la plus simple à  calculer même si elle est le plus souvent
éloignée de la réalité.



\section{Premier exemple: exponentiation}


\subsection{Méthode naïve}

\begin{algo}
\FUNC{puisr1}{%
\pfarg{a,n}{entiers naturels}}{entier naturel}
\BEGIN
\IF{n=0}
\RETURN{1}
\ELSE
\RETURN{a*puis1(a,n-1)}
\ENDIF
\END
\end{algo}


Ici encore, la  complexité est clairement en $\Theta(n)$,  même avec une
méthode itérative:


\begin{algo}
\FUNC{puisi1}{%
\pfarg{a,n}{entiers naturels}}{entier naturel}
\VAR
\DECLVAR{i,r}
\ENDVAR
\BEGIN
\STATE{r \recoit{} 1}
\FOR{i}{1}{n}
\STATE{r \recoit{} a*r}
\ENDFOR
\RETURN{r}
\END
\end{algo}






\subsection{Diviser pour régner}




On va distinguer deux cas, selon la parité de l'exposant, ce qui va nous
permettre de gagner en efficacité. En effet:


$$a^n=
\begin{cases}
  \left(a^{ \frac{n}{2} }\right)^2\ \text{ si } n\text{ est pair}\\
  a \cdot \left(a^{ \frac{n-1}{2} }\right)^2\ \text{ sinon }
\end{cases}
$$



\begin{algo}
\FUNC{puis2}{%
\pfarg{a,n}{entiers naturels}}{entier naturel}
\BEGIN
\IF{n=0}
\RETURN{1}
\ELSE
\IF{n=1}
\RETURN{a}
\ELSE
\IF{n est pair}
\RETURN{puis2(a*a,n/2)}
\ELSE
\RETURN{a*puis2(a*a,(n-1)/2)}
\ENDIF
\ENDIF
\ENDIF
\END
\end{algo}


Par  exemple,   $a^{11}=a\cdot  \left(a^2\right)^5=a  \cdot   a^2  \cdot
\left(\left(a^2\right)^2\right)^2$ ce qui  entraîne 5 multiplications au
lieu de 11.

De  même, vérifiez  que $x^{27}$  se calcule  en ...  multiplications et
$x^{\numprint{1000000000}}$ en 41 multiplications.




Généralisons: soit $K$ la complexité de cet algorithme. On a $K(1)=0$.

Sinon,   le   nombre  de   multiplications   effectuées  pour   calculer
\verb+puis2(a,n)+   est   égal   au   nombre   de   multiplications   de
\verb+puis(a,[n/2])+ auquel  il faut ajouter 1 (pour  \verb+a*a+) si $n$
est pair et 2 (\verb+a*a+ puis \verb+a*puis2+) si $n$ est impair.

Ainsi, $K(1)=0$ et $1+K([n/2]) \leqslant K(n) \leqslant 2+K([n/2])$.

On montre par récurrence que la suite $(u_n)_{n\in\bbn^*}$ définie par
$\begin{cases}
  u_1=0\\
u_n=1+u_{[n/2]}
\end{cases}$

a pour valeur $u_n=\left[\log_2(n)\right]+1$.

De même,  la suite $(v_n)_{n\in\bbn^*}$ définie par
$\begin{cases}
  v_1=0\\
v_n=2+v_{[n/2]}
\end{cases}$

a pour valeur $v_n=2 \cdot\left[\log_2(n)\right]$.

On en déduit que $$\forall n\in\bbn,\ \left[\log_2(n)\right] \leqslant K(n) \leqslant 2\left[\log_2(n)\right]$$

Ainsi,   la    complexité   de    cet   algorithme   est    en   $\Theta
\left(\log_2(n)\right)$ ce  qui est bien plus  efficace que l'algorithme
naïf : on vérifie qu'il faut entre 29 et 58 opérations pour calculer un nombre à la
puissance $\numprint{1000000000}$.


Ce  n'est cependant  pas  toujours l'algorithme  le  plus efficace.  Par
exemple,  il  est  plus  rapide   de  calculer  $a^{27}$  en  faisant  6
multiplications au lieu de 7:

$$a^{27}=\Bigl( \bigl( a^3 \bigr)^3 \Bigr)^3$$


Cependant,  un algorithme  qui tenterait  de déterminer  l'algorithme de
calcul le plus efficace risque d'être beaucoup plus coûteux...


\section{Recherche dans un tableau}


\subsection{Préliminaires}

On veut  rechercher si une valeur se  trouve dans un tableau  donné et à
quel endroit.

On  définit un  type d'éléments  qui constitueront  le tableau,  un type
d'indices et un type de
tableau de  taille fixée à l'avance.  Ces types seront  utilisés tout au
long de la section.


\begin{lstlisting}[caption={}]
CONST 
  ind_max = 100;

TYPE
  element = WORD;
  indice = 1..ind_max;
  tableau = ARRAY[indice] of element;
\end{lstlisting}




\subsection{Recherche séquentielle}


On parcourt les éléments du tableau un par un à partir du premier.


\begin{lstlisting}[caption={}]
PROCEDURE recherche_seq(tab : tableau;
                        debut,fin : indice;
                        valeur_cherchee : element);
VAR ici : indice;
    trouve : boolean;

{-- Si on trouve un element egal a valeur_cherchee alors ici sera egal a
  l'indice de cet element et trouve vaudra TRUE.

Parametres : tab (E) -> tableau dans lequel on effectue la recherche
             debut (E) -> indice de debut de recherche
             fin (E) -> indice de fin de recherche
             valeur_cherchee (E) -> comme son nom l'indique
             ici (S) -> indice de l'element trouve
             trouve (S) -> vrai ou faux selon que la valeur a ete trouvee ou non

Exemple d'appel : recherche_seq(tab,1,10,32) --}

BEGIN
 trouve:=FALSE;
 ici:=debut;
 WHILE ((ici<=fin) AND (not trouve)) DO
   IF (tab[ici]=valeur_cherchee) 
   THEN trouve:=TRUE
   ELSE ici:=ici+1
END;
\end{lstlisting}



Par exemple, on l'utilise dans le programme suivant:

\begin{lstlisting}
PROGRAM rech_seq;

CONST ind_max = 100;

TYPE
   element = WORD;
   indice = 1..ind_max;
   tableau = ARRAY[indice] of element;

VAR n,i,x: WORD;
     Tabi: tableau;
     ici : indice;
     trouve: boolean;

BEGIN
 WRITELN('Entrez la longueur du tableau a trier : ');
 READLN(n);
 WRITELN('Entrez le nombre a chercher : ');
 READLN(x);
 WRITELN('Entrez les elements du tableau : ');
 FOR  i:=1 TO n DO
    READ(Tabi[i]);
 WRITELN;
 recherche_seq(Tabi,1,n,x);
 IF trouve=TRUE THEN
 WRITELN('Le nombre ',x, ' porte le numero ',ici, ' dans le tableau.')
 ELSE WRITELN('Le nombre ',x,' ne se trouve pas dans le tableau.');
 READLN();
 READLN
END.                                  
\end{lstlisting}


et on obtient:

\begin{Verbatim}
Entrez la longueur du tableau a trier : 
4
Entrez le nombre a chercher : 
2
Entrez les elements du tableau : 
11
6
2
987

Le nombre 2 porte le numero 3 dans le tableau.

\end{Verbatim}

\subsection{Recherche dichotomique}


Pour être plus efficace, divisons pour régner.

Supposons  que  nous disposions  d'un  tableau  déjà  trié dans  l'ordre
croissant (cf \vref{sec::tri}).

Considérons un  élément situé  en son milieu  et comparons-le  au nombre
cherché ce qui orientera notre recherche.



\begin{lstlisting}[caption={}]
PROCEDURE recherche_dich(tab : tableau;
                        debut,fin : indice;
                        valeur_cherchee : element);
  VAR haut,bas : indice;
{-- Si on trouve un element egal a valeur_cherchee alors ici sera egal a
  l'indice de cet element et trouve vaudra TRUE.

Parametres : tab (E) -> tableau dans lequel on effectue la recherche
             debut (E) -> indice de debut de recherche
             fin (E) -> indice de fin de recherche
             valeur_cherchee (E) -> comme son nom l'indique
             haut,bas (L) -> indice mobiles des sous-tableaux etudies
             trouve (S) -> vrai ou faux selon que la valeur a ete trouvee ou non

Exemple d'appel : recherche_dich(tab,1,10,32) --}

BEGIN
 trouve:=FALSE;
 compteur:=0;
 haut:=fin;
 bas:=debut;
 milieu:=(haut+bas) DIV 2;
 WHILE ((haut>=bas) AND (not trouve)) DO
  BEGIN
   IF (tab[milieu]=valeur_cherchee)
   THEN trouve:=TRUE
   ELSE IF tab[milieu]>valeur_cherchee
        THEN haut:=milieu-1
        ELSE bas:=milieu+1;
   compteur:=compteur+1;
   milieu:=(bas+haut) DIV 2
  END;
END;                             
\end{lstlisting}


On rajoute  un compteur et on  introduit la procédure  dans le programme
suivant:

\begin{lstlisting}[caption={}]
BEGIN
 WRITELN('Entrez la longueur du tableau a trier : ');
 READLN(n);
 WRITELN('Entrez le nombre a chercher : ');
 READLN(x);
 WRITELN('Entrez les elements du tableau : ');
 FOR  i:=1 TO n DO
    READ(Tabi[i]);
 WRITELN;
 recherche_dich(Tabi,1,n,x);
 IF trouve=TRUE THEN
 WRITELN('Le nombre ',x, ' porte le numero ',milieu, ' dans le tableau.')
 ELSE WRITELN('Le nombre ',x,' ne se trouve pas dans le tableau.');
 WRITELN('En ',compteur,' coups.');
 READLN();
 READLN
END.              
\end{lstlisting}



et on obtient par exemple:

\begin{Verbatim}
Entrez la longueur du tableau a trier : 
40
Entrez le nombre a chercher : 
21
Entrez les elements du tableau : 
0
1
2
3
.
.
.
39

Le nombre 21 porte le numero 22 dans le tableau.
En 4 coups.
\end{Verbatim}


Quelle est  la complexité  au pire de  cet algorithme?  Comparez-la avec
celle de la recherche séquentielle.

\section{Algorithmes de tri\label{sec::tri}}

\subsection{Permutation}

Nous aurons,  tout au  long de cette  section, besoin de  permuter deux
éléments d'un tableau. Nous utiliserons la procédure suivante:


\begin{lstlisting}[caption={}]
PROCEDURE echange(a,b:element);
VAR temp : element;
BEGIN
  temp:=a;
     a:=b;
     b:=temp
END;
\end{lstlisting}



\subsection{Tri par sélection}


C'est une  méthode élémentaire :  elle consiste à déterminer  le minimum
d'un tableau  de nombres, à le placer  en tête du tableau  résultat et à
recommencer sur le tableau initial tronqué.


Commentez le programme suivant:


\begin{lstlisting}[caption={}]
PROGRAM tri_selec2;

 CONST ind_max = 100;

 TYPE
   element = WORD;
   indice = 1..ind_max;
   tableau = ARRAY[indice] of element;

 VAR n,i,compteur: WORD;
     Tabi,tab_trie: tableau;

PROCEDURE  tri_sel(tab:tableau;debut,fin:indice);
VAR i,j,actuel:indice;
    temp:element;
BEGIN
 tab_trie:=tab;
 compteur:=0;
 FOR i:=debut TO fin-1 DO
  BEGIN
   actuel:=i;
     FOR j:=i+1 TO fin DO
       IF tab_trie[j]<tab_trie[actuel]
       THEN  {on echange les valeurs}
         BEGIN
         compteur:=compteur+1;
         temp:=tab_trie[j];
         tab_trie[j]:=tab_trie[actuel];
         tab_trie[actuel]:=temp
         END;
  END;
END;

BEGIN
 WRITELN('Entrez la longueur du tableau a trier : ');
 READLN(n);
 WRITELN('Entrez les elements du tableau : ');
 FOR  i:=1 TO n DO
    READLN(Tabi[i]);
 WRITELN;
 tri_sel(Tabi,1,n);
 FOR  i:=1 TO n DO
    WRITE(tab_trie[i]:5);
 WRITELN;WRITELN;
 WRITE('En ',compteur,' comparaisons.');
 READLN
END.                                              
\end{lstlisting}



La  fonction  \verb+tri_sel+  effectue  $n$ itérations,  la  $i$-eme  en
effectuant $(n-i)$ avec au maximum autant de comparaisons. La complexité au pire, en considérant
comme opération élémentaire  la comparaison de deux entiers,  est donc de
l'ordre  de $\frac{n(n-1)}{2}$  c'est-à-dire  quadratique.



\begin{Verbatim}
Entrez la longueur du tableau a trier : 
10
Entrez les elements du tableau : 
10
9
8
7
6
5
4
3
2
1

    1    2    3    4    5    6    7    8    9   10

En 45 comparaisons.
\end{Verbatim}

\subsection{Tri par insertion}

C'est  l'algorithme  correspondant  à  une personne  triant  des  cartes
qu'elle saisit une par une sur la table.
Nous garderons cette image à l'esprit pour décrire notre algorithme.

Nous  balayons  un  tableau du  début  à  la  fin. Au  moment  d'étudier
la carte n\textdegree \verb+ind_test+, on prend la \verb+ind_test+\up{e}
carte et  on la met à  sa place en  la testant avec les  carte d'indices
inférieurs déjà rangées.

Commentez le programme suivant:

\begin{lstlisting}[caption={}]
PROGRAM tri_inser_it;

 CONST ind_max = 100;

 TYPE
   element = WORD;
   indice = 1..ind_max;
   tableau = ARRAY[indice] of element;

 VAR n,i,compteur: WORD;
     Tab : tableau;

 PROCEDURE  tri_ins_it(VAR tab : tableau; max : indice);
 VAR ind_test, ind_mobil : indice;
     nb_a_inserer : element;
 BEGIN
   FOR ind_test:=2 TO max DO
    BEGIN
      nb_a_inserer:=tab[ind_test];
      ind_mobil:=ind_test-1;
      WHILE (ind_mobil >= 1) AND (tab[ind_mobil] > nb_a_inserer) DO
        BEGIN
          tab[ind_mobil+1]:=tab[ind_mobil];
          ind_mobil:=ind_mobil-1;
          compteur:=compteur+1 
        END;
      tab[ind_mobil+1]:=nb_a_inserer
    END;
 END;

BEGIN
 WRITELN('Entrez la longueur du tableau a trier : ');
 READLN(n);
 WRITELN('Entrez les elements du tableau : ');
 FOR  i:=1 TO n DO
    READLN(Tab[i]);
 tri_ins_it(Tab,n);
 WRITELN;
 FOR  i:=1 TO n DO
    WRITE(Tab[i]:5);
 WRITELN;WRITELN;
 WRITE('En ',compteur,' comparaisons.'); 
 READLN
END.                                                            
\end{lstlisting}



Pour information, voici ce que ça peut donner en récursif avec CAML:

\caml

\begin{lstlisting}
# let rec insere element = function
   | [] -> [element]
   | tete::queue -> if element <= tete
                then element::tete::queue 
                else tete::(insere element queue);;
\end{lstlisting}



\begin{lstlisting}
# let rec tri_insertion = function
   |  [] -> []
   | tete::queue -> insere tete (tri_insertion queue);;
\end{lstlisting}

Par exemple:

\begin{lstlisting}[caption={}]
# tri_insertion([3;5;2;4;88;75;325;11;21]);;
- : int list = [2; 3; 4; 5; 11; 21; 75; 88; 325]
\end{lstlisting}

ou encore:

\begin{lstlisting}[caption={}]
# tri_insertion([1.;sqrt(2.);acos(1.);2.*.acos(0.)]);;
- : float list = [0.; 1.; 1.41421356237309515; 3.14159265358979312]
\end{lstlisting}


Bon, pour  en revenir à  notre procédure \verb+tri_ins_it+,  il faudrait
déterminer sa complexité. 

Nous prendrons  cette fois la copie  d'un élément dans  le tableau comme
opération élémentaire.



Au pire, la  liste est dans l'ordre inverse. On fait  $i-1$ copies pour le
$i$\up{e} élément de la liste. Ainsi,  le nombre total de copies au pire
est:

$$0+1+2+\cdots+n-1=\dfrac{n(n-1)}{2}$$

donc la complexité au pire est quadratique.




\Pasc

\subsection{Tri à bulles}

On parcourt le tableau de nombres  et on transpose tout couple qui n'est
pas dans le bon ordre.

Par exemple, si on veut trier 4-3-2-1, cela donne successivement:

4-3-2-1

3-4-2-1

3-2-4-1

2-3-4-1

2-3-1-4

2-1-3-4

1-2-3-4

Les maxima montent comme des bulles dans un verre d'eau...


\begin{lstlisting}[caption={}]
FUNCTION bulle(tab:tableau; nmax : indice):tableau;
VAR tabf: tableau;
    k : indice;
    temp:WORD;
BEGIN
  tabf:=tab;
  k:=1;
  WHILE k < nmax DO
    BEGIN
      IF tabf[k]>tabf[k+1] THEN
        BEGIN
          temp:=tabf[k];
          tabf[k]:=tabf[k+1];
          tabf[k+1]:=temp;
          k:=1
        END
      ELSE k:=k+1
    END;
  bulle:=tabf;
END;
\end{lstlisting}


On peut également parcourir toute la liste et effectuer les échanges puis
recommencer au début de la liste:


\begin{lstlisting}[caption={}]
FUNCTION bulle(tab:tableau; nmax : indice):tableau;
VAR tabf: tableau;
    k : indice;
    temp:WORD;
    echange:BOOLEAN;
BEGIN
  tabf:=tab;
  REPEAT
   echange:=FALSE;
   FOR k:=1 TO nmax-1 DO
    BEGIN
      IF tabf[k]>tabf[k+1] THEN
        BEGIN
          temp:=tabf[k];
          tabf[k]:=tabf[k+1];
          tabf[k+1]:=temp;
          echange:=TRUE;
        END
    END;
  UNTIL echange=FALSE;
  bulle:=tabf;
END;
\end{lstlisting}


Encore une autre version en partant de la fin:

\begin{lstlisting}[caption={}]
PROGRAM tri_bulle4;

 CONST ind_max = 100;

 TYPE
   element = WORD;
   indice = 1..ind_max;
   tableau = ARRAY[indice] of element;

 VAR n,i,compteur: WORD;
     Tabi,tabf: tableau;

PROCEDURE bulle(tab:tableau; nmin,nmax : indice);
VAR k,j : indice;
    temp:WORD;
BEGIN
  tabf:=tab;
  FOR k:=nmax DOWNTO nmin+1 DO
   FOR j:=nmin TO k-1 DO
    BEGIN
      compteur:=compteur+1;
      IF tabf[j]>tabf[k] THEN
        BEGIN
          temp:=tabf[k];
          tabf[k]:=tabf[j];
          tabf[j]:=temp;
        END
    END;
END;



BEGIN
 WRITELN('Entrez la longueur du tableau a trier : ');
 READLN(n);
 WRITELN('Entrez les elements du tableau : ');
 FOR  i:=1 TO n DO
    READLN(Tabi[i]);
 bulle(Tabi,1,n);
 WRITELN;
 FOR  i:=1 TO n DO
    WRITE(tabf[i]:5);
 WRITELN;WRITELN;
 WRITE('En ',compteur,' comparaisons.');
 READLN
END.    
\end{lstlisting}


\begin{Verbatim}
Entrez la longueur du tableau a trier : 
10
Entrez les elements du tableau : 
10
1
2
3
4
5
6
7
8
9

    1    2    3    4    5    6    7    8    9   10

En 45 comparaisons.
\end{Verbatim}



À chaque itération, on effectue  $n-1$ comparaisons. Dans le pire des cas,
(le plus petit  élément est en dernier), on  effectue $n$ itérations: la
complexité est donc quadratique ici encore.

Dans le meilleur  des cas, la liste est déjà triée  et la complexité est
linéaire car on n'effectue qu'une itération de $n-1$ comparaisons.

\pagebreak

\subsection{Tri fusion}

On utilise la méthode diviser  pour régner: on \og coupe\fg{} le tableau
à trier en deux, on trie chaque tableau et on fusionne les deux tableaux
obtenus, de manière récursive.

Voici une illustration sur un exemple:


%\begin{figure}
\begin{center}
  \includegraphics[scale=0.4]{Mergesort}
\end{center}
%\end{figure}

On suppose qu'un type de variable \verb+TAB+ a été créé. Commentez cette procédure:


\begin{lstlisting}[caption={}]
PROCEDURE Tri_Fusion (tab : TAB; min, max : INTEGER);  
VAR  
   mid, i, j, k, ind_min, ind_max: INTEGER; 
   tab_aux : TAB;  
BEGIN  
     IF max > min THEN  
     BEGIN           
          mid := (min + max) DIV 2;  
          Tri_Fusion (tab, min, mid);  
          Tri_Fusion (tab, mid + 1, max);  
            
     FOR i := mid DOWNTO min DO  
              tab_aux[i] := tab[i];  
            
     FOR j := mid + 1 TO max DO  
              tab_aux[mid + 1 + max - j] := tab_aux[j]; 
            
     ind_bas := min; ind_haut := max;  
          FOR k := min TO max DO 
          BEGIN  
               IF tab_aux[ind_bas] < tab_aux[ind_haut] THEN  
               BEGIN  
                    tab[k] := tab_aux[ind_bas];  
                    ind_bas := ind_bas + 1;  
               END  
               ELSE  
                   BEGIN  
                         tab[k] := tab_aux[ind_haut];  
                         ind_haut := ind_haut - 1;  
                   END;  
          END;  
     END;  
END;  
\end{lstlisting}


Pour étudier la complexité de  cet algorithme, nous allons prendre comme
opération élémentaire la copie d'un élément dans un tableau. Soit $n$ la longueur du
tableau à trier. On effectue  $n$ premières copies pour créer le tableau
auxiliaire  puis   $n$  nouvelles   copies  pour  modifier   le  tableau
initial.  Il  faut  ensuite  ajouter  le  coût de  la  fusion  des  deux
sous-tableaux issus des appels récursifs.

Appelons $K$ la fonction coût associé au tri par fusion, alors:

$$
\begin{cases}
K(0)=K(1)=0\\
K(n)=K    \left(\lceil    \frac{n}{2}   \rceil\right)+K    \left(\lfloor
  \frac{n}{2} \rfloor\right)+2n
\end{cases}
$$

Posons  $u_n=K(n)$.  La  récurrence  définissant la  suite  $(u_n)$  est
compliquée mais, comme pour la dichotomie, nous 
allons l'étudier dans le cas particulier où $n$ est une puissance de 2.
On peut toutefois montrer rapidement par récurrence que la suite $(u_n)$
est croissante.



Posons maintenant $n=2^k$ et $u_n=u_{2^k}=x_k$, alors
$ x_0=0$ et, pour $k\in\bbn^*$, $x_k=2x_{k-1}+2^{k+1}$. On obtient successivement:

$$x_k=2 \left(2x_{k-2}+2^k\right)+2^{k+1}=2 \left(2 \left(2x_{k-3}+2^{k-1}\right)+2^k\right)+2^{k+1}$$
On montre  alors par récurrence  que $$x_k=2^{k}x_0+k\cdot 2^{k+1}=k\cdot
2^{k+1}$$


Or, pour tout entier  $n$ non nul, $$2^{\lfloor \log_2(n)\rfloor} \leqslant
n \leqslant 2^{\lfloor \log_2(n)\rfloor+1}$$ donc

$$
2^{\lfloor \log_2(n)\rfloor+1}\lfloor \log_2(n)\rfloor \leqslant K(n) \leqslant 2^{\lfloor \log_2(n)\rfloor+2}\left(\lfloor \log_2(n)\rfloor+1\right)
$$

c'est-à-dire


$$2n\lfloor \log_2(n)\rfloor \leqslant K(n) \leqslant 4n \left(\lfloor \log_2(n)\rfloor+1\right)$$


Finalement

\begin{center}
  \fbox{$K(n)=\Theta \bigl( n\ln(n) \bigr)$}
\end{center}

Ce résultat ne  dépend pas du tableau à classer  car les opérations sont
effectuées systématiquement:  la complexité du  tri par fusion  est donc
quasi  linéaire  dans tous  les  cas ce  qui  est  une amélioration  par
rapport aux tris précédents.


\subsection{Tri Shell}

\subsection{Tri rapide}





\vfill

\eject


\modeexercice % entre en mode exercice
\section{EXERCICES}


\begin{listeexercices}

  \begin{exercice}
    Écrire une version PASCAL de l'algorithme d'exponentiation rapide en
    récursif puis en itératif.

Prouvez ensuite la terminaison de la version itérative. 
  \end{exercice}





  \begin{exercice}
Calculez  la complexité  de l'algorithme  suivant en  supposant  que les
$\cdots$ représentent des opérations se déroulant indépendamment de $n$:


\begin{algo}
\FUNC{algo}{%
\pfarg{n}{entier positif}}{entier}
\VAR
\DECLVAR{i,k}{}
\ENDVAR
\BEGIN
\STATE{k \recoit{} n}
\WHILE{k>0}
\STATE{...}
\FOR{i}{1}{k}
\STATE{...}
\ENDFOR
\STATE{k \recoit{} k DIV 3}
\ENDWHILE
\STATE{...}
\END 
\end{algo}
\end{exercice}


\begin{exercice}[E3A 2007]
Un tableau d'entiers T est  dit\textit{ trié par ordre croissant} si ses
entrées sont  triées par ordre croissant:  si $\ell$ est  la longueur du
tableau,  $\forall  (i,j)\in  \bigl\{  1,...,\ell \bigr\}^2,\  i  \ie  j
\Longrightarrow  T[i]  \leqslant  T[j]$.  Il est  dit  \textit{trié  par
  ordre   décroissant}   si   ses   entrées  sont   triées   par   ordre
décroissant.  Dans les deux  cas, il  est dit  \textit{trié}. Remarquons
qu'un  tableau T  peut être  à la  fois trié  dans l'ordre  croissant et
décroissant s'il vérifie: si $\ell$ est la longueur du tableau, $\forall  (i,j)\in  \bigl\{  1,...,\ell \bigr\}^2,\  i  \ie  j
\Longrightarrow T[i] = T[j]$. Il est dit alors \textit{constant}.

Écrire la fonction:

\begin{Verbatim}
Test-tri 
   données T : tableau d'entiers
           l : entier
  résultat x : entier
\end{Verbatim}

qui  prend en  entrée un  tableau T  de longueur  $\ell$ et  retourne la
valeur 1 si  le tableau T est trié par ordre  croissant et non constant,
$-1$ si  T est trié par  ordre décroissant et  non constant, 0 si  T est
constant et 2 si T n'est pas trié.

Écrire la procédure:

\begin{Verbatim}
Fusion 
   données T : tableau d'entiers
           l : entier
           U : tableau d'entiers
           m : entier
  résultat W : tableau d'entiers trié
\end{Verbatim}

qui  fusionne  deux  tableaux   triés  tous  deux  par  ordre  croissant
(respectivement  tous deux  triés par  ordre décroissant),  de longueurs
respectives  $\ell$, $m$;  le résultat  est  un tableau  trié par  ordre
croissant (respectivement décroissant) de longueur $\ell+m$. Dans le cas
où les deux tableaux ne sont  pas triés dans un même ordre, la procédure
\verb+Fusion+ renverra un tableau vide et un message d'avertissement.


\end{exercice}


\begin{exercice}[Centrale 2007: Autour de la suite de Fibonacci]


L'objectif de ce problème est de comparer les complexités temporelles (et dans une moindre mesure
 spatiale) d'algorithmes de calcul numérique de suites entières vérifiant une relation de récurrence
linéaire. Les  entiers manipulés  pourront être arbitrairement  long (ce
qui n'est a priori pas le cas ni en Caml ni en Pascal). Dans les calculs
de complexité, on demande des  ordres de grandeur du nombre d'opérations
élémentaires sur les bits. 

\textit{Exemple 1}  : l'algorithme naturel  pour sommer deux  entiers de
$n$  bits demande $O(n)$  opérations élémentaires  (additions bit-à-bit,
propagation de retenue). 


On ne demande pas d'équivalents, mais des majorants asymptotiques.

Lorsque $u_n = O(v_n )$ et $v_n = O(u_n )$, on pourra noter $u_n = \Theta(v_n )$, ce qui est plus précis que $u_n = O(v_n )$.

\textit{Exemple 2} :  le \og tri bulle\fg{} d'un  tableau de $n$ valeurs
effectue $\Theta(n^2 )$ comparaisons de valeurs, et réalise$O(n^2)$ échanges dans le tableau.


Les candidats rédigeant en Caml devront donner le type de chaque fonction écrite.



\textit{Notation} :  $a[b]$ désignera  $a$ modulo $b$,  c'est à  dire le
reste dans la division euclidienne de $a$ par $b$. 



\begin{enumerate}
\item 
\begin{enumerate}
\item  \textbf{Questions préliminaires.}

\item  Évaluer le nombre d'opérations élémentaires sur des bits requises pour effectuer le produit
de deux entiers de $n$ bits avec une méthode élémentaire (que l'on décrira sommairement).


\item Donner un algorithme  effectuant une multiplication d'entiers avec
  une meilleure  complexité. Le décrire, et  donner (sans justification)
  sa complexité temporelle. 
\item   Décrire    très   sommairement   l'algorithme   d'exponentiation
  rapide. Justifier son intérêt par rapport à un algorithme élémentaire.

\end{enumerate}

\item  \textbf{Diverses façons de calculer $\mathbf{f_n}$ }.

La suite de Fibonacci est définie par les relations $f_0 = 0$, $f_1 = 1$, et pour tout $n \in \bbn$ :

$$f_{n+2} = f_n + f_{n+1}$$


\begin{enumerate}
\item En utilisant les résultats  standards sur les suites vérifiant une
  relation de  récurrence linéaire d'ordre 2,  à coefficients constants,
  donner  la   valeur  de  $f_n$  ,   et  l'ordre  de   grandeur  de  sa
  représentation binaire  (écriture en base  2). En déduire  un minorant
  pour le temps de calcul de tout programme calculant $f_n$.

\item  Écrire une fonction récursive \verb+fibo+ prenant en entrée un entier $n$ et retournant $f_n$ en
 appliquant directement la définition de $f$.

\item  Prouver que le nombre d'appels récursifs effectués pour calculer $f_n$ avec la fonction
précédente est exponentiel en $n$.

\item Écrire  une nouvelle fonction \verb+fibo2+ réalisant  le calcul de
  $f_n$ de façon  itérative, en calculant de proche  en proche les $f_k$
  pour  $k \leqslant  n$.  Donner le  nombre  d'additions d'entiers  qui
  seront effectuées lors du calcul de $f_n$, et évaluer la dépendance du
  temps  de calcul  par rapport  à $n$,  ainsi que  la place  en mémoire
  requise (on  supposera que les entiers calculés  restent inférieurs au
  plus grand entier représentable en Caml ou en Pascal). 


\item On observe qu'en notant $X_n=\begin{pmatrix} f_n\\ f_{n+1}
  \end{pmatrix}$ et $A=
  \begin{pmatrix}
    0&1\\1&1
  \end{pmatrix}
$, on a $X_{n+1}=AX_n$  pour tout $n\in\bbn$, puis $X_n=A^nX_0$. Estimer
le temps de calcul et la place en mémoire requise pour calculer $f_n$ en
exploitant cette relation.
  
\item Si on cherche à calculer $f_n$ modulo un entier $k$ \og petit\fg{}
  (dans  un sens  à préciser  par le  candidat), quelle  méthode peut-on
  utiliser, et quels sont le temps et l'espace requis pas cette méthode?

\end{enumerate}
\end{enumerate}
\end{exercice}





\begin{exercice}[École de l'Air]

On  dispose  d'une pile  de  rondelles  de  diamètres variés,  que  l'on
souhaite ranger  par ordre  décroissant de taille,  la plus  large devant
être en  bas de la pile.  Malheureusement, on ne peut  manipuler la pile
que  \og par  morceaux\fg{}:  la seule  opération  autorisée consiste  à
prendre  la partie  de la  pile surmontant  une certaine  rondelle  et à
retourner d'un bloc tout le paquet.

Par exemple, si une pile contient  des rondelles de diamètres 7, 10, 20,
2 et 5 et que l'on retourne le bloc commençant à la rondelle de diamètre
20, on obtient la pile de diamètres successifs 7, 10, 5, 2 et 20.

\medskip

Nous modéliserons  la pile  de rondelles par  un tableau  $d$ d'entiers,
indicé de 0 à  $n-1$, où $n$ est le nombre de  rondelles, la case numéro
$i$ contenant  le diamètre  en millimètres de  la rondelle $i$.  La case
numéro 0 correspond au bas de la pile.

Nous supposerons la constante $n$ définie.

En Pascal, $d$ est de type \verb+Pile+ défini par:

\centering \verb+Pile = ARRAY[0..n-1] OF INTEGER+

\begin{enumerate}
\item Écrire une procédure 

\verb+retourne(VAR d:Pile  ; i:INTEGER)+

  telle que  \verb+retourne(d,i)+ modifie  le tableau \verb+d+  pour \og
  retourner  \fg{}  la partie  supérieure  de la  pile  à  partir de  la
  rondelle d'indice $i$ (incluse).

\item Quel  est, en nombre d'affectations  dans \verb+d+, le  coût de ce
  retournement?

\item Comment  faire pour mettre en bas  de la pile la  rondelle la plus
  large?

\item Écrire une procédure 

\verb+place(  VAR d:Pile ; i:INTEGER)+


  telle que  \verb+place(d,i)+ modifie  le tableau \verb+d+  pour mettre
  l'indice  $i$ la  rondelle  la plus  large  de la  partie  de la  pile
  surmontant la rondelle d'indice $i$ (incluse);

\item En déduire une fonction ou une procédure qui trie \verb+d+.

\item  Quel  est  le  coût  au  pire de  cette  méthode,  en  nombre  de
  retournements d'un morceau de pile?
\end{enumerate}

\end{exercice}

















\end{listeexercices}


\vfill

\eject
\section{DES SOLUTIONS}


\begin{listeexercices}

\pasc

\setcounter{exercice}{2}

\begin{exercice}[E3A 2007]

  \begin{lstlisting}[caption={}]
    PROGRAM e3a2007;

 CONST ind_max = 100;

 TYPE
   element = SHORTINT;
   indice = 1..ind_max;
   tableau = ARRAY[indice] of element;

 VAR n,i: WORD;
     Tabi: tableau;


FUNCTION  test_tri(T:tableau;l:WORD):SHORTINT;
VAR k,j:indice;
    delta:element;
BEGIN
 k:=1;
 WHILE ((T[k+1]=T[k]) AND (k<=l-2)) DO k:=k+1;
 IF ((k=l-1) AND (T[k+1]=T[k])) THEN test_tri:=0
 ELSE BEGIN
  j:=k;
  delta:=(T[j+1]-T[j]);
  WHILE ((delta*(T[j+1]-T[j])>=0) AND (j<=l-2)) DO j:=j+1;
  IF ((j=l-1) AND (delta*(T[j+1]-T[j])>=0)) THEN BEGIN
   IF delta>0 THEN test_tri:=1
   ELSE test_tri:=-1
  END
  ELSE test_tri:=2
 END;

END;


{--Traitement de la procedure par Pascal--}

BEGIN
 WRITELN('Entrez la longueur du tableau a tester : ');
 READLN(n);
 WRITELN('Entrez les elements du tableau : ');
 FOR  i:=1 TO n DO
    READLN(Tabi[i]);
 WRITELN;
 WRITE(test_tri(Tabi,n));
 READLN
END.                                                          
  \end{lstlisting}

{\small
\begin{Verbatim}
Entrez la longueur du tableau a tester : 
3
Entrez les elements du tableau : 
8
8
9

1
\end{Verbatim}
}


Voici une version pour la question 2 sans le test de croissance par gain
de place (rajouter un IF test\_tri(T)=1 AND test\_tri(U)=1):


\begin{lstlisting}[caption={}]
PROGRAM e3a2007_2;

 CONST ind_max = 100;

 TYPE
   element = LONGINT;
   indice = 1..ind_max;
   tableau = ARRAY[indice] of element;

 VAR n1,n2,i: WORD;
     W,Tab1,Tab2: tableau;


PROCEDURE  Fusion(T,U:tableau;l,m:WORD);
VAR kmin,kmax,k:indice;
    lmin,lmax,j:WORD;
    Tmin,Tmax:tableau;
BEGIN
 k:=1;
 kmin:=1;
 kmax:=1;
 {--Recherche de l element maxi--}
 IF T[l]<=U[m] THEN
   BEGIN
    lmin:=l; Tmin:=T; lmax:=m; Tmax:=U
   END
 ELSE
   BEGIN
    lmin:=m; Tmin:=U; lmax:=l; Tmax:=T
   END;
 {--tri des deux tableaux--}
 WHILE kmin<=lmin DO
   BEGIN
    IF Tmin[kmin]<=Tmax[kmax] THEN
      BEGIN
       W[k]:=Tmin[kmin]; k:=k+1; kmin:=kmin+1
      END
    ELSE
      BEGIN
       W[k]:=Tmax[kmax]; k:=k+1; kmax:=kmax+1
      END
   END;
 {--Rajout des derniers elements du tableau contenant le max--}
 FOR j:=0 TO (lmax-kmax) DO W[k+j]:=Tmax[kmax+j]
END;

{--Traitement de la procedure par Pascal--}

BEGIN
 WRITELN('Entrez la longueur du premier tableau a fusionner : ');
 READLN(n1);
 WRITELN('Entrez les elements du premier tableau : ');
 FOR  i:=1 TO n1 DO
    READLN(Tab1[i]);
 WRITELN;
 WRITELN('Entrez la longueur du deuxieme tableau a fusionner : ');
 READLN(n2);
 WRITELN('Entrez les elements du deuxieme tableau : ');
 FOR  i:=1 TO n2 DO
    READLN(Tab2[i]);
 WRITELN;
 Fusion(Tab1,Tab2,n1,n2);
 FOR  i:=1 TO n1+n2-1 DO
 WRITE(W[i],' , ');
 WRITE(W[n1+n2]);
 READLN
END.                                                   
\end{lstlisting}


Par exemple:
{\small
\begin{Verbatim}
Entrez la longueur du premier tableau
a fusionner : 
5
Entrez les elements du premier tableau : 

3
66
77
1000

Entrez la longueur du deuxieme tableau 
a fusionner : 
8
Entrez les elements du deuxieme tableau : 
-2
0
1
2
4
5
888
999

-2,0,0,1,2,3,4,5,66,77,888,999,1000
\end{Verbatim}
}

\end{exercice}


\setcounter{exercice}{4}

\begin{exercice}[École de l'Air]
  \begin{enumerate}
  \item Faisons un petit tableau pour comprendre:

{\tiny
\begin{center}
             \begin{tabularx}{\linewidth}{Y{6}}
$n-1$ & $n-1-1$ & $n-1-2$ & $\cdots$  & $n-1-(n-i-2)$
&$n-1-(n-i-1)$\\
\hline
$i$ & $i+1$ & $i+2$ & $\cdots$ & $i+(n-i-2)$ & $i+(n-i-1)$
                    \end{tabularx}
             \end{center}
}


On comprend donc que \verb|d[i+k]| doit devenir \verb+d[n-1-k]+.


\begin{lstlisting}[caption={}]
FUNCTION retourne(d:Pile ; i:INTEGER):Pile;
VAR dd:Pile;
     k:INTEGER;
BEGIN
 dd:=d;
 FOR k:=0 TO n-i-1 DO dd[i+k]:=d[n-1-k]
 retourne:=dd
END;
\end{lstlisting}

\item  Il y  a eu  une affectation  pour créer  \verb+dd+ que  l'on peut
  négliger puis $n-i$ pour les
  échanges.

\item  On commence  par créer  une  fonction qui  trouve le  rang de  la
  rondelle de taille maximum.


  \begin{lstlisting}[caption={}]
FUNCTION ind_maxi(d:Pile ; i:INTEGER):INTEGER;
VAR ind_max,j:INTEGER;
BEGIN
  ind_max:=i;
  FOR j:=i+1 TO n-1 DO
    IF d[j]>d[ind_max] THEN ind_max:=j
  ind_maxi:=ind_max
END; 
  \end{lstlisting}

puis on retourne la pile à partir de \verb+ind_maxi+ pour mettre la plus
grosse rondelle en dernieravec \verb+retourne(d,ind_max)+ puis on retourne totalement la pile pour
mettre la plus grosse rondelle en premier avec \verb+retourne(d,0)+.

\item On utilise la même idée que précédemment:

  \begin{lstlisting}[caption={}]
PROCEDURE place(VAR d:Pile ; i:INTEGER);
VAR ind_max:INTEGER;

BEGIN
  ind_max:=ind_maxi(d,i);
  retourne(d,ind_max);
  retourne(d,i);
END;
  \end{lstlisting}


\item On utilise successivement la procédure \verb+place+ de bas en haut
  pour placer dans l'ordre décroissant les rondelles:

  \begin{lstlisting}[caption={}]
PROCEDURE tri(d:Pile);
VAR i:INTEGER;
BEGIN
  FOR i:=0 TO n-2 DO 
    place(d,i);
END;
  \end{lstlisting}


\item La  question posée est  sans intérêt: chaque appel  à \verb+place+
  effectue deux retournements et il y a $n-1$ appels à place donc il y a
  $2(n-1)$ retournements.

\medskip

 La   procédure  \verb+place(d,i)+  appelle   trois
  procédures qui effectuent des affectations:

  \begin{itemize}
 \item \verb+ind_maxi+ qui effectue au pire \verb+n-i+ affectations;
  \item \verb+retourne(d,ind_maxi)+  qui effectue \verb+n-ind_maxi+ donc
    au pire \verb+n-i+ affectations;
  \item \verb+retourne(d,i)+ qui effectue \verb+n-i+ affectations.
  \end{itemize}

Donc   au  pire,  il   y  aura   $  \displaystyle\sum_{i=0}^{n-1}3(n-i)$
retournements  c'est-à-dire $\frac{3}{2}n(n+1)$:  la complexité  au pire
est quadratique en nombre d'affectations.

  \end{enumerate}
\end{exercice}


\end{listeexercices}


\Pasc
\modenormal % restaure les définitions de sections, sous-sections, etc;



%%% Local Variables: 
%%% TeX-master: "PolyInfo10"
%%% End: 
