Chapitre 0: Rappels

Nous allons revoir quelques définitions importantes de première en s'appuyant sur les algorithmes classiques de recherche et de tris.

Algorithme naïf de recherche: la recherche en table

Pour rechercher un élément dans une table on pourrait simplement parcourir tout simplement le tableau jusqu'à rencontrer la valeur recherché. C'est ce que l'on appelle la recherche en table.

def recherche(liste, élément):
    """Recherche d'un élément dans une liste
    
    Arguments
    ---------
    liste: liste d'entiers
    élément: entier
        l'élément cherché
    
    Returns
    -------
    int: l'indice de l'élément si trouvé ou -1 sinon
    
    """
    for i in range(len(liste)):
        if liste[i] == élément:
            # l'élément est trouve
            return i
    # non trouvé
    return -1

# Quelques tests
assert recherche([1], 1) == 0
assert recherche([1,6,5], 5) == 2
assert recherche([1,6,5], 7) == -1

Même si cet algorithme simple semble faire le travail, il n'est en pratique pas du tout utiliser, car il n'est pas du tout efficace.

Pour mesurer l'efficacité d'un algorithme, on utilise la notion de complexité.

Notion de complexité

Si je donne à mon programme une entrée de taille $N$. Quel est l'ordre de grandeur, en fonction de $N$, du nombre d'opérations qu'il va effectuer ?

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.

Si on prend l'exemple de l'algorithme précédent, on se rend compte que cela dépend des cas. Expliquez...

Pour pouvoir faire des comparaisons entre algorithmes, l'informaticien étudie souvent la complexité dans le pire des cas.

for i in range(len(liste)):      # N opérations
    if liste[i] == élément:      # N opérations
        return i                 # 0 opération(on est dans le pire des cas)
return -1                        # 1 seul return 

Notation asymptotique: grand O

On utilise la notation asymptotique ($N \rightarrow \infty$) pour décrire le temps d'exécution des algorithmes. On se placera dans le pire des cas(Ex: élément non trouvé pour une recherche) la complexité est alors notée $O$.

Un algorithme efficace: la recherche dichotomique

Quand on cherche un mot dans le dictionnaire, on ne va pas le chercher en les lisant un par un, on va utiliser la méthode de recherche dichotomique vue en première.

Cette méthode est possible dans le cas ou les données ont été au préalable trié, ce pour quoi il existe également des algorithmes efficaces.

Voici un exemple d'implémentation en Python:

def recherche_dichotomique(liste, élément):
    """Recherche dichotomique

    Arguments
    ---------
    liste: liste d'entiers
        ATTENTION: la liste doit être triée
    élément: entier
        l'élément cherché
    
    Returns
    -------
    int: l'indice de l'élément si trouvé ou -1 sinon
    
    """
    # on initialise les indices début et fin aux extrémités de la liste
    début = 0
    fin = len(liste)    
    while début <= fin:
        # On se place au milieu de la liste
        milieu = (début + fin) // 2 # il, s'agit d'une division entière
        if liste[milieu] == élément:
            # l'élément est trouvé
            return milieu
        elif liste[milieu] < élément:   
            # l'élément est situé dans la sous-liste de droite    
            début = milieu + 1
        else:
            # l'élément est situé dans la sous-liste de gauche
            fin = milieu - 1
    return -1

Cet algorithme est beaucoup plus efficace, sa complexité (asymptotique dans le pire des cas) est $O(log(N))$.

Ceci fait une énorme différence notamment lorsque la taille des données augmente:

Correction d'un algorithme

Pour rappel, un algorithme est une suite d'instructions permettant d'obtenir un résultat.

La correction d'un algorithme est une démonstration qui prouve que l'algorithme permet bien d'obtenir le résultat souhaité.

Nous allons utiliser une méthode répandue semblable au raisonnement par récurrence fondée sur la recherche d'un invariant de boucle.

Pour prouver la correction nous devons montrer les trois points suivants:

1. Initialisation: L'invariant est vrai avant la première itération.
2. Conservation: si l'invariant est vrai avant une itération, il restera vrai après l'itération.
3. Terminaison: la boucle se termine et nous donne le résultat attendu.

Nous allons appliquer cette méthode aux algorithmes de tris vus en première.

Correction du tri par sélection

On rappelle le principe de l'algorithme.

Sur un tableau de N éléments (numérotés de 0 à $N-1$), le principe du tri par sélection est le suivant :   - rechercher le plus petit élément du tableau, et l'échanger avec l'élément d'indice 0 ; - rechercher le second plus petit élément du tableau, et l'échanger avec l'élément d'indice 1 ; - continuer de cette façon jusqu'à ce que le tableau soit entièrement trié.

Implémentation en Python

En voici une implémentation en python.

def tri_selection(t):
    N = len(t)
    # Parcourir le tableau jusqu'à l'avant dernière valeur
    # en effet la dernière valeur sera forcément la plus grande
    for i in range(N-1):
        # on recherche l'indice du plus petit élément du sous-tableau de droite
        i_min = i
        #  Parcourir le reste du tableau pour rechercher l'élément le plus petit restant
        for j in range(i+1, N):
            if t[j] < t[i_min]:
                i_min = j
        if i_min != i:
            # échanger t[i] et t[i_min]
            t[i], t[i_min] = t[i_min], t[i]
    return t

Voici les états successifs du tableau après chaque tour de boucle avec en entrée [12, 15, 1, 3, 7]:

[1, 15, 12, 3, 7]
[1, 3, 12, 15, 7]
[1, 3, 7, 15, 12]
[1, 3, 7, 12, 15]

Correction de l'algorithme

L'invariant de boucle consiste à montrer que si les $i$ premiers éléments du tableau sont triés avant l'itération, alors les $i+1$ premiers éléments seront triés après une itération.

1. Initialisation: Au départ, $i = 0$, le sous-tableau trié de gauche ne contient aucun élément []. Il est donc forcément trié.
2. Conservation: Lorsqu'on considère le tour de boucle $i$, le tableau est déjà trié pour les indices $0$ à $i-1$. Grâce à la boucle interne, on trouve le plus petit élément parmi les éléments d'indice $i$ à $n$ (tous plus grands que l'élément d'indice $i-1$), et on le place à l'indice $i$. Après le tour de boucle, le tableau sera donc trié pour les indices de $0$ à $i$.
3. Terminaison: la boucle se termine lorsqu'on arrive à l'avant-dernier élément du tableau. Le tableau est trié pour les éléments d'indice $0$ à $n-2$, et le dernier élément d'indice $n-1$ est forcément plus grand que l'élément d'indice $ $n-2$. Le tableau est donc entièrement trié.

def tri_insertion(t: list):
    N = len(t)
    for i in range(1, N):
        x = t[i]
        j = i
        while j > 0 and t[j-1] > x:
            t[j] = t[j-1]
            j = j - 1
        t[j] = x
    return t