Chapitre 1: Parcours séquentiel d’un tableau

Programme

Contenus	Capacités attendues	Commentaires
Parcours séquentiel d’un tableau	Écrire un algorithme de recherche d’un extremum, de calcul d’une moyenne.	On montre que le coût est linéaire

Dans ce chapitre, nous allons étudier des algorithmes de parcours séquentiel d’un tableau pour:

Rechercher un élément d’un type donné.
Rechercher le maximum d’un tableau.
Calculer la moyenne d’un tableau.

Ces algorithmes «séquentiels» ne sont pas du tout efficace, on les appelle en anglais Brute force algorithms.

Exemple de résolution d'un sudoku par force brute. Toutes les solutions sont explorées jusqu'à trouver la bonne.

1 Méthodes de parcours séquentiel d’un tableau

Comme vu dans le chapitre P3C2, on peut itérer sur les valeurs ou sur les index.

1.1 Itération sur les valeurs

On fait une itération sur les valeurs du tableau en utilisant le mot-clé in.

tab = [12, -3, 15, -9, 17, 7]
for val in tab:
    print(val)

>>sortie

1.2 Itération sur les index

C’est la méthode classique utilisée dans les langages impératifs.

for i in range(len(tab)):
    val = tab[i]
    print("indice:", i, "valeur:", val)

>>sortie

indice: 0 valeur: 12
indice: 1 valeur: -3
indice: 2 valeur: 15
indice: 3 valeur: -9
indice: 4 valeur: 17
indice: 5 valeur: 7

2 Recherche d’un extrémum

On initialise la valeur au premier élément du tableau puis on parcourt le tableau pour vérifier s’il existe un élément soit plus petit soit plus grand.

2.1 Recherche du maximum

def maximum(liste):
    # ne pas utiliser max pour le nom de variable
    # car la fonction max existe en Python(on l'écraserait!)
    maxi = liste[0]
    for e in liste:
        if e > maxi:
            maxi = e
    return maxi

# appel de la fonction sur tab
maximum(tab)

2.2 Recherche du minimum

def minimum(liste):
    mini = liste[0]
    for e in liste:
        if e < mini:
            mini = e
    return mini

# appel de la fonction avec la liste tab en argument
minimum(tab)

-9

3 Calculer la moyenne d’un tableau

On initialise une valeur accumulatrice à 0, puis on additionne tous les éléments du tableau. Enfin on divise la somme des éléments par le nombre d’éléments du tableau.

def moyenne(liste):
    somme = 0
    for e in liste:
        somme = somme + e
    # On divise la somme de tpus les éléments par leur nombre
    moyenne = somme / len(liste)
    return moyenne

# appel de la fonction
moyenne(tab)

6.5

4 Coût de l’algorithme: notion de complexité

Pour mesurer l’efficacité temporelle d’un algorithme, on introduit la notion de complexité.

Complexité: La complexité d’un algorithme est le nombre d’opérations élémentaires(opération arithmétique, comparaison, affectation…) effectuées pour obtenir un résultat.

La complexité d’un algorithme dépend souvent de la taille des données d’entrée notée $N$ . Dans notre cas la taille du tableau dans lequel on recherche l’élément.

Pour comparer facilement les algorithmes on se place dans le pire des cas, dans les algorithmes présentés il faut toujours parcourir entièrement la liste pour trouver le maximum, le minimum ou la moyenne: il y a donc $N$ itérations.

On dit que le coût de l’algorithme est linéaire ou encore que c’est un algorithme de complexité $O(N)$ .