Parcours séquentiel d’un tableau

Notion de tableau

Source : https://fr.wikipedia.org/wiki/Tableau_(structure_de_données)

En informatique, un tableau est une structure de données représentant une séquence finie d’éléments auxquels on peut accéder efficacement par leur position, ou indice, dans la séquence. C’est un type de conteneur que l’on retrouve dans un grand nombre de langages de programmation. On parle aussi de tableau indexé.

Dans les langages à typage statique (comme C, Java et OCaml), tous les éléments d’un tableau doivent être du même type. Certains langages à typage dynamique (tels que Python) permettent des tableaux hétérogènes.

Tableaux en Python

En Python, les tableaux sont représentés grâce à des objets appelés listes (type list). Une liste ressemble à un p-uplet : un ensemble ordonné d’éléments avec des indices pour les repérer.

D’un point de vue syntaxique, les éléments d’une liste sont séparés par des virgules et entourés de crochets :

L = [45, 21, 56 ,12, 1, 8, 30, 22, 6, 33]

Mais on peut également considérer que les chaînes de caractères sont des conteneurs de caractères.

S = "Numérique et Sciences Informatiques !"

On accède aux éléments de ces tableaux grâce à leur propriété d’itérateurs, par leur indice.

>>> L[3]
12

>>> S[13]
'S'

Et on peut assigner des éléments à une liste par une syntaxe proche :

>>> L[4] = 5
>>> L
[45, 21, 56 ,12, 5, 8, 30, 22, 6, 33]

Attention, ceci n’est pas autorisé pour les chaînes de caractères !

>>> S[13] = 's'
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError : 'str' object does not support item assignment

 

 

Tableaux en JavaScript

En JavaScript, les tableaux sont des éléments de type array.

Créer un tableau

var L = [45, 21, 56 ,12, 1, 8, 30, 22, 6, 33];
console.log(L[0]);         // accès par indice
console.log(L.length);     // longueur du tableau

Boucler sur un tableau

L.forEach(function(item, index, array) {
   console.log(item, index);
   });

Pour la suite, nous utiliserons Python, et travaillerons sur une liste de nombres entiers générés aléatoirement :

from random import randint
L = [randint(1, 100) for i in range(10)]

Parcours et Itération

En Python, les listes, les chaînes de caractères, les tuples, et un grand nombre d’autres objets sont des itérateurs : il contiennent dans leur structure les méthodes permettant de les parcourir.

Par indice

On  peut parcourir un tableau en faisant évoluer un indice :

i = 0                 # initialisation de i
while i < len(L):     # vérification
   print(L[i])
   i += 1             # incrémentation de i

for i in range(len(L)):
   print(L[i])

Par valeur

Les listes Python possèdent leur propre propriété d’itération, on peut donc directement itérer sur les valeurs :

for e in L:
   print(e)

Par indice et valeur

Il est parfois intéressant d’avoir à la fois l’indice et la valeur d’un élément de la liste :

for i, e in enumerate(L):
   print(i, e)

Recherche d’une occurrence

Il s’agit de déterminer la position (l’indice) d’un élément e prétendument présent dans la liste L .

On parle d’occurrence de e dans L.

Algorithme

Un « pointeur » i, initialisé à zéro, permet d’accéder aux éléments de la liste L. À chaque itération, on compare l’élément d’indice i de la liste avec l’élément e recherché. S’ils sont égaux, cela signifie que l’indice de e dans L vaut i et les itérations cessent, dans le cas contraire, on incrémente i et on fait une nouvelle itération. Si l’élément e n’est pas dans la liste L, le pointeur va jusqu’au bout de la liste, et finit par prendre la valeur de la longueur de la liste.

Implémentation en Python

def indice(e, L):
   i = 0
   continuer = True
   while i < len(L) or continuer:
      if L[i] == e:
         continuer = False
      else:
         i = i + 1
   return i

Remarque : si i == len(L) alors cela signifie que L ne contient aucune occurrence de e.

 

Coût temporel

Nous supposerons que chaque opération (affectation, comparaison, opération arithmétique, …) a un coût de 1 « unité » de temps.

Si n est la longueur de la liste L, on peut calculer la complexité ainsi :

def indice(e, L):
   i = 0                              # 1 (une affectation)
   continuer = True                   # 1 (une affectation)
                                      # dans le pire des cas, on itère n fois
   while i < len(L) and continuer:      # 3 (une comparaison, une interrogation de longueur de liste, une opération booléenne
      if L[i] == e:                     # 2 (une interrogation de liste, une affectation) 
         continuer = False              # 1 (une affectation)
      else:                           # Pire des cas = on continue !
         i = i + 1                      # 2 (une opération, une affectation)
   return i

Complexité : \(T(n)=2+7\times n=\mathcal{O}(n)\)

Coût linéaire !

Méthode Python

L.index(e)

Renvoie l’indice de l’élément e dans la liste L.

Attention :

• si e n’est pas dans L, L.index(e) provoque une erreur !
• s’il y a plusieurs occurrences de e dans L, seul l’indice de la première est renvoyé.

Recherche des extremums

Algorithme

Pour connaitre la valeur maximale des valeurs contenues dans la liste L, il faut évaluer tour à tour tous les éléments e de L.

La valeur maximale à une étape donnée est mémorisée dans une variable m, initialisée avec le premier élément de la liste L.

Si l’élément e est supérieur à m, alors m prend alors la valeur de e.

Implémentation en Python

def maximum(L):
    m = L[0]
    for e in L[1:]:
        if e > m:
            m = e
    return m

Coût

def maximum(L):
    m = L[0]            # 1
                        # x(n-1)
    for e in L[1:]:     # 1
        if e > m:         # 1
            m = e         # 1 (pire des cas)
    return m

Méthode Python

Il existe deux fonctions max() et min() permettant de déterminer les extrémums d’une liste.

Calcul de la moyenne

Algorithme

Pour calculer la moyenne des valeurs d’une liste, il faut calculer la somme de ces valeurs et diviser par le nombre de valeurs contenues dans la liste.

Pour calculer la somme on initialise une variable s à zéro, et on itère sur l’ensemble des éléments e de la liste. A chaque itération, on ajoute à s la valeur de l’élément e.

Implémentation en Python

def somme(L):
    s = 0
    for e in L:
        s += e
    return s

Coût

def somme(L):
    s = 0            # 1
                     # xn
    for e in L:        # 1
        s += e         # 2
    return s

Méthode Python

La fonction sum() permet de calculer la somme des valeurs d’une liste.

Il suffit ensuite de diviser par la longueur de la liste len(L).

Sources : cours sur la complexité algorithmique : https://www.supinfo.com/cours/2ADS/chapitres/01-notion-complexite-algorithmique

Exercices

def compter(S, c):
    n = 0
    for l in S:
        if c == l:
            n += 1
    return n

Autres exercices