Aller au contenu principal

TD2 – Application : variants et invariants

Objectifs
  1. Identifier un variant de boucle ;
  2. Comprendre et formuler un invariant de boucle ;
  3. utiliser les étapes initialisation / maintenance / terminaison pour raisonner sur un algorithme.

Variant de boucle : test de palindrome​

On considère un algorithme qui permet de vérifier si un mot est un palindrome, c’est-à-dire un mot qui se lit dans les deux sens.

def palindrome(mot) :
    i = 0
    j = len(mot)-1
    pal = True
    while i <= j and pal == True :
        if mot[i] == mot[j] :
            i = i+1
            j = j-1
        else :
            pal = False
    return pal

Principe de l’algorithme :

  • une variable i commence au début du mot ;
  • une variable j commence à la fin du mot ;
  • on compare les caractères situés aux positions i et j ;
  • si les caractères sont identiques, on avance i et on recule j ;
  • sinon, le mot n’est pas un palindrome.

Identifier le variant​

  1. Quelle(s) variable(s) évoluent à chaque tour de boucle ?
  2. Expliquer pourquoi ces variables garantissent l’arrêt de la boucle.

Tracer l’exécution de l’algorithme​

  1. Compléter les tableaux suivants.

    Mot étudié : radar

    Exécutionijpal
    Initialisation0vrai
    Tour 1
    Tour 2
    Tour 3

  2. Pour quel mot l’algorithme s’arrête-t-il avec pal = vrai ?

  3. En quoi l’évolution de i et j constitue-t-elle un variant de boucle ?

Invariant de boucle : calcul d’une puissance de 2​

def puissance(n):
    p = 1
    for k in range(n):
        p = p*2
    return p

On considère un algorithme qui :

  • initialise une variable p à 1 ;
  • répète n fois une multiplication par 2 ;
  • renvoie la valeur finale de p.

Invariant proposé​

On propose l’invariant suivant :

À chaque début d’itération, la variable p est égale à 2 exposant le nombre d’itérations déjà effectuées.

Vérification de l’invariant​

En suivant la méthode du cours, expliquer pourquoi cet invariant est correct :

  1. Initialisation
    Que vaut p avant le premier tour de boucle ?
  2. Maintenance
    Pourquoi l’invariant reste-t-il vrai après un tour de boucle ?
  3. Terminaison
    Que vaut p lorsque la boucle se termine ?
    Quelle valeur est alors renvoyée par l’algorithme ?

Invariant de boucle : tri par sélection​

Le tri par sélection consiste à :

  • chercher le plus petit élément d’une liste ;
  • l’échanger avec le premier élément ;
  • recommencer le même procédé à partir de la deuxième position, puis de la troisième, etc.

Comprendre le fonctionnement​

  1. Dessiner les différentes étapes permettant de trier la liste suivante avec le tri par sélection :
    [5, 3, 9, 1, 7]

Invariant du tri par sélection​

On propose l’invariant suivant :

À chaque début d’itération, la partie gauche de la liste est triée et contient les plus petits éléments.

3. Vérification de l’invariant​

À l’aide du tableau ci-dessous, répondre aux questions.

iÉtat de la liste
05 9 -1 2 7
1-1 9 5 2 7
2-1 2 5 9 7
3-1 2 5 7 9
4-1 2 5 7 9
  1. Initialisation
    Pourquoi l’invariant est-il vrai au début de l’algorithme ?
  2. Maintenance
    Expliquer pourquoi l’échange effectué à chaque étape conserve l’invariant.
  3. Terminaison
    Pourquoi peut-on affirmer que la liste est triée à la fin de l’algorithme ?
  4. Écrire l'algorithme du tri par sélection.