Algorithmes de parcours séquentiel d'un tableau

Les algorithmes de parcours séquentiel permettent de parcourir les éléments d'un tableau à l'aide d'une boucle.

Ils font partie des algorithmes fondamentaux en informatique, leur parfaite maîtrise est donc indispensable car ils sont à la base de beaucoup d'autres algorithmes qui doivent passer en revue tous les éléments d'une collection (tableau, tuple, liste, dictionnaires, etc.).

On détaille dans ce chapitre les trois algorithmes au programme :

l'algorithme de recherche d'un élément (ou d'une occurrence)
l'algorithme de recherche d'un extremum (maximum ou minimum)
l'algorithme de calcul d'une moyenne

Algorithme de recherche d'un élément

On veut écrire un algorithme qui cherche si un élément est présent ou non dans un tableau.

Spécification de l'algorithme

La spécification d’un algorithme précise de manière non ambigüe ce que doit faire un algorithme. En particulier, on y indique : le nom des données manipulées (entrées), le nom des données renvoyées (sorties), le rôle de l’algorithme ainsi que les hypothèses sur les entrées (précondition) et les sorties (postcondition). Un algorithme sera considéré comme correct s’il respecte cette spécification.

Voici la spécification de l'algorithme de recherche d'un élément :

Entrée(s) : un tableau tab de taille $n$ et une valeur v
Sortie(s) : un booléen
Rôle : chercher si la valeur v est présente dans tab
Précondition(s) : v est du même type que les éléments de tab
Postcondition(s) : le booléen renvoyé vaut Vrai si v appartient à tab, et Faux sinon

Algorithme

L'idée est la suivante :

on parcourt une à une les valeurs du tableau tab :
- si on en trouve une égale à v, on renvoie Vrai (inutile de regarder les valeurs suivantes) ;
- sinon on passe à la valeur suivante ;
si on a parcouru tout le tableau sans trouver v, on renvoie Faux.

Voici l'algorithme écrit en langage naturel et en Python (fonction recherche) :

Langage naturel

pour chaque elt de tab faire :
    si elt = v alors :
        renvoyer Vrai
    fin si
fin pour

Python

def recherche(v, tab):
    for elt in tab:
        if elt == v:
            return True
    return False

On peut tester cette fonction :

>>> recherche(5, [2, 3, 1, 5, 0])
True
>>> recherche(1, [0, 3, 0, 0])
False

Coût de l'algorithme

Le coût d'un algorithme est le nombre d'opérations élémentaires (arithmétiques ou logiques) ainsi que d'affectations nécessaires à son exécution dans le pire cas. Le coût d'un algorithme dépend toujours de la taille des données d'entrée (ici la taille $n$ du tableau).

Convention de comptage : on ne compte pas l'affectation de la variable de boucle (elt, qui prend successivement chaque valeur du tableau), ni le calcul de la longueur len(tab), ni les instructions renvoyer (return).

Le nombre de tours de boucle dépend des valeurs du tableau : si v est la première valeur du tableau, un seul tour suffit. Le pire cas est celui où v n'est pas dans le tableau (ou seulement en dernière position) : la boucle effectue alors $n$ tours et la comparaison elt == v est effectuée $n$ fois.

Il n'y a aucune affectation ni aucune opération arithmétique.

On dénombre ainsi dans le pire cas :

Comparaisons	Affectations	Opérations arithmétiques
$n$	$0$	$0$

Le coût de l'algorithme (dans le pire cas) est donc $n + 0 + 0 = n$.

Comme ce coût est de l'ordre de $n$, on dit que le coût de l'algorithme de recherche d'un élément est linéaire.

Remarques

Parcours par indice

Il est aussi possible de parcourir le tableau par indice (c'est la fonction recherche_v2 de l'exercice 1 du notebook) :

def recherche_v2(v, tab):
    for i in range(len(tab)):
        if tab[i] == v:
            return True
    return False

Le coût est le même : $n$ comparaisons dans le pire cas, donc un coût linéaire.

Si notre algorithme ne devait plus renvoyer Vrai ou Faux mais l'indice de la valeur v cherchée, alors il aurait été obligatoire de parcourir le tableau par indice, pour garder trace des indices et renvoyer celui demandé. Le choix du parcours dépend donc de la spécification de l'algorithme à écrire !

Sans sortie anticipée

La fonction recherche utilise le mot clé return pour stopper son exécution dès que la valeur v est trouvée (sortie anticipée). On peut aussi écrire l'algorithme sans sortie anticipée, à l'aide d'un booléen trouvee initialisé à Faux et qui prend la valeur Vrai si on trouve v :

def recherche_v3(v, tab):
    trouvee = False
    for elt in tab:
        if elt == v:
            trouvee = True
    return trouvee

Cette version n'est pas optimale : elle parcourt toujours tout le tableau, même si v est la première valeur. Dans le pire cas (tous les éléments sont égaux à v), elle effectue $n$ comparaisons et $n+1$ affectations, soit un coût de $2n+1$ : le coût reste linéaire, mais la version avec sortie anticipée est la plus simple à écrire et la plus rapide. On pourra donc l'utiliser sans problème.

Avec une boucle `while`

On aurait également pu écrire une version optimisée (avec arrêt dès que v est trouvée) sans utiliser une sortie anticipée (avec return) à condition d'utiliser une boucle while. Cependant l'écriture est plus longue et compliquée :

def recherche_v4(v, tab):
    i = 0
    trouvee = False
    while i < len(tab) and trouvee == False:
        if tab[i] == v:
            trouvee = True
        i = i + 1
    return trouvee

Algorithme de recherche du maximum

On veut écrire un algorithme qui recherche la valeur maximale dans un tableau.

La recherche du maximum est présentée ici, mais ce qui va être dit est vrai pour la recherche d'un extremum de manière générale, qu'il s'agisse d'un maximum ou d'un minimum.

Spécification de l'algorithme

Entrée(s) : un tableau tab de taille $n$
Sortie(s) : un entier maxi
Rôle : chercher l'élément maximal de tab
Précondition(s) : tab est un tableau non vide d'entiers
Postcondition(s) : maxi est un entier qui est l'élément maximal de tab

Algorithme

L'idée est la suivante :

on initialise la valeur maximale par le premier élément du tableau ;
on parcourt une à une les valeurs du tableau tab :
- si on en trouve une strictement supérieure au maximum provisoire, cette valeur devient notre nouveau maximum (provisoire) ;
- sinon, on ne fait rien.

Voici l'algorithme écrit en langage naturel et en Python (fonction recherche_max) :

Langage naturel

maxi ← tab[0]
pour chaque elt de tab faire :
    si elt > maxi alors :
        maxi ← elt
    fin si
fin pour

Python

def recherche_max(tab):
    maxi = tab[0]
    for elt in tab:
        if elt > maxi:
            maxi = elt
    return maxi

On peut tester :

>>> recherche_max([1, 2, 3, 4, 5])
5
>>> recherche_max([7, 9, 2])
9

Coût de l'algorithme

Dans tous les cas, notre algorithme va effectuer $n$ tours de boucle, donc dans le pire cas aussi. Ainsi, la comparaison elt > maxi sera effectuée $n$ fois.

Au premier tour de boucle, elt vaut tab[0], donc la condition elt > maxi est fausse. Si les éléments sont rangés dans l'ordre (strictement) croissant, alors la condition elt > maxi est vraie à chacun des $n-1$ tours de boucle suivants, et l'affectation maxi ← elt est effectuée $n-1$ fois.

Le pire cas est donc un tableau dans lequel chaque élément est strictement supérieur au précédent (par exemple [1, 2, 3, 4, 5] pour un tableau de $n=5$ éléments).

On dénombre ainsi dans le pire cas :

Comparaisons	Affectations	Opérations arithmétiques
$n$	$n$	$0$

Remarque : il y a $1$ affectation pour l'initialisation maxi ← tab[0], puis $n-1$ affectations maxi ← elt, donc $n$ affectations.

Le coût de l'algorithme (dans le pire cas) est donc $n + n + 0 = 2n$.

Comme ce coût est de l'ordre de $n$, on dit que le coût de l'algorithme de recherche d'un extremum est linéaire.

Remarques

Parcours par indice

La version précédente a le (petit) désavantage de comparer le premier élément du tableau avec lui-même (au premier tour de boucle) alors que ce n'est pas utile. Un parcours par indice permet de commencer au deuxième élément (c'est la fonction recherche_max_v2 de l'exercice 1 du notebook) :

def recherche_max_v2(tab):
    maxi = tab[0]
    for i in range(1, len(tab)):
        if tab[i] > maxi:
            maxi = tab[i]
    return maxi

Cette version effectue $n-1$ comparaisons et $n$ affectations dans le pire cas (on ne compte pas la soustraction du n-1), soit un coût de $2n-1$ : cela ne change rien, le coût reste linéaire.

Si notre algorithme ne devait plus renvoyer la valeur maximale mais une position de cette valeur maximale, alors il aurait été obligatoire de parcourir le tableau par indice, pour garder trace des indices et renvoyer celui demandé. Le choix du parcours dépend donc de la spécification de l'algorithme à écrire !

Algorithme de calcul d'une moyenne

On veut écrire un algorithme qui calcule la moyenne des nombres présents dans un tableau.

Spécification de l'algorithme

Entrée(s) : un tableau tab de taille $n$
Sortie(s) : un réel
Rôle : calculer la moyenne des éléments de tab
Précondition(s) : tab est un tableau non vide d'entiers
Postcondition(s) : le réel renvoyé est la moyenne des éléments de tab

Algorithme

L'idée est de calculer la somme des valeurs de tab puis de calculer la moyenne en divisant la somme par le nombre d'éléments de tab :

on initialise la somme des valeurs à 0 ;
on parcourt une à une les valeurs du tableau tab :
- on ajoute chaque valeur à notre somme ;
la réponse est la somme divisée par n (le nombre d'éléments de tab).

Voici l'algorithme écrit en langage naturel et en Python (fonction moyenne) :

Langage naturel

somme ← 0
pour chaque elt de tab faire :
    somme ← somme + elt
fin pour
moy ← somme / n

Python

def moyenne(tab):
    somme = 0
    for elt in tab:
        somme = somme + elt
    return somme / len(tab)

On peut tester :

>>> moyenne([10, 14, 6])
10.0
>>> moyenne([8, 15, 12, 14, 19, 11])
13.166666666666666

Coût de l'algorithme

Dans tous les cas, notre algorithme va effectuer $n$ tours de boucle, donc dans le pire cas aussi. Ainsi, l'affectation somme ← somme + elt est effectuée à chaque tour de boucle.

N'importe quel tableau est donc un pire cas pour notre algorithme.

On dénombre ainsi :

Comparaisons	Affectations	Opérations arithmétiques
$0$	$n+1$	$n+1$

Remarque : il y a $1$ affectation pour l'initialisation somme ← 0 et $n$ affectations somme ← somme + elt, donc $n+1$ affectations. Il y a $n$ additions et une division (somme / n) donc $n+1$ opérations arithmétiques.

Le coût de l'algorithme (dans le pire cas) est donc $0 + (n+1) + (n+1) = 2n + 2$.

Comme ce coût est de l'ordre de $n$, on dit que le coût de l'algorithme de calcul d'une moyenne est linéaire.

Remarques

Parcours par indice

Il est aussi possible de parcourir le tableau par indice (c'est la fonction moyenne_v2 de l'exercice 1 du notebook) :

def moyenne_v2(tab):
    somme = 0
    for i in range(len(tab)):
        somme = somme + tab[i]
    return somme / len(tab)

Le coût est le même ($2n+2$), donc linéaire. La version par valeur est légèrement plus simple à écrire et peut donc être privilégiée pour le calcul de la moyenne des éléments d'un tableau.

Bilan

La spécification d'un algorithme définit de manière non ambigüe ce qu'un algorithme doit faire, les données avec lesquelles il travaille (les entrées) et les données qu'il renvoie (les sorties).
Un algorithme de parcours séquentiel d'un tableau parcourt les éléments du tableau à l'aide d'une boucle. Ces algorithmes sont à la base de beaucoup d'autres algorithmes.
Les trois algorithmes de parcours séquentiel étudiés ont tous un coût linéaire, c'est-à-dire un coût de l'ordre de la taille $n$ du tableau parcouru.
Le type de parcours, par indice ou par valeur, dépend de l'algorithme et de l'exercice.
Nous verrons d'autres algorithmes au cours de l'année, dont certains n'ont pas un coût linéaire.

Références :

Documents ressources de l'équipe éducative du DIU EIL, Université de Nantes, Christophe JERMANN et Christophe DECLERCQ.

Germain BECKER & Sébastien POINT, Lycée Mounier, ANGERS Licence Creative Commons

Algorithmes de parcours séquentiel d'un tableau

Algorithmes de parcours séquentiel d'un tableau

Algorithme de recherche d'un élément

Spécification de l'algorithme

Algorithme

Coût de l'algorithme

Remarques

Parcours par indice

Sans sortie anticipée

Avec une boucle while

Algorithme de recherche du maximum

Spécification de l'algorithme

Algorithme

Coût de l'algorithme

Remarques

Parcours par indice

Algorithme de calcul d'une moyenne

Spécification de l'algorithme

Algorithme

Coût de l'algorithme

Remarques

Parcours par indice

Bilan

Avec une boucle `while`