Les variantes de boucle

Les variantes de boucle

Qu'est-ce qu'une variante de boucle ?

Lorsque nous concevons des algorithmes itératifs, nous devons nous assurer qu'ils se terminent effectivement. La variante de boucle est un outil fondamental pour prouver la terminaison d'une boucle.

Alors que l'invariant de boucle nous aide à prouver l'exactitude partielle ("si la boucle se termine, elle produit le bon résultat"), la variante de boucle nous aide à prouver la terminaison ("la boucle se termine effectivement").

Invariant vs Variante

  Exemple 1 : Boucle for simple

Considérons le programme de somme des entiers déjà étudié :

def somme(n):
    s = 0
    for i in range(1, n+1):
        s += i
    return s

Variante de boucle :

Vérification des propriétés :

• Positivité : Au début de la boucle, \(i = 1\), donc \(v = n\). Pendant la boucle, \(i \le n\), donc \(v \ge 1\). La variante est toujours positive.
• Décroissance stricte : À chaque itération, \(i\) est incrémenté de 1, donc \(v\) diminue exactement de 1. La valeur décroît strictement.
• Borne inférieure : Lorsque \(v\) atteint 0 (c'est-à-dire \(i = n+1\)), la boucle se termine. On a une garantie de terminaison.

  Exemple 2 : Recherche dichotomique

Considérons l'algorithme de recherche dichotomique dans un tableau trié :

def recherche_dichotomique(tab, x):
    debut = 0
    fin = len(tab) - 1
    
    while debut <= fin:
        milieu = (debut + fin) // 2
        if tab[milieu] == x:
            return milieu
        elif tab[milieu] < x:
            debut = milieu + 1
        else:
            fin = milieu - 1
    
    return -1

Variante de boucle :

Vérification des propriétés :

• Positivité : La condition de boucle \(\text{debut} \le \text{fin}\) garantit que \(v \ge 1\).
• Décroissance stricte: À chaque itération, on remplace l'intervalle courant par sa moitié gauche ou droite :
  • Si on cherche dans la moitié gauche : \(\text{fin}\) devient \(\text{milieu} - 1\)
  • Si on cherche dans la moitié droite : \(\text{debut}\) devient \(\text{milieu} + 1\)
  Dans les deux cas, la taille du nouvel intervalle est strictement inférieure à la taille de l'intervalle précédent (au moins divisée par 2).
• Borne inférieure : La taille de l'intervalle ne peut pas devenir négative. Lorsqu'elle atteint 0, la condition de boucle \(\text{debut} \le \text{fin}\) devient fausse et la boucle se termine.

  Exemple 3 : Algorithme d'Euclide (PGCD)

L'algorithme d'Euclide calcule le plus grand commun diviseur de deux entiers :

def pgcd(a, b):
    while b != 0:
        r = a % b
        a = b
        b = r
    return a

Variante de boucle :

Vérification des propriétés :

• Positivité : La condition de boucle \(b \neq 0\) garantit que \(v > 0\).
• Décroissance stricte : À chaque itération, \(b\) devient \(a \mod b\). Par définition du modulo, \(0 \le a \mod b < b\). Donc la nouvelle valeur de \(b\) est strictement inférieure à l'ancienne.
• Borne inférieure : \(b\) est un entier positif qui décroît strictement. Il ne peut pas décroître indéfiniment ; il finira par atteindre 0, ce qui termine la boucle.

  Exemple 4 : Parcours en profondeur (DFS) avec pile explicite

Considérons un parcours en profondeur d'un graphe utilisant une pile :

def dfs_iteratif(graphe, depart):
    visites = set()
    pile = [depart]
    
    while pile:
        sommet = pile.pop()
        if sommet not in visites:
            visites.add(sommet)
            for voisin in graphe[sommet]:
                if voisin not in visites:
                    pile.append(voisin)
    return visites

Variante de boucle :

Ici, la terminaison est garantie par le fait que :

• Chaque sommet ne peut être ajouté à la pile que s'il n'a pas déjà été visité.
• Le nombre total de sommets est fini.

Vérification des propriétés :

• Positivité : \(v\) est positif tant qu'il reste des sommets à visiter.
• Décroissance stricte : À chaque fois qu'on visite un nouveau sommet (ajout à l'ensemble visites), \(v\) diminue de 1. Bien que la pile puisse contenir plusieurs éléments, le nombre de sommets non visités décroît strictement à chaque nouvelle découverte.
• Borne inférieure : \(v\) ne peut pas devenir négatif. Lorsqu'il atteint 0, tous les sommets accessibles ont été visités et la pile finira par se vider.

Cas particuliers et pièges à éviter

  Contre-exemple : boucle infinie

def boucle_dangereuse(n):
    i = 0
    while i < n:
        # Oubli d'incrémenter i !
        # La variante (n - i) ne décroît jamais
        print(i)

Ici, la variante \(v = n - i\) ne décroît pas car \(i\) n'est pas modifié. La boucle est infinie.

Récapitulatif des variantes étudiées

Comment trouver une variante ?

Exercices d'application

  Exercice 1 : Puissance itérative

def puissance(x, n):
    resultat = 1
    for _ in range(n):
        resultat *= x
    return resultat

Question : Quelle est la variante de boucle ? Démontrez les trois propriétés.

  Exercice 2 : Tri à bulles

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

Question : Identifiez les variantes pour les deux boucles imbriquées.

Comparaison finale : Invariant vs Variante