Concevoir une boucle

Les variables de boucle

La possibilité d'écrire des boucles d'instructions est un élément fondamental des langages de programmation. Comme dans beaucoup de langages, une boucle en Python est structurée autour du mot-clé while.

<INIT>
While <CONDITION>:
    <ITERATION>

<ITERATION> est le bloc d'instructions qui est répété à l'identique tant que l'expression <CONDITION> est vraie. Pour que la boucle puisse se terminer il faut que l'expression <CONDITION> finisse par devenir fausse. Pour cela il faut que quelque chose change, évolue, à chaque itération. Ce quelque chose se matérialise par une ou plusieurs variables de boucle.

<Initialisation des variables de boucle>
While <Condition sur les variables de boucles>:
    <Modification des variables de boucle>

Exemple : Écrivons une fonction moy(n) qui calcule la moyenne des carrés parfaits inférieurs à n.

moy(12) vaut 3.5 car $\frac{1}{4}(0+1+4+9)=3.5$

In [ ]:
def moy(n):
    """ Retourne la moyenne des carrés parfaits inférieurs
        à n.
    """
    s = 0               #5
    k = 0               #6
    while k**2 < n:     #7
        s = s + k**2    #8
        k = k + 1       #9
    m = s / k           #10
    return m            #11

moy(12)
Out[ ]:
3.5

Dans le code ci-dessus, seules k et s changent au fil des itérations. Ceux sont les deux variables de boucle.

  • Les variables de boucle doivent être correctement initialisées. Ceci est fait lignes 5 et 6.
  • Le but des instructions itérées (lignes 8 et 9) est de faire évoluer les variables de boucle.
  • La condition de continuation de la boucle est l'expression k**2 < n. Cette condition porte ici uniquement sur la variable de boucle k.

Invariant de boucle

On appelle invariant de boucle une propriété qui dépend des variables de boucle mais qui cependant demeure vraie à chaque itération. La notion d'invariant de boucle est un outil conceptuel efficace pour concevoir une boucle avec méthode et pour justifier que cette boucle est correcte.

Illustrons ceci sur l'exemple simple où l'on souhaite écrire une fonction qui calcule la factorielle d'un entier $n$. L'utilité du concept d'invariant de boucle peut sembler douteuse ici en raison de la simplicité de l'exemple. Mais la démarche exposée ci-dessous sera identique et prendra tout son intérêt lorsque nous aurons à concevoir des boucles plus complexes.

Conception de la boucle

Pour calculer pas à pas le produit des $n$ facteurs il faut mémoriser à chaque itération le produit partiel p obtenu jusqu'ici ainsi qu'un entier k qui permet de savoir le travail qu'il reste à effectuer. k et p sont les deux variables de boucle. On peut concevoir la boucle en cherchant à maintenir vraie la propriété

$$p\times k!=n!$$

avec l'idée de faire passer petit à petit les facteurs de $k!$ dans le produit $p$.

Il reste maintenant à construire la boucle en ayant cet invariant en tête :

  • Quelles sont les instructions à itérer pour maintenir l'invariant de boucle ?
  • À quelle condition la boucle doit-elle se terminer ?
  • Quelles doivent-être les valeurs initiales des variables de boucle ?

Écriture de la boucle

In [ ]:
def fact(n):
    """ Retourne la factorielle de l'entier n.
    """
    p = 1
    k = n
    while k != 0:
        # Propriété : p * k! = n!
        p = p * k                     #8
        k = k - 1                     #9
    return p

fact(5)

Preuve de correction de la boucle

La propriété $p\times k!=n!$ est bien un invariant de boucle car :

  • La propriété est satisfaite au début de la première itération puisque $1\times n!=n!$.

  • Les instructions itérées lignes 8 et 9 maintiennent vraie la propriété d'une itération à l'autre puisque $p\times k!=(p\times k)\times (k-1)!$.

Pour démontrer que la fonction retourne bien la factorielle de $n$ il faut en particulier justifier que la boucle n'est pas infinie, c'est-à-dire que la condition de continuation k != 0 n'est pas éternellement vraie. Ceci est évident ici car l'instruction k = k - 1 assure que l'entier k diminue d'une unité à chaque itération.

En sortie de boucle nous pouvons affirmer que :

  • L'invariant de boucle est satisfait : $p\times k!=n!$
  • La condition de continuation est fausse : $k=0$

L'association de ces deux énoncés donne $p=n!$ ce qui prouve que la fonction fact retourne la bonne valeur.

En résumé

  1. On cherche à traduire l'idée de la boucle sous la forme d'un invariant de boucle.
  2. On écrit la boucle en s'appuyant sur l'invariant de boucle
  3. On démontre la correction de la boucle :
    • on montre que la propriété est bien un invariant de boucle en raisonnant par récurrence
    • on montre que la boucle se termine, par exemple en mettant en évidence une quantité entière strictement décroissante.
    • on combine l'invariant de boucle et la condition de sortie de boucle pour justifier que la boucle est correcte.

Application : Recherche par dichotomie

L'utilité de l'invariant de boucle va être manifeste dans ce problème non trivial. Le problème consiste à retrouver l'indice où se trouve une valeur x dans une liste L triée dans l'ordre croissant. Voici plus précisément la docstring de la fonction :

def index(L, x):
    """ Retourne le plus petit indice j tel que L[j] >= x.
        Retourne -1 si L[j] < x pour tout j.
    """

Par exemple :

index([4, 6, 7, 12, 24], 2)   retourne 0
index([4, 6, 7, 12, 24], 7)   retourne 2
index([4, 6, 7, 12, 24], 10)  retourne 3
index([4, 6, 7, 12, 24], 27)  retourne -1

Une façon simple de réaliser cette fonction est de parcourir la liste L jusqu'à obtenir une valeur supérieure ou égale à x.

In [ ]:
def index(L, x):
    """ Retourne le plus petit indice j tel que L[j] >= x.
        Retourne -1 si L[j] < x pour tout j.
    """
    n = len(L)
    i = 0
    while i < n and L[i] < x:
        i = i + 1
    if i == n:
        return -1
    else:
        return i

        
index([4, 6, 7, 12, 24], 10)
Out[ ]:
3

Ce code est correct : il retourne bien la valeur spécifiée par la docstring. Cependant il est possible d'exploiter le fait que les éléments de L sont ordonnés pour écrire un code bien plus efficace. L'idée est d'effectuer une recherche par dichotomie. Cette idée consiste à lire la valeur centrale de la liste afin de savoir de quel côté se trouve l'indice recherché. On réapplique ensuite la même idée sur l'une des deux moitiés de liste, etc.

Le principe de la dichotomie est simple à comprendre. Par contre, il faut être méticuleux dans l'écriture du code. Il s'agit de retourner le plus petit indice i tel que L[i] >= x et non pas le plus grand indice. L'inégalité est large et non pas stricte. Sans méthode il est facile de commettre une erreur. Et d'ailleurs, comment être certain qu'il n'y a pas d'erreurs dans le code que nous aurons écrit.

Nous allons programmer la boucle en utilisant deux variables de boucle u et v. Notre idée est qu'au début de chaque étape nous savons que l'indice $i$ est à rechercher dans l'intervalle $[u,\,v]$. Autrement dit nous savons que :

$$\forall k\quad k\lt u \Longrightarrow \text{L}[k]\lt x \quad\text{et}\quad k\geq v \Longrightarrow \text{L}[k]\geq x\quad\quad(P)$$

État d'avancement au début d'une itération

Les instructions à itérer vont consister à lire la valeur au milieu de l'intervalle $[\,u,\,v]$ et à faire évoluer correctement les variables de boucle u et v.

L'état final (condition d'arrêt de la boucle) doit correspondre à la situation où l'on sait pour tout $k$ si $L[k]\lt x$ ou si $L[k]\geq x$.

État final

L'état initial correspond à la situation où l'on a encore aucune information sur les éléments de $L$ :

État initial

Nous avons maintenant tous les éléments pour coder méthodiquement notre algorithme itératif.

In [ ]:
def index(L, x):
    """ Retourne le plus petit indice i tel que L[i] >= x.
        Retourne -1 si L[i] < x pour tout i.
        
        Les éléments de L sont supposés être ordonnés par
        ordre croissant.
    """
    n = len(L) 
    u = 0
    v = n
    while u < v:
        # Pour tout indice k
        # Si k < u alors L[k] < x
        # Si k >= v alors L[k] >= x
        m = (u + v) // 2               #15
        if L[m] < x:                   #16
            u = m + 1                  #17
        else:                          #18
            v = m                      #19
    if v == n:
        return -1
    else:
        return v
        
index([2, 6, 7, 12, 24], 10)
Out[ ]:
3

Preuve de la correction de la fonction index :

Montrons que la propriété

$$\forall k\quad k\lt u \Longrightarrow \text{L}[k]\lt x \quad\text{et}\quad k\geq v \Longrightarrow \text{L}[k]\geq x\quad\quad(P)$$

est un invariant de boucle, c'est-à-dire qu'elle est satisfaite au début de chaque itération.

Au début de la première itération $u=0$ et $v=n$. Il n'existe aucun indice $k$ tel que $k\lt 0$ ni aucun indice $k$ tel que $k\geq n$. La propriété $(P)$ est donc trivialement vraie dans ce cas.

Si la propriété $(P)$ est satisfaite au début d'une itération, il est clair que les instructions des lignes 15 à 19 la maintiennent vraie pour l'itération suivante car la liste des éléments est croissante.

Ceci prouve que la propriété $(P)$ est bien un invariant de boucle.

Montrons que la boucle se termine.

Tant que $u\lt v$ on a $u\leq \left\lfloor\frac{u+v}{2}\right\rfloor\lt v$ et donc $u\lt m+1$ et $m\lt v$. Les instructions des lignes 16-19 garantissent donc que l'entier $v-u$ est strictement décroissant ce qui assure que la condition $u\lt v$ sera fausse au bout d'un nombre fini d'itérations. Ceci prouve que la boucle se termine.

Montrons que la fonction retourne la bonne valeur.

En sortie de boucle la propriété (P) est satisfaite et la condition de continuation est fausse. On a donc :

$$u\geq v\quad\text{et}\quad\forall k\lt u\quad \text{L}[k]\lt x \quad\text{et}\quad \forall k\geq v \quad \text{L}[k]\geq x$$

Ceci n'est possible que si $u=v$ et on a ainsi :

$$\quad\forall k\lt v \quad \text{L}[k]\lt x \quad\text{et}\quad\forall k\geq v \quad \text{L}[k]\geq x$$
  • Si $v=n$ cela signifie que tous les éléments de L sont strictement inférieurs à $x$.
  • Sinon, cela signifie que $v$ est le plus petit indice tel que $\text{L}[v]\geq x$.

Dans ces deux cas, la fonction retourne donc bien la bonne valeur.