• Algorithmes avec des vecteurs

    Rappel : on appelle vecteur un tableau en une dimension.

    1.Recherche séquentielle d’un élément

    Prenons par exemple un tableau d’entiers.

    On déclare le type vec_t suivant :

    CONST VMax = 1000;
     TYPE vec_t = array [1..VMax] of integer;

    Soit v un vec_t de vn éléments (1 ≤ vn ≤ VMax).
    On veut écrire une fonction booléenne qui dit si un entier x se trouve dans le tableau v.

    Dans un vecteur non trié

    On parcourt le tableau et on s’arrête dès que x est trouvé ou que la fin du tableau est atteinte.

    Première implémentation

    FUNCTION cherche1 (v : vec_t; vn, x : integer) : boolean;
    VAR i : integer;
    BEGIN
       i := 1;
       while (i <= vn) and (v[i] <> x) do
          i := i+1;
          cherche1 := i <= vn;
    END;

    On sort du while dans deux situations :
    – Si i > vn, on a parcouru tout le tableau sans trouver x.

    – Sinon i <= vnet v[i] = x: on a trouvé x.

    On ne peut donc pas écrire comme résultat cherche1 := v[i] = x puisque i peut sortir du tableau; c’est pourquoi on écrit cherche1 := i <= vn.

    Il y a un problème : dans le while, l’expression (i <= vn) and (v[i] <> x) est toujours complétement évaluée, même si le premier terme est faux.

    En effet, le and ne signifie pas « et sinon ».
    La conséquence est que si x n’est pas dans v, à la dernière itération on évaluera (vn+1 <= vn) and (v[vn+1] <> x) et on sortira du vecteur ! !

    → Implémentation à éviter absolument. :/

    Deuxième implémentation avec un booléen

    On va décomposer le test dans le while.

     

    FUNCTION cherche2 (v : vec_t; vn, x : integer) : boolean;
    VAR i : integer;
        continuer : boolean; 
    BEGIN
         i := 1;
     continuer := true;
      while continuer do
             if i > vn then
    continuer := false 
     else if v[i] = x then
                continuer := false
    else i := i+1; 
    cherche2 := i <= vn;
    END;

     

    Troisième implémentation

     

    FUNCTION cherche3 (v : vec_t; vn, x : integer) : boolean; 
    VAR i : integer;
    BEGIN
         i := 1;
     while (i<vn) and (v[i]<>x) do {i<n strictement}
    i := i+1;
         cherche3 := v[i] = x;
    END;

     

    On sort toujours du while avec i <= vn, donc on ne sort jamais du tableau. Par contre pour le résultat, il faut changer le test,

    et on a le droit d’écrire cherche3 := v[i] = x.

    Le coût  Le vecteur v étant non trié, il faut

    vn itérations si x n’appartient pas à  v.
    vn/2 itérations en moyenne si x appartient à v.

     

    Dans un vecteur trié

    Lorsqu’on parle de vecteur trié, on suppose toujours que les vecteurs sont triés par ordre croissant : ∀i, v[i] ≤ v[i + 1].

    On parcourt le tableau et on s’arrête dès que :
    x est trouvé
    – ou la fin du tableau est atteinte
    – ou v[i] > x : ça veut dire que tous les éléments qui suivent seront plus grands que x, inutile de continuer.
    On peut adapter facilement la méthode 3 :

    
    
    FUNCTION cherche4 (v : vec_t; vn, x : integer) : boolean; 
    VAR i : integer;
    BEGIN
        i := 1;
        while (i<vn) and (v[i]<x) do {v[i]<x strictement} 
          i := i+1;
        cherche4 := v[i] = x;  
    END;

     

    Le coût Le vecteur v étant trié, il faut en moyenne vn/2 itérations, que xappartienne ou non à v .

     

    2.La dichotomie

    Prenons l’exemple du correcteur orthographique dans un traitement de texte, utilisé pour corriger une lettre.

    Le dictionnaire du correcteur contient tous les mots de la langue, orthographiés de toutes les façons possibles, soit par exemple  1 million d’entrées.

    Avec la recherche séquentielle sur un dictionnaire trié, il faudra donc en moyenne 500 000 itérations pour trouver un mot !

    Mettons que le texte à corriger fasse 2000 mots. Il faudra donc 2000 × 500 000 = 1 milliard d’itérations pour corriger le texte !

    Sachant qu’en plus, la comparaison de deux mots est nettement plus lente que la comparaison de 2 entiers, la correction va durer plusieurs jours !! (Heureusement que je fais pas ce métier :p )

    Pour accélérer les choses, on va s’inspirer du jeu des 1000 dinars.

    Le jeu des 1000 dinars

    Jeu1 L’ordinateur choisit un prix secret entre 1 et 1000 dt, et le joueur doit le deviner en un nombre minimum de coups.

     

    PROCEDURE jeu1 (secret : integer); 
    VAR n, essai : integer; 
        continuer : boolean; 
    
    BEGIN
      continuer := true; n := 1; 
      while continuer do
        begin
          write (’Essai ’, n, ’ : ’); 
         readln (essai); 
            if essai < secret then 
                writeln (’+’)
            else if essai > secret then
                writeln (’-’) 
            else 
               begin
                 writeln (’Gagné en ’, n, ’ coups’);
                 continuer := false;
               end;
             n := n+1; 
         end;
    END;

     

    Ce qui nous intéresse c’est la stratégie du joueur : admettons que secret = 326.

    Screen Shot 2016-01-18 at 8.55.57 AM

    La solution est trouvée en seulement 9 coups !

    C’est le principe de la dichotomie: on a un intervalle de possibilités, et à chaque itération on réduit de moitié la taille de cet intervalle.

    De la sorte, le nombre maximum d’itération est log2vn, c’est à dire 10 pour vn = 1000, de 20 pour vn = 1 million.(On rentre pas trop dans les détails ^^)

    Jeu2 La réciproque : l’utilisateur choisit un prix secret entre 1 et 1000 dt, et l’ordinateur doit le deviner en un nombre minimum de coups.

    Le programme va donc gérer un intervalle de possibilités, c’est-à-dire un début et une fin, proposer le milieu de l’intervalle, puis changer l’intervalle en fonction de la réponse.

    La recherche dichotomique consiste à faire la même chose sur les indices, et est donc très performante: sur l’exemple du correcteur orthographique, il faudra 20 itérations pour trouver un mot, donc 40 000 itérations pour corriger tout le texte, ce qui est quasiment instantanné.

    Recherche dichotomique

    La dichotomie se fait toujours sur un vecteur trié.

    Cela consiste à considérer une certaine plage de recherche inf..sup sur le vecteur, plage que l’on réduit d’un facteur 2 à chaque itération.

    Au départ, la plage de recherche est tout le vecteur.

    À une itération donnée, on a une plage [inf..sup] et son milieu est m := (inf + sup) div 2.

    On a donc la subdivision : [inf..m-1], [m], [m+1..sup].

    –Soit v[m] = x et on a fini.
    – Soit v[m] < x, donc x n’appartient pas à [inf..m] et la nouvelle plage sera [m+1..sup].

    – Soit v[m] > x, donc x appartient à [m..sup] et la nouvelle plage sera [inf..m-1].

    On implémente l’algorithme avec un booléen trouve.

     

    FUNCTION cherche5 (v : vec_t; vn, x : integer) : boolean; 
    VAR inf, sup, m : integer;
        trouve : boolean; 
    
    BEGIN
        trouve := false;
        inf := 1; sup := vn;
    
        while (inf <= sup) and not trouve do
        begin
           m := (inf + sup) div 2;
           if v[m] = x then 
           trouve:= true
           else if v[m] < x then
                 inf := m+1;
           else sup := m-1;

    end;

        cherche5 := trouve; 
    END;

     

    Remarque Le fait de prendre m-1 ou m+1 n’est pas une simple optimisation, mais est essentiel pour que l’algorithme se termine.
    On peut am ́eliorer l’efficacit ́e dans le cas ou` x ̸∈ v :

     

    BEGIN
        trouve := false;
        if (v[1] <= x) and (x <= v[vn]) then 
        begin
           inf := 1; sup := vn;
          while {...}
        end;
        cherche6 := trouve; 
    END;

    3.Tri d’un vecteur

    Soit v[1..vn] un vecteur non trié. Nous voulons construire un vecteur w[1..vn] qui contienne les même éléments que v, et qui soit trié.

    Il existe de très nombreuses méthodes de tris, qui sont plus ou moins faciles à implémenter, et dont certaines sont nettement plus efficaces que d’autres.

    Dans certaines méthodes on peut se passer du second vecteur w, en travaillant directement sur v où seront permutés des éléments.

    Tri par remplacement

    La méthode consiste à sélectionner des minimums successifs dans v, et à les ranger au fur et à mesure dans w.

    Au départ on recherche quel est le max.

    À chaque pas :

    ◃ on cherche min(v)
    ◃ on le met au bout de w
    ◃ on le remplace dans v par max(v)

    Exemple Trier dans l’ordre alphabétique les lettres du mot ’ETABLES’.

    Le max est la lettre ’T’.

    Screen Shot 2016-01-18 at 9.16.18 AM

    FUNCTION maximum (v : vec_t; vn : integer) : char;
    VAR i : integer; m : char;
    BEGIN
       m := v[1];
       for i := 2 to vn do
            if v[i] > m then 
                m := v[i];
        maximum := m;
    END;
    
    FUNCTION ind_min (v : vec_t; vn : integer) : integer;
    VAR i, j : integer;
    BEGIN
        j := 1;
        for i := 2 to vn do
          if v[i] < v[j] then 
                 j := i;
         ind_min := j;
    END;
    
    

    PROCEDURE tri_remplacement ( v : vec_t; vn : integer; VAR w : vec_t);

    VAR max : char;

    i, j : integer;

    BEGIN
     { recherche du max } 
      max := maximum (v,vn);
    { pas à pas }
     for i := 1 to vn-1 do 
      begin
       j := ind_min (v,vn);
       w[i] := v[j];
       v[j] := max;
      end;
    { on met le max dans la dernière case }
      w[vn] := max;
    END;
    
    
    

    Tri par permutation

    Dans la méthode précédente, la place occupée est double; on peut éviter de créer un nouveau vecteur en travaillant directement sur v.

    Principe On est à l’étape i.
    ◃ Supposons déjà trié v[1..i-1], et non traité v[i..vn].

    ◃ On cherche le min dans v[i..vn]
    ◃ On le permute avec v[i].
    ◃ Maintenant v[1..i] est trié.

    Exemple Trier les lettres du mot ’ETABLES’.

    Screen Shot 2016-01-18 at 9.30.00 AM

    Le coût
    Les performances sont meilleures que le tri par remplacement : il y a environ (vn^2) / 2 comparaisons, et vn / 2 permutations en moyenne.
    Par exemple si vn = 1000, on aura 500 000 comparaisons et 1500 affectations.

     Tri à bulles

    C’est une variante du tri par permutation, un peu moins efficace; il y a une version optimisée qui est un peu meilleure que le tri par permutation.

    Principe On est à l’étape i.

    •   Supposons déjà trié v[1..i-1], et non traité v[i..vn].
    •   On parcourt v[i..vn] en descendant et, chaque fois que deux éléments consécutifs ne sont pas dans l’ordre, on les permute.
    •   En fin de parcours le min de v[i..vn] se retrouve dans v[i].
    •   Maintenant v[1..i] est trié.Le nom du « tri à bulles » vient de ce que à chaque étape i, les éléments les plus « légers » remontent vers la surface, sont transportés à gauche. (bon à retenir 😀 )On constate aussi que à chaque étape, l’ordre général est accru.Tri à bulles optimiséSi lors d’une étape i, aucune permutation n’a lieu, c’est que [i..vn] est déjà dans l’ordre, et le tri est fini.→ booléen apermute ou encore mieux, indice dp de dernière permutation.

    Tri par comptage

    Cette méthode consiste à construire un vecteur d’indices ind, où l’on calcule la position que devrait avoir chaque élément pour que le vecteur soit trié.

    Exemple Résultat sur le tri des lettres du mot ’ETABLES’.

    Screen Shot 2016-01-18 at 9.38.15 AM

    PROCEDURE tri_comptage ( v : vec_t; vn : integer; VAR w  : vec_t);
    VAR i, k : integer;
        ind : array [1..VMax] of integer;
    BEGIN
     { init }
          for i := 1 to vn do 
             ind[i] := 1;
     { construit ind }
          for i := 1 to vn-1 do
             for k := i+1 to vn do
                 if v[k] < v[i] then 
                     ind[i] := ind[i]+1 
                 else ind[k] := ind[k]+1;
    { construit w }
           for i := 1 to vn do 
              w[ind[i]] := v[i]; 
    END;

     

    Le coût
    La place occupée est importante (3 vecteurs).

    Le nombre de comparaisons est constant (vn × (vn − 1)/2). C’est du même ordre que le tri par permutation ou à bulles non optimisé.

    Il y a très peu d’affectations (vn) ; cela est très intéressant si les éléments de vn sont « lourds », par exemple des strings ou des records triés sur un champ.

     

    4.Mise à jour d’un vecteur

    Soit v[1..vn] un vecteur, avec 1 ≤ vn ≤ VMax.
    On regarde comment insérer ou supprimer un élément de v, en conservant l’ordre ou non des éléments.

    Insertion dans un vecteur non trié

    Pour insérer un élément x en queue de v, il suffit de faire

     

    if vn < VMax then
    begin
      vn := vn+1;
     v[vn] := x;
    end;

     

    Si on veut insérer x à une autre position, c’est que l’on considère que le vecteur est trié avec un certain ordre (croissant, décroissant, d’apparition, etc).

    Insertion dans un vecteur trié

    On veut insérer x à la position i dans v, avec 1 ≤ i ≤ vn. On doit décaler v[i..vn] vers la droite :

    if vn < VMax then 
    begin
       vn := vn+1;
       for j := vn downto i+1 do   { en descendant }
         v[j] := v[j-1];
       v[i] := x;
    
    end;

    Suppression dans un vecteur non tri ́e

    On veut supprimer l’élément v[i], avec 1 ≤ i ≤ vn.

    Si l’ordre des éléments dans v est indifférent, on place l’élément de queue dans le trou.

     

    v[i]:=v[vn]; {si i = vn, cela ne fait rien } 
    vn := vn-1;

     

    Suppression dans un vecteur trié

    On décale v[i+1..vn] vers la gauche :

     for j := i to vn-1 do { en montant }
        v[j] := v[j+1];
        vn := vn-1;
    
    

    5.Tri par insertion

    Voici un algorithme de tri basé sur l’insertion dans un vecteur trié.

    Principe On est à l’étape i.

    •   Supposons déjà trié v[1..i-1], et non traité v[i..vn].
    •  On pose x = v[i]. La case i est disponible.
    •   On cherche k tel que v[k-1] ≤ x < v[k].
    •   On insère x à la position k dans v[1..i-1], ce qui oblige à décaler d’abord v[k..i-1] vers v[k+1..i]; le trou en i est bouché.
    •   Maintenant v[1..i] est trié et v[i+1..vn] est non traité.Exemple Trier les lettres du mot ’ETABLES’.Au départ, on considère que v[1..1] est trié ; on va donc insérer les éléments suivants, de 2 à vn.

    Screen Shot 2016-01-18 at 9.57.45 AM

     

    Implémentation du tri

     

    PROCEDURE tri_insertion ( var v : vec_t; vn : integer);
    VAR i : integer;
    BEGIN
         for i := 2 to vn do
         inserer_trie (v, i);
    END;

     

    Implémentation de l’insertion

     

    PROCEDURE inserer_trie ( var v : vec_t; i : integer); 
    VAR j, k : integer;
        x : type_element;
        
    BEGIN
         { élément à insérer }
          x := v[i];
         { recherche position d’insertion de x }
          k := posit_ins (v, i, x);
        { décalage : en descendant }
          for j := i downto k+1 do 
             v[j] := v[j-1];
         { insertion }
          v[k] := x;
        
    END;
    
    
    
    

    Optimisation de la recherche du point d’insertion

    La recherche du point d’insertion k peut se faire séquentiellement; mais on a tout intérêt à employer une recherche dichotomique, bien plus efficace.

     

    FUNCTION posit_ins ( var v : vec_t; i : integer; x : type_element) : integer;
    VAR inf,sup, m : integer;
    BEGIN
        { le cas des extrémités }
            if x < v[1] then 
              posit_ins := 1 
            else if v[i-1] <= x then
              posit_ins := i 
            else 
              begin
                  { init dichotomie : les cas 1 et i sont déjà traités } 
                  inf := 2;
                  sup := i-1;
                  
                  {recherche position m tel que v[m-1] <= x < v[m] }
                  { : variante de la dichotomie habituelle, }
                  { sans le booléen trouve }
                  while inf < sup do 
                  begin
                     m := (inf + sup) div 2;  
                     if v[m] <= x then 
                       inf := m+1
                     else sup := m;
                  end;
    
                  posit_ins := sup; 
               end; 
    END;

     

    Le coût
    Méthode nettement plus efficace que les autres pour vn grand :

    Par exemple avec vn = 1000, le coût est de 10 000, contre 500 000 pour les autres tris.

Laisser un commentaire

Votre adresse de messagerie ne sera pas publiée. Les champs obligatoires sont indiqués avec *

Facebook