Articles - Algorithmique

Algorithmes de tri

Tri par insertion
Soit un tableau de valeur non triées.
Algorithme :

class TriparInsertion
{
     int tab[ ]; //tableau de valeur à trier
     void trierParInsertion( )
     {
          for(int i=1; i < tab.length; i++)
          {     //on fait la valeur tab[i]
               for(int j=i-1; (j > = 0) && (tab[j+1] < tab[j]); j--)
               {     //inversion 
                    int temp = tab[j+1];
                    tab[j+1] = tab[j];
                    tab[j] = temp;
               }
          }
     }
}

Exemple

7 2 4 6 3 9 8 5 
2 7 4 6 3 9 8 5 
2 4 7 6 3 9 8 5
2 4 6 7 3 9 8 5
2 4 6 3 7 9 8 5 
2 4 3 6 7 9 8 5
2 3 4 6 7 9 8 5 
2 3 4 6 7 8 9 5 
2 3 4 6 7 8 5 9
2 3 4 6 7 5 8 9
2 3 4 6 5 7 8 9 
2 3 4 5 6 7 8 9

Complexité
Dans le meilleur des cas : O(n) pour un tableau déjà trié.
Dans le pire des cas : O(n²) pour un tableau triè dans l'ordre inverse.
L'algorithme est très simple à écrire mais mauvaise complexité dans certain cas.
Réservé aux cas des petits tableaux (n < 20) car le facteur multiplicatif (qui est supprimé dans la notion O(...) est petit, alors que les algorithmes, en théorie meilleurs, ont des gros facteurs multiplicatifs : 100n log(n)

Tri par tas (Heap sort)
Notions
Les arbres :
Chaque noeud n'a qu'un seul père. Un noeud a 1 ou 0 père. Une feuille est un noeud sans fils. La racine est un noeud unique sans père. La hauteur d'un arbre est la distance entre la racine et la feuille la plus éloignée.
Les arbres binaires :
Tout noeud a 0, 1 ou 2 fils.
Les arbres binaires équilibrés :
Il s'agit d'un arbre binaire où chaque noeud a 2 fils obligatoirement, sauf ceux du dernier niveau.
Tas :
Il s'agit d'un arbre binaire équilibré, contenant des valeurs (1 par noeud) telles que tout noeud contient une valeur plus grande ou égale à se fils.

Algorithme
2 phases : construction du tas puis destruction du tas.
Construction du tas
On ajoute les valeurs une par une.
On met chaque valeur le plus en bas à gauche du tas
On la compare à son père. Si elle est plus grande on fait l'échange et on recommence.
Exemple

7 2 4 6 3 9 8 5
     on ajoute 7
               7
     on ajoute 2
               7
             /
          2
     on ajoute 4
               7
             /    \          
          2       4
     on ajoute 6
               7					       7
             /    \          				       /  \
          2       4                                       6     4
         /						    /
       6					         2
etc ...
        9
    6      8
  5  3  4  7
2                        ............ au final !

Complexité des algorithmes

But : pouvoir comparer deux algorithmes

temps d'exécution
place occupé en mémoire (par le programme + les données)
performance garantie ou moyenne ?
dans quel cas ? (nombre de données, ...)
complexité d'écriture de l'algorithme

Cout approximatif d'une opération

i = 1;       // 1 opération (affectation)
i = j + 1;  // 2 opérations (addition+affectation)
k = t[ i ];  // 2 opérations (accès tableau+affectation)
a = 2*k + t[i+3]; // 5 opérations

if (i<2)          // 2 opérations
{  i=i+3;   }    // 2 opérations
else
{   i=(2*i)-(7*j);   }    // 4 opérations
                 => meilleur cas : 4 opérations (i<2)
                 => pire cas : 6 opérations (i>2)
                 => cas moyen : (6+4)/2 = 5 opérations (dépend de i)

for (i=0; i<10; i++)   // 1 + 2 + 1
{
     s=s+1; // 2 opérations
}
     => initialisation 1 opération
     => 10 boucles : (test + incr + calcul) x 10
     => test de sortie 2 opérations
     => TOTAL : 53 opérations

for (i=0; i initialisation 1 opération
     => n boucles : (test + incr + calcul) x n
     => test de sortie 2 opérations
     => TOTAL : 5n + 3 opérations

Ecriture en O(...)

pour comparer 2 algorithmes, on ne comparera que les facteurs les plus significatifs (pour un n suffisamment grand)
=> n² plus significatif que n ou toute autre constante
O(5n²+3n+3) = O(n²)

Classification des algorithmes
O(1)
O(log(n))
O(n)
O(n.log2(n))
O(n²)
O(n^3)
.........
O(x^n)
O(n!) --> catastrophique

Quelques exemples simples

chercher la plus grande valeur dans un tableau de n valeurs non trié : O(n)
chercher si une valeur est présente dans un tableau non trié
meilleur cas : O(1)
pire cas : O(n)
cas moyen : O(n/2) = O(n)
chercher la moyenne des valeurs d'un tableau de n x m valeurs : O(n*m)

Recherche dichotomique :
Pb : cherche si une valeur est présente dans un tableau DEJA TRIE par ordre croissant
Algorithme :

class TableauTrie
{
     int tab[];
     ...
     public int chercher(int valeur)
     {
          //recherche dichotomique retourne le n° de la case si trouvée -1 sinon
          int ig, id; // index gauche et droit
          ig = 0;
          id = tab.length - 1;
          while(ig!=id)
          {
               if (tab[(ig+id)/2]==valeur)
               {
                    return ((ig+id)/2); //trouvé
               }
               if (tab[(ig+id)/2] > valeur)
               {
                    id = (ig+id)/2;
               }
               else
               {
                    ig = (ig+id)/2;
               }
          }
          return (-1); // pas trouvé
     }
}

Complexité au pire des cas : O(log2(n))

Syntaxe des boucles et tests en Algo

Bloc d'instructions :

début
     instructions
fin

Bloc d'instructions bis :

{
     instructions
}

Affectation :

maVariables <-- 3  /maVariable reçoit la valeur 3

Si ... Alors ... Sinon :

Si expresion booléenne Alors
     instructions
Sinon
     instructions

Tant que .... faire :

Tant que expresion booléenne Faire
     instructions

Les choix :

Cas maVariable
     valeur1 : instructions
     valeur2 : instructions
     valeur3 : instructions

Manipulation des tableaux

Tableau d'objets :

tab[4] : maClasse; // on crée un tableau de 4 lignes de type maClasse
Pour i de 0 à  3 faire
     tab[i] <-- nouveau monConstructeur();

Tableau à 2 dimensions :

tab[4][4] : entier; // on crée un tableau de 4 lignes et 4 colonnes de type entier
Pour i de 0 à  3 faire
     Pour j de 0 à  3 faire
          tab[i][j] <-- 123; // toutes les cellules du tableau contiennent la valeur 123

Utilisation des classes

Création d'une classe :

Classe : maClasse
{
     var privée i : entier;
     var privée j : entier;
     monConstructeur(p1, p2) //doit porter le même nom que la classe
     {
          j <-- p1;
          i <-- p2;
     }
}

Programme principal :

Algorithme : monAlgo
{
     Inclure maClasse;
     monObjet : maClasse;
     var a <-- 5: entier;
     var b <-- 3 : entier;
     monObjet <-- nouveau monConstructeur(a, b);
     écrire(monObjet.maMéthode);
}

Présentation d'un algorithme

Algorithme : nom de l'algorithme

Spécifications : à quoi sert l'algorithme
Données : quelles sont les données que l'algorithme manipule
Résultats : quels sont les résultats donnés par l'algorithme
Analyse : comment se découpe l'enchaînement de traitements

Lexique : liste des variables et constantes

Variables : type quelles sont les variables utilisées
Constantes : type quelles sont les constantes utilisées

Algorithme des traitements : contenu de programme rédigé en pseudo-code