Université Bordeaux 1
Licence Semestre 2   Initiation à l'algorithmique
Dernière mise à jour effectuée le 2 Juillet 2007

Tableaux


  1. Définition
  2. Définition 5.1. Un tableau est une table d'association à clé unique telle que
    • le nombre d'éléments de la table (dimension ou taille) est constant,
    • l'accès aux éléments s'effectue directement par la clé,
    • les valeurs minimum et maximum des clés sont des constantes.
    On écrit en EXALGO
    nom_tableau=tableau[min_indice..max_indice] de type_predefini;
    
    ce qui signifie que
    • les éléments ont pour type le type_prédéfini
    • les indices des éléments vont de min_indice à max_indice, avec min_indice<max_indice,
    La taille du tableau est donc max_indice-min_indice+1.
    Pour accéder à un élément d'un tableau T d'indice I, on écrit T[I]. La complexité de l'accès à un élément du tableau est O(1).
    Notation Soit min_indice<i<j<max_indice, notera T[i..j] la séquence des éléments de T (T[i],T[i+1],...,T[j]).
    Beaucoup d'algorithmes peuvent être décrits sans préciser un type particulier. Dans ce cas, on écrira à la place de type_prédéfini le mot élément et on précisera les valeurs possibles pour élément.
    Exemple 5.1.
    Soit deux tableaux
    • TC=tableau[1..10]de car;
    • TE=tableau[1..10]d'entiers;
    L'algorithme qui permet de trier TC et TE est le même. Seul différe le type de l'élément manipulé. On écrirera dans ce cas un algorithme sur un tableau
    T=tableau[1..10]d'éléments;
    et on précisera que élément est dans {car,entier}.

  3. Primitives
  4. Les paramètres tableaux doivent, sauf raison majeure, être passés en paramètre par référence afin d'éviter la recopie.

    Initialisation d'un tableau

    fonction init(ref T:tableau[min_indice..max_indice] d'éléments;
                  val valeurInitiale:élément):vide;
      var i:entier;
      début
        pour i allant de min_indice à max_indice faire
          T[i]= valeurInitiale
        finpour
      fin
    finfonction
    
    Complexité: O(n).

    Taille d'un tableau

    fonction taille(ref T:tableau[min_indice..max_indice] d'élément):entier;
      début
        retourner(max_indice-min_indice+1)
      fin
    finfonction
    
    Complexité: O(1).

    Echange d'éléments

    fonction echange(ref T:tableau[min_indice..max_indice] d'élément;
                     val indice1,indice2: entier):vide;
      var e:élément;
      début
        e=T[indice1];
        T[indice1]=T[indice2];
        T[indice2]=e;
      fin
    finfonction
    
    Complexité: O(1).

    Copie de tableau

    fonction copie(ref T1,T2:tableau[min_indice..max_indice] d'élément;
                   val indiceT1_1,indiceT1_2,indiceT2: entier):booleen; 
      var i:entier;
      début
        si indiceT2+indiceT1_2-indiceT1_1>max_indice alors
          retourner(faux)
        sinon       
          pour i allant de indiceT1_1 à indiceT1_2 faire
            T2[indiceT2]=T1[i];
            indiceT2=indiceT2+1;
          finpour
          retourner(vrai)
      fin
    finfonction
    
    Complexité
    • minimum : O(1)
    • maximum : O(n)
    Source Python

  5. Quelques exemples d'algorithmes
  6. Somme des éléments d'un tableau d'entiers

    fonction somme(ref T:tableau[min_indice..max_indice] d'entiers):entier;
      var s,i:entier;
      début
        s=0;
        pour i allant de min_indice à max_indice faire
          s=s+T[i]
        finpour
        retourner(s)
      fin
    
    Complexité: O(n)

    Recherche d'un élément

    Propriété 5.2. Soit i,j deux entiers, i<=j. Soit T un tableau d'éléments d'indice variant entre i et j. Pour tout élément e, appartenant au tableau T, on a
    T[i]=e ou e est dans T[i+1..j]
    fonction cherche(ref T:tableau[min_indice..max_indice] d'élément;val e:élément):entier;
      var i:entier;
      début
        pour i allant de min_indice à max_indice faire
          si T[i]==e alors
            retourner(i)
        finpour
        retourner()
      fin
    finfonction
    
    Complexité
    • minimum : O(1)
    • maximum : O(n)
    Source Python

    Recherche de l'indice du premier élément minimum

    On suppose que le tableau contient des éléments comparables (l'ensemble des éléments est muni d'une relation d'ordre). Choisissons ici, pour simplifier les notations, des entiers.
    Propriété 5.3.. Soit i,j deux entiers, i<=j. Soit T un tableau d'entiers d'indice variant entre i et j. Soit m l'élément minimum du tableau, on a
    T[i]=m ou m est dans T[i+1..j]
    fonction minimum(ref T:tableau[min_indice..max_indice] d'entier):entier;
      var i,sauv:entier;
      début
      sauv=min_indice;
      pour i allant de min_indice+1 à max_indice faire
        si T[i]<T[sauv] alors
          sauv=i
        finsi
      finpour
      retourner(sauv)
    finfonction
    
    Complexité : O(n)

  7. Matrices
  8. Déclaration

    Une matrice M de dimension nxm est un tableau de dimension n dont chaque élément est un tableau de dimension m. On peut donc déclarer la matrice sous la forme suivante
    var M:tableau[1..n]de tableau [1..m] d'éléments;
    

    Initialisation


    fonction initMatrice(ref M:tableau[1..n] de tableau [1..m]  d'éléments;
                  val valeurInitiale:élément):vide;
      var i,j:entier;
      début
      pour i allant de 1 à n faire
        pour j allant de 1 à m faire
          M[i][j]=valeurInitiale
        finpour
      finpour
      retourner()
    finfonction
    
    Complexité : O(nm)

    Somme de deux matrices réélles


    
    fonction sommeMatrice(ref M1,M2:tableau[1..n] de tableau [1..m]  de réels):
                          tableau[1..n] de tableau [1..m]  de réels;
      var i,j:entier;
      var M:tableau[1..n] de tableau [1..m] de réels;
      début
      pour i allant de 1 à n faire
        pour j allant de 1 à m faire
          M[i][j]=M1[i][j]+M2[i][j];
        finpour
      finpour
      retourner(M)
    finfonction
    
    Complexité : O(nm)