ALGORITHMES DE RECHERCHE

Recherche séquentielle

Introduction

Pour Thomas Cormen, très grand professeur d'informatique, un algorithme est une procédure de calcul, bien définie, qui prend en entrée une valeur ou un ensemble de valeurs, et qui donne en sortie une valeur ou un ensemble de valeurs. C'est un outil permettant de résoudre un problème de calcul bien spécifié.
Un algorithme doit se terminer dans un temps raisonnable et doit résoudre correctement le problème donné. Ces deux propriétés sont respectivement nommées:

• complexité (en temps)
• correction

Cette première leçon d'algorithmique sera orientée vers la recherche (séquentielle) d'un élément dans un tableau.

Parcours séquentiel d'un tableau

Recherche d'une occurence

Soit le problème suivant: étant donné un tableau t de $n$ éléments, écrire un algorithme qui permet de dire si un élément $x$ appartient à ce tableau.

Le problème: $x$ appartient-il au tableau ?

Les entrées: un tableau t et un élément x;

La sortie: une réponse vraie ou fausse (True ou False)

Une solution:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

---------------------------
Algorithme appartient(x, t)
---------------------------
Entrées:
- t: tableau
- x: élément de même type que les éléments du tableau t
Sortie: booléen (réponse)

Variable: n, entier naturel

n = taille(t)
Pour i allant de 0 à n-1 
    Si t[i] = x  
        Renvoyer Vrai  
Renvoyer Faux

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

#Implémentation en python
def appartient_v1(x, t):
    """
    renvoie un booléen correspondant à la présence ou l'absence de x dans t;
    t: tableau
    x: élément de même type que les éléments de t
    """
    n = len(t)
    for i in range(n):
        if t[i] == x:
            return True
    return False

1

appartient_v1(-5, [5, 10, 15, 20])

1

False

1
2
3
4
5
6
7
8
9

def appartient_v1b(x, t):
    """
    renvoie un booléen correspondant à la présence ou l'absence de x dans t;
    t: tableau
    x: élément de même type que les éléments de t
    """
    pass
# TESTS - 
appartient_v1b(-1, [5, 10, 15, 20])

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

def appartient_v2(x, t):
    """
    renvoie un booléen correspondant à la présence ou l'absence de x dans t;
    t: tableau
    x: élément de même type que les éléments de t
    """
    for elt in t:
        if elt == x:
            return True
    return False

Recherche d'un extrémum

Deuxième problème: étant donné un tableau t de $n$ éléments (des entiers pour se fixer les idées). Le deuxième algorithme proposé permet de trouver le minimum parmi les éléments de ce tableau.

Le problème: quellle est la plus petite valeur du tableau ?

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

---------------------
Algorithme minimum(t)
---------------------
Entrée: un tableau t;  
Sortie: le plus petit élément de t  
Variables: 
    n, entier naturel
    mini, même type que les éléments de t
Précondition: t non vide

n = taille(t)
mini = t[0]
Pour i allant de 1 à n-1:
    Si t[i] < mini
        mini = t[i]
Renvoyer mini

Implémentation en python

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

def minimum(t):
    """
    Renvoie le plus petit élément de t
    """
    assert t != [], "Erreur: tableau vide"
    n = len(t)
    mini = t[0]
    for i in range(1,n):
        if t[i] < mini:
            mini = t[i]
    return mini

# Tests
minimum([5, 10, -15, 20])
minimum([0, 12])

Calcul d'une moyenne

Troisième problème: étant donné un tableau t de $n$ éléments que l'on supposera entiers. L'algorithme proposé permet de trouver la moyenne des éléments de ce tableau.

Le problème: quelle est la valeur moyenne des éléments du tableau ?

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

---------------------
Algorithme moyenne(t)
---------------------
Entrée: un tableau t de flottants;  
Sortie: la moyenne de tous les éléments de t  
Variables: 
    n, entier naturel
    somme, flottant
Précondition: t non vide

n = taille(t)
somme = 0
Pour i allant de 0 à n-1:
    somme = somme + t[i]
Renvoyer somme / n

1
2
3
4
5
6
7
8

def moyenne(t):
    """
    Renvoie la moyenne des éléments d'un tableau t non vide;
    """
    pass

# Tests
moyenne([5.5, 10.0, 15.0, 19.5])

Efficacité des algorithmes

En informatique, la question de la performance des algorithmes est centrale. D'une manière générale, le traitement d'une certaine quantité de données requiert un temps d'xecution lié à cette quantité.
Ainsi dans nos exemples où $n$ est la taille du tableau d'entrée, la boucle est parcourue:

• $n$ fois dans le pire des cas (si x n'appartient pas au tableau) dans le problème 1
• $n-1$ fois dans le problème 2;
• $n$ fois dans le problème 3;

Le temps d'exécution sera lié au nombre d'opérations effectuées, qui dépend ici de la taille de l'entrée $n$, plus exactement proportionnel à $n$ (ou $n-1$). On dit que la complexité en temps de ces algorithmes est linéaire.

Recherche dichotomique

Principe

On souhaite rechercher une valeur $x$ dans un tableau t trié (par ordre croissant pour se fixer les idées). L'idée principale est de comparer $x$ avec la valeur située au milieu du tableau:

1
2
3
4

 g                  m                  d
+-----------------+----+----------------+
|    ....         |t[m]|    ....        |
+-----------------+----+----------------+

• si elle est plus petite, il suffit de restreindre la recherche dans la partie gauche du tableau;
• sinon, on la restreint à la partie droite de $t$.
• ou alors on a trouvé $x$

En répétant ce procédé on divise la zone de recherche par deux à chaque fois. On peut alors représenter la situation avec le schéma ci-dessous. Il s'agit d'une application du principe diviser pour régner qui sera vu en terminale.

1
2
3
4

 0              g        d             n-1
+--------------+----------+--------------+
| éléments < x |  ....    | éléments > x | 
+--------------+----------+--------------+

Algorithme

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

---------------------------
Algorithme dichotomie(x, t)
---------------------------
    Entrées: 
        tableau t de taille n; 
        x élément à rechercher, de même type que les éléments de t
    Renvoie index de x ou rien si non trouvé.
    Pré-condition: t trié

    Variables: g, d et m des index repérant les "bords" du tableau et le milieu respectivement

Fixer g à 0 et d à n-1
Tant que g <= d
    calculer index m du milieu du tableau [g..d]
    Si t[m] = x
        Renvoyer m
    Sinon si x > t[m]
        g = m + 1
    Sinon si x < t[m]
        d = m - 1
Renvoyer non trouvé

Implémentation en python

1
2
3
4
5
6

# Fonction à utiliser pour vérifier qu'un tableau est trié
def est_trie(t):
    """
    Vérifie si un tableau t est trié et renvoie un booléen comme réponse
    """
    return all(t[i] <= t[i + 1] for i in range(len(t) - 1))

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

# RECHERCHE DICHOTOMIQUE

def dichotomie(x, t):
    """
    Renvoie la position de x dans le tableau t trié; None si non trouvé
    Précondition: t trié
    """
    assert est_trie(t), "Erreur: tableau non trié"

    g = 0 # index gauche
    d = len(t) - 1 # index droit
    # A compléter

Terminaison de l'algorithme

Lorsqu'un programme contient une boucle while il est suceptible de diverger (on dit aussi qu'il peut entrer dans une boucle infinie). Pour montrer l'arrêt de la boucle, on utilise une technique de raisonnement appelé technique du variant de boucle. Il s'agit de trouver parmi les éléments du programme une quantité:

• entière;
• positive;
• qui décroit strictement à chaque tour de boucle.

Si on peut exhiber un variant de boucle, l'algorithme termine.