27 - Algorithmique

Les exercices se font dans Thonny, dans le fichier 27_algorithmique.py.

Cours associé : 19 - Dichotomie .

Exercice 1 : QCM – vérification des prérequis

Pour chaque question, une seule réponse est correcte.

1. Quelle est la complexité d’un parcours séquentiel d’une liste de $n$ éléments ?

• A. $O(1)$
• B. $O(\log n)$
• C. $O(n)$
• D. $O(n^2)$

Correction publiée après la séance.

2. Que signifie « prouver la terminaison » d’un algorithme ?

• A. Vérifier qu’il donne le bon résultat
• B. Montrer qu’il finit toujours en un nombre fini d’étapes
• C. Calculer sa complexité
• D. Écrire ses tests

Correction publiée après la séance.

3. Pour prouver la terminaison d’une boucle while, on utilise :

• A. Un invariant de boucle
• B. Un variant de boucle
• C. Une assertion
• D. Un test unitaire

Correction publiée après la séance.

4. La recherche dichotomique nécessite que le tableau soit :

• A. De taille paire
• B. Constitué d’entiers
• C. Trié
• D. Sans doublons

Correction publiée après la séance.

Exercice 2 : recherche séquentielle pas à pas

On considère la fonction suivante :

def chercher(L, x):
    for i in range(len(L)):
        if L[i] == x:
            return True
    return False

1. Recopier et compléter la trace de chercher([3, 8, 1, 7, 5], 7). La première ligne est donnée.

2. Combien de tours la boucle fait-elle pour chercher([3, 8, 1, 7, 5], 4) ? Que renvoie la fonction ?

   Indice

   4 est-il dans la liste ? Si la condition L[i] == x n’est jamais vraie, la boucle va jusqu’au bout de range(len(L)), puis la fonction exécute la ligne qui suit la boucle.

3. Pourquoi la boucle se termine-t-elle toujours ? Donner un variant.

   Indice

   Un variant est un entier positif qui diminue à chaque tour. Ici, i augmente de 1 à chaque tour sans pouvoir dépasser len(L) : quelle quantité, calculée avec len(L) et i, diminue alors à chaque tour ?

4. Pour une liste de $n$ éléments, combien de comparaisons faut-il au pire ? Dans quel cas ?

   Indice

   Le pire cas est celui où la boucle fait le plus de tours : que doit-il se passer pour que tous les éléments soient comparés à x ?

Correction publiée après la séance.

Exercice 3 : parcours séquentiel guidé

3.1 Recherche d’un élément

Compléter la fonction suivante, puis répondre aux questions :

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

1. La boucle se termine-t-elle toujours ? Quel est le variant ?

   Indice

   Combien de tours fait au plus une boucle for qui parcourt une liste ? Le variant mesure ce qui reste à faire : quelle quantité diminue de 1 à chaque tour ?

2. L’algorithme est-il correct ? Justifier.

   Indice

   Examiner les deux cas : a est dans L, et a n’est pas dans L. Dans chacun, que renvoie la fonction, et est-ce le résultat attendu ?

3. Quelle est la complexité au pire cas ?

   Indice

   Compter les comparaisons == a quand a est absent de L : combien y en a-t-il pour une liste de $n$ éléments ?

Correction publiée après la séance.

3.2 Calcul de moyenne (météo)

Écrire une fonction moyenne(L) qui calcule la moyenne d’une liste de flottants (par exemple des températures). Déterminer sa complexité.

def moyenne(L):
    total = 0
    for x in L:
        total = ...
    return ...

Correction publiée après la séance.

Exercice 4 : recherche d’un extremum (sport)

Le tableau suivant donne les temps (en secondes) de cinq coureurs sur un 100 m : [11.2, 10.8, 12.1, 10.5, 11.7]

1. Écrire une fonction indice_min(L) qui renvoie l’indice du minimum d’une liste (sans utiliser min() ni index()).

   Indice

   Garder l’indice i_min du plus petit élément vu jusqu’ici, en partant de 0. Parcourir les indices suivants et mettre i_min à jour quand L[i] est plus petit que L[i_min].

   Code à copier puis compléter

   def indice_min(L):
       i_min = 0
       for i in range(1, len(L)):
           if ...:
               i_min = ...
       return i_min
   

2. En déduire le numéro du coureur le plus rapide.

   Indice

   Le plus rapide a le plus petit temps. Les indices commencent à 0, alors que les coureurs sont numérotés à partir de 1.

3. Prouver la terminaison et la correction. Déterminer la complexité.

   Indice

   Terminaison : quelle quantité entière diminue à chaque tour de la boucle ? Correction : que contient i_min après le tour qui a examiné l’élément d’indice i ? Cette propriété, vraie à chaque tour, est un invariant.

Correction publiée après la séance.

Exercice 5 : invariant et correction – factorielle

On considère le programme suivant :

def factorielle(n):
    i = 0
    f = 1
    while i < n:
        i = i + 1
        f = f * i
    return f

1. Justifier que la boucle n’est pas infinie (donner le variant).

   Indice

   Comment évolue i à chaque tour, et quand la condition i < n devient-elle fausse ? Le variant est une quantité entière, calculée avec n et i, qui diminue de 1 à chaque tour.

2. Calculer factorielle(4) et vérifier que le résultat est $4! = 24$.

   Indice

   Dresser un tableau avec une ligne par tour, qui donne les valeurs de i et de f à la fin du tour : i passe de 0 à 4.

3. Montrer que $f = i!$ est un invariant de la boucle.

   Indice

   Deux étapes : vérifier que $f = i!$ est vrai avant le premier tour (que valent i et f ?), puis montrer que si $f = i!$ au début d’un tour, c’est encore vrai à la fin, après i = i + 1 et f = f * i.

4. En déduire que l’algorithme est correct (c’est-à-dire que factorielle(n) renvoie $n!$).

   Indice

   Que vaut i à la sortie de la boucle, quand i < n est devenu faux ? L’invariant donne alors la valeur de f.

Correction publiée après la séance.

Exercice 6 : recherche dichotomique

1. Écrire une fonction dichotomie(L, x) qui cherche la valeur x dans une liste triée L et renvoie True si elle est présente, False sinon.

   Indice

   Deux indices, g et d, délimitent la zone où x peut encore se trouver : au départ, toute la liste. Tant que cette zone n’est pas vide, comparer x à l’élément du milieu : s’il est égal, x est présent ; s’il est plus petit que x, poursuivre la recherche à droite du milieu, sinon à gauche.

   Code à copier puis compléter

   def dichotomie(L, x):
       g = 0
       d = len(L) - 1
       while g <= d:
           m = (g + d) // 2
           if L[m] == x:
               return ...
           elif L[m] < x:
               g = ...
           else:
               d = ...
       return False
   

2. Tracer l’exécution sur L = [2, 5, 8, 12, 16, 23, 38, 42] avec x = 23.

   Indice

   Faire un tableau avec une ligne par tour et les colonnes g, d, m, L[m], la comparaison et l’action. Au premier tour, g = 0, d = 7 et m = (0 + 7) // 2.

3. Prouver la terminaison (variant : $d - g$). Quelle est la complexité ?

   Indice

   À chaque tour, soit g augmente, soit d diminue, et la zone de recherche est coupée en deux. Combien de fois peut-on diviser $n$ par 2 avant d’arriver à moins de 1 ?

Correction publiée après la séance.

Exercice 7 : synthèse – annuaire téléphonique

Un annuaire est une liste de tuples (nom, numéro) triée par ordre alphabétique :

annuaire = [
    ("Dupont", "01 23 45 67 89"),
    ("Garcia", "06 12 34 56 78"),
    ("Lambert", "04 56 78 90 12"),
    ("Martin", "07 89 01 23 45"),
    ("Petit", "03 21 09 87 65"),
]

1. Écrire une fonction recherche_seq(annuaire, nom) qui cherche un nom par parcours séquentiel et renvoie le numéro (ou None).

   Indice

   Parcourir l’annuaire en déballant chaque tuple : for n, numero in annuaire:. Renvoyer le numéro dès que n est le nom cherché ; après la boucle, renvoyer None.

   Code à copier puis compléter

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

2. Écrire une fonction recherche_dicho(annuaire, nom) qui fait la même chose par dichotomie (le tableau est trié alphabétiquement).

   Indice

   Même algorithme que dichotomie à l’exercice 6, en comparant annuaire[m][0], le nom de la case du milieu, au nom cherché : les chaînes se comparent avec < dans l’ordre alphabétique. Quand le nom est trouvé, renvoyer annuaire[m][1].

   Code à copier puis compléter

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

3. Comparer le nombre de comparaisons effectuées pour trouver "Petit" avec chaque méthode.

   Indice

   Séquentiel : à quelle position se trouve "Petit" dans l’annuaire ? Dichotomie : suivre l’algorithme sur les cinq noms, comme dans la trace de l’exercice 6.

4. Si l’annuaire contenait un million d’entrées, combien de comparaisons faudrait-il au maximum avec chaque méthode ?

   Indice

   Séquentiel : dans le pire cas, on examine toutes les entrées. Dichotomie : combien de fois faut-il diviser un million par 2 pour arriver à 1 ? Comparer avec $2^{20}$, qui vaut environ un million.

Correction publiée après la séance.