Objectifs

savoir lire et concevoir un algorithme ;
savoir analyser un algorithme simple pour déterminer sa complexité dans le pire des cas et prouver sa correction ;
savoir implémenter des algorithmes en Python.

Chapitres

Codage et complexité. Codage des données, taille d’une donnée, notion de complexité dans le pire des cas d’un algorithme donné, utilisation de la notation $O$ .
Tris naïfs. Exemples d’algorithmes de tris non efficaces (tri à bulle, tri par insertion).
Récursivité. Introduction des stratégies usuelles de résolution de problèmes par programmation récursive, paradigme “diviser pour régner”. Exemple du tri fusion.
Programmation dynamique.
Structures de données. Introduction des notions de piles et files, exemple d’implémentation en Python.

Thèmes supplémentaires. Au choix parmi, par exemple :

structures de données plus avancées telles que les tas ;
algorithmes simples sur les graphes ;
algorithmes gloutons.

Laboratoire visuel : les tris

Suivez pas à pas les tris à bulles, par sélection et par insertion, puis comparez leur nombre d’opérations sur des listes aléatoires.

Le tri à bulles suit ce code :

def tri_bulles(L):
    n = len(L)
    for k in range(n - 1):
        for j in range(n - 1 - k):
            if L[j] > L[j + 1]:
                L[j], L[j + 1] = L[j + 1], L[j]
    return L

Le tri par sélection suit ce code :

def tri_selection(L):
    n = len(L)
    for i in range(n - 1):
        p = i
        for j in range(i + 1, n):
            if L[j] < L[p]:
                p = j
        L[i], L[p] = L[p], L[i]
    return L

Le tri par insertion suit ce code :

def tri_insertion(L):
    n = len(L)
    for i in range(1, n):
        x = L[i]
        j = i - 1
        while j >= 0 and L[j] > x:
            L[j + 1] = L[j]
            j = j - 1
        L[j + 1] = x
    return L

Suivez chaque comparaison et chaque échange ou écriture. Les étiquettes au-dessus des cases montrent où pointent les indices du code ; la zone verte est définitive pour les bulles et la sélection, et triée pour l’insertion.

Algorithme

Petit tableau d'entiers

Jusqu'à 10 entiers, séparés par des virgules ou des espaces.

Essayer :

Tableau initial

comparées échangées zone définitive

Vitesse

Comparer sur des listes aléatoires

Choisissez une taille N. Pour chaque essai, les trois méthodes sont évaluées sur la même liste ; le graphique conserve les moyennes obtenues pour chaque taille testée.

Taille N de chaque liste

Entiers tirés entre 0 et 999 : 1 000 listes si N ≤ 100, 500 si N ≤ 10 000, puis 100. N doit être compris entre 1 et 100 000.

Aucun test effectué.

Une opération = une comparaison de valeurs, un échange (même avec soi-même), ou une écriture dans L pour l’insertion (décalage ou insertion de x). Les tests de boucle ne sont pas comptés. Au-delà de N = 200, les comptes sont calculés exactement : N(N − 1)/2 comparaisons pour les bulles et la sélection, N − 1 échanges pour la sélection, et autant d’échanges que d’inversions pour les bulles. Pour l’insertion : une écriture par inversion, plus N − 1 insertions ; une comparaison par inversion, plus un test d’arrêt pour chaque valeur qui n’est pas un nouveau minimum strict.

Taille N	Listes	Tri à bulles · moyenne	Tri par sélection · moyenne	Tri par insertion · moyenne

Les compteurs suivent les versions de code/tri_bulles.py, code/tri_selection.py et tri_insertion : seules les comparaisons de valeurs et les échanges ou écritures dans L sont comptés.

Laboratoire visuel : recherche dichotomique

Dans une liste triée par ordre croissant, cherchez une valeur en réduisant à chaque étape l’intervalle où elle peut se trouver.

def recherche_dichotomique(L, x):
    d = 0
    f = len(L) - 1
    while d <= f:
        m = (d + f) // 2
        if L[m] == x:
            return m
        if L[m] < x:
            d = m + 1
        else:
            f = m - 1
    return -1

La liste doit être triée par ordre croissant. Suivez les bornes d et f et le milieu m : chaque comparaison permet de trouver x ou d’éliminer une partie de l’intervalle.

Intervalle initial

milieu examiné cases éliminées valeur trouvée

Vitesse