16 - TD Algorithmique

Réponse : C. Un parcours séquentiel visite chaque élément une seule fois, soit $n$ opérations. La complexité est linéaire.

• A est faux : $O(1)$ signifie un temps constant (indépendant de $n$), ce qui n’est possible que si on connaît directement la position.
• B est faux : $O(\log n)$ est la complexité de la recherche dichotomique (dans un tableau trié).
• D est faux : $O(n^2)$ correspond à des algorithmes avec deux boucles imbriquées (comme le tri par sélection).

Réponse : B. La terminaison garantit que l’algorithme ne boucle pas indéfiniment.

• A est faux : c’est la correction (pas la terminaison).
• C est faux : la complexité mesure le temps d’exécution, pas la terminaison.
• D est faux : les tests vérifient empiriquement, mais ne prouvent rien.

Réponse : B. Un variant est une quantité entière positive qui décroît strictement à chaque itération. Quand elle atteint 0, la boucle s’arrête.

• A est faux : l’invariant sert à prouver la correction, pas la terminaison.
• C est faux : une assertion vérifie une condition à un instant donné, elle ne prouve pas la terminaison.
• D est faux : un test unitaire vérifie un cas particulier.

Réponse : C. La dichotomie compare l’élément cherché au milieu du tableau pour éliminer une moitié. Cela ne fonctionne que si le tableau est trié.

• A est faux : la taille n’a pas d’importance.
• B est faux : la dichotomie fonctionne avec tout type comparable (flottants, chaînes, etc.).
• D est faux : les doublons ne gênent pas la recherche.

def est_element(a, L):
    """Renvoie True si a est dans L, False sinon."""
    for element in L:
        if element == a:
            return True
    return False

assert est_element(3, [1, 2, 3]) == True
assert est_element(5, [1, 2, 3]) == False
assert est_element(1, []) == False

1. Terminaison : la boucle for parcourt une liste de longueur finie, elle se termine toujours. Le variant est le nombre d’éléments restant à parcourir.
2. Correction : si a est dans L, il sera comparé à un moment et la fonction renverra True. Si a n’est pas dans L, toutes les comparaisons échoueront et la fonction renverra False.
3. Complexité : au pire (élément absent ou en dernière position), on effectue $n$ comparaisons : $O(n)$.

def moyenne(L):
    """Calcule la moyenne d'une liste non vide."""
    assert len(L) > 0, "La liste ne doit pas être vide"
    total = 0
    for x in L:
        total += x
    return total / len(L)

# Test avec des températures (en °C)
temps = [12.5, 14.0, 11.3, 15.8, 13.2]
assert abs(moyenne(temps) - 13.36) < 0.01

Terminaison : la boucle for parcourt une liste finie. Correction : à la fin, total contient la somme de tous les éléments, et on divise par le nombre d’éléments. Complexité : $O(n)$ (un seul parcours).

def indice_min(L):
    """Renvoie l'indice du plus petit élément de L."""
    assert len(L) > 0
    i_min = 0
    for i in range(1, len(L)):
        if L[i] < L[i_min]:
            i_min = i
    return i_min

temps = [11.2, 10.8, 12.1, 10.5, 11.7]
i = indice_min(temps)
print(f"Coureur le plus rapide : n°{i+1} avec {temps[i]} s")
# Coureur le plus rapide : n°4 avec 10.5 s

Terminaison : variant $n - i$, décroît de 1 à chaque itération.

Correction (invariant) : à l’entrée de la boucle pour l’indice $i$, i_min contient l’indice du minimum de L[0:i]. Cet invariant est maintenu car on met à jour i_min si L[i] < L[i_min]. À la fin ($i = n$), i_min est l’indice du minimum de toute la liste.

Complexité : $O(n)$ (un seul parcours, une comparaison par élément).

1. Terminaison : le variant est $n - i$. À chaque itération, $i$ augmente de 1 donc $n - i$ décroît de 1. Comme $n - i$ est un entier initialement positif (si $n \geq 0$), il atteint 0 en au plus $n$ itérations.

2. Trace de factorielle(4) :

Résultat : $f = 24 = 4!$ ✓

3. Invariant $f = i!$ :

• Initialisation : avant la boucle, $i = 0$ et $f = 1 = 0!$ ✓
• Conservation : si $f = i!$ au début d’un tour, alors après le tour : $i’ = i + 1$ et $f’ = f \times i’ = i! \times (i+1) = (i+1)! = i’!$ ✓

4. Correction : à la sortie de la boucle, $i = n$ (car la condition i < n est fausse). Par l’invariant, $f = i! = n!$. Donc factorielle(n) renvoie bien $n!$.

def dichotomie(L, x):
    """Recherche dichotomique de x dans L triée."""
    g = 0
    d = len(L) - 1
    while g <= d:
        m = (g + d) // 2
        if L[m] == x:
            return True
        elif L[m] < x:
            g = m + 1
        else:
            d = m - 1
    return False

Trace pour x = 23 :

Trouvé en deux étapes (au lieu de six en séquentiel).

Terminaison : le variant est $d - g + 1$ (taille de l’intervalle de recherche). À chaque itération, soit $g$ augmente, soit $d$ diminue. Le variant décroît strictement et est toujours positif tant que $g \leq d$.

Complexité : à chaque itération, l’intervalle est divisé par 2. Au bout de $k$ itérations, l’intervalle contient au plus $n / 2^k$ éléments. On s’arrête quand $n / 2^k \leq 1$, soit $k \leq \log_2(n)$. La complexité est $O(\log n)$.

# Tests
L = [2, 5, 8, 12, 16, 23, 38, 42]
assert dichotomie(L, 23) == True
assert dichotomie(L, 2) == True
assert dichotomie(L, 42) == True
assert dichotomie(L, 10) == False
assert dichotomie(L, 0) == False

def recherche_seq(annuaire, nom):
    for n, numero in annuaire:
        if n == nom:
            return numero
    return None

def recherche_dicho(annuaire, nom):
    g, d = 0, len(annuaire) - 1
    while g <= d:
        m = (g + d) // 2
        if annuaire[m][0] == nom:
            return annuaire[m][1]
        elif annuaire[m][0] < nom:
            g = m + 1
        else:
            d = m - 1
    return None

3. Pour trouver "Petit" (dernier élément) :

• Séquentiel : cinq comparaisons (on parcourt tout).
• Dichotomie : trois comparaisons au maximum ($\lceil \log_2(5) \rceil = 3$).

4. Pour un million d’entrées :

• Séquentiel : jusqu’à $1,000,000$ comparaisons.
• Dichotomie : $\lceil \log_2(1,000,000) \rceil = 20$ comparaisons au maximum.

La dichotomie est incomparablement plus efficace sur de grands ensembles triés.