Algorithmes sur les tableaux (3 TD)


Les premiers travaux dirigés d'ASD concernent le traitement des tableaux d'entiers.

  1. Généralités.
  2. Parcours simples, algorithmes linéaires
  3. Parcours doubles, algorithmes quadratiques.
  4. Linéarisation d'algorithmes quadratiques.
  5. Modifications de tableaux.


1. Généralités

1.1. Langage algorithmique et conventions

Conventions

1.2. Coût d'un algoritme : notations "Grand O"


On dit qu'une fonction f(n) est en O(g(n)) lorsqu'il existe une constante positive C et un entier N tel que pour tout n>N, f(n) < C g(n).

Exemples

1.3. Evaluations de la complexité d'un algorithme


Exemple. Considérons la fonction Trouve ci-dessus:

Cas le pire : N (le tableau ne contient pas a)
Cas le meilleur : 1 (le premier élément du tableau est a)
Complexité moyenne : Si les nombres entiers de 1 à k apparaissent de manière équiprobable, on peut montrer que le cout moyen de l'algorithme est

                                                N
k (1 - (1 - 1/k) ).

De fait les cas où l'on peut explicitement calculer la complexité en moyenne sont rares. Cette étude est un domaine à part entière de l'algorithmique que nous aborderons assez peu en Licence. Toutefois, il est indispensable, après avoir écrit un algorithme, de calculer sa complexité dans le pire des cas et dans le meilleur des cas.

2. Parcours simples, algorithmes linéaires.

Il s'agit d'algorithmes consistant parcourir à l'aide d'une boucle les éléments d'un tableau et à exécuter pour chacun d'eux un nombre borné d'opérations. Ces algorithmes sont linéaires, c'est à dire en O(n) où n est la taille du tableau.
  1. Trouver le plus petit élément d'un tableau .
  2. Trouver l'indice du deuxième plus grand élément d'un tableau.
    Une correction
  3. Trouver le nombre d'occurences d'une valeur dans un tableau.
  4. Ecrire un algorithme qui fournit le plus petit indice d'une valeur a dans un tableau t, et qui retourne -1 si l'élément a n'apparait pas dans le tableau.
  5. Soit T un tableau fomrmé uniquement de 0 et de 1. Ecrire un algorithme qui retourne la position i dans le tableau T telle que T[i] est la plus longue suite de zéros dans T.
    Une correction

    3. Parcours doubles, algorithmes quadratiques.


    Il s'agit d'algorithmes consistant à parcourir à l'aide de deux boucles imbriquées les éléments d'un tableau et à exécuter pour chacun d'eux un nombre borné d'opérations. Ces algorithmes sont quadratiques, c'est à dire en O(n^2), même si la boucle intérieure n'est pas complète (ne pas oublier que 1+2+3+..+n = O(n^2)).
  6. Trouver l'élément le plus fréquent dans un tableau .
  7. Trouver la somme des carrés des différences des éléments d'un tableau.


    4. Linéarisations d'algorithmes quadratiques.


    Certains algorithmes peuvent paraître a priori quadratiques alors qu'ils sont en fait linéaires.
  8. Trouver le plus grand écart dans un tableau (i.e. le maximum des |t[i]-t[j]|) .

    Une méthode classique pour linéariser des algorithmes quadratiques dans les tableaux est l'utilisation d'un tableau supplémentaire pour enregistrer le résultat de calculs.

  9. Linéariser ainsi l'algorithme qui retourne l'élément le plus fréquent d'un tableau de taille N dans le cas particulier ou le tableau est constitué de nombres entiers compris entre 1 et N.
    Problème : descentes et des invertions sur les permutations.

    Quelquefois, c'est le raisonnement qui permet une telle linéarisation.

  10. Linéariser le calcul de la somme des carrés des différences des éléments d'un tableau.


    5. Modifications de tableaux.


    Il s'agit d'algorithmes qui modifient le tableau donné en entrée du programme en déplaçant ses éléments.
  11. Algorithme de décalage d'un tableau
    Exemple (1,3,2,2,1) -> (3,2,2,1,1)
  12. Renversement de tableau
    Exemple (1,3,2,2,1) -> (1,2,2,3,1)
  13. Algorithmes du drapeau.

Complexite du cas en moyenne de l'algorithme Trouve.

On peut se convaincre du résultat en examinant le fragment de code maple suivant.

Le nombre total de tableaux de longueur n est k^n, qui se décomposent comme suit, selon la position du premier a:

> A:=simplify((k-1)^N+sum((k-1)^i*k^(N-1-i),i=0..(N-1)));

N
A := k


> B:=simplify(N*(k-1)^N+sum((i+1)*(k-1)^i*k^(N-1-i),i=0..(N-1)));

N (N + 1)
B := - (k - 1) k + k


> C:=simplify(B/A);
/k - 1\N
C := - k |-----| + k
\ k /
> C1:=k*(1-(1-1/k)^N);
N
C1 := k (1 - (1 - 1/k) )


> simplify(C1-C);
0


Remarque. On en déduit qu'asymptotiquement (lorsque N est grand et k fixé >1), le coût de l'algorithme est sensiblement k+N. En effet, (1-1/k)^N vaut alors 1-N/k.