Correction d’un programme

1. Notion de variant et d’invariant de boucle

Document élève

1.1. Objectif

L’objectif de cette activité est faire découvrir la notion de correction d’un programme, l’identification des variants et invariants de boucle et de la notion de complexité au travers d’un algorithme simple.

1.2. Prérequis

Utilisation de l’environnement de développement
Type élémentaire : les entiers
Structure algorithmique de base : boucle while

1.3. Conditions

Activité semi-débranchée
Niveau première
Type d’activité TD/TP
Durée : 3h

1.4. Rubriques du programme :

Algorithmique :
- Variant et invariant de boucle
- Cout unitaire et linéaire
Langage et programmation :
- Constructions élémentaires
- Spécification
- Mise au point

2. Introduction

Un programme peut être amené à manipuler un grand nombre de données dont les valeurs peuvent évoluer au cours de son exécution. Il est important de s’assurer que le programme réalise bien le traitement voulu et qu’il s’arrêtera en retournant le bon résultat. C’est par la correction du programme que l’on pourra s’en assurer. Cette correction consiste à trouver :

un variant de boucle : condition de sortie d’une boucle
un invariant de boucle : propriété logique qui reste vraie de l’entrée de la boucle jusqu’à sa sortie

3. Variant de boucle

Le variant de boucle est la variable qui croit ou décroit à chaque itération de la boucle. Cette variable comparée à une valeur constante doit permettre de mettre fin à la boucle après un nombre fini d’itérations.

for i in range(10):
    # faire quelque chose

i va croitre de 0 à 9 et la boucle prend fin après la 10ème itération.

    i = 0
    while i < 10:
        # faire quelque chose

4. Invariant de boucle

L’invariant de boucle est une propriété qui est vérifiée tout au long de l’exécution d’une boucle. Prenons l’exemple de la fonction ci-dessous qui retourne le quotient de la division entière de deux nombres entiers positifs et non nuls :

    def division_entiere(a : int, b : int) -> int:
    '''retourne quotient tel que a = b*quotient + reste'''
        if not (a>0 && b>0):
            return None
        reste = a
        quotient = 0
        while reste >= b:
            reste = reste - b
            quotient = quotient + 1
        return quotient

Etat des variables en entrée de boucle :
- a et b sont des entiers positifs non nuls
- \$reste = a\$ et \$quotient = 0\$
Definir un invariant de boucle :
- \$a = b*quotient + reste\$ devrait toujours être vérifié, ce serait donc notre invariant de boucle.
Avant d’entrer dans la boucle : \$a = b*quotient + reste\$ donne :
- \$a = b*0 + a = a\$ l’invariant est donc bien vérifié
Dans la boucle :
- à l’itération \$i\$, on a : \$a = b*quotient_i + reste_i\$
- à l’itération \$i+1\$, on a : \$a = b*(quotient_i + 1) + (reste_i - b)\$
- Soit : \$a = b*quotient_i + b + reste_i - b\$
- Donc : \$a = b*quotient_i + reste_i\$
- Conclusion : la propriété \$a = b*quotient + reste\$ est toujours vrai dans la boucle
A la sortie de la boucle :
- A la dernière itération on avait \$a = b*quotient_n + reste_n\$ et \$reste_n <= b\$
- La condition de bouclage n’est plus respectée, on sort de la boucle et la propriété \$a = b*quotient + reste\$ est toujours vrai
Conclusion : la propriété \$a = b*quotient + reste\$ est bien l’invariant de boucle. On peut certifier que la fonction donne bien le résultat attendu.

4.1. Exercices

Considérons la fonction suivante qui effectue la multiplication de deux nombres entiers a et b avec b>=0 :

def produit(a : int, b : int) -> int:
    '''Retourne produit = a*b avec b>=0'''
    if b<0:
        return None
    i = 0
    p = 0
    while i<b:
        p = p + a
        i = i + 1
    return p

Q1) Quelle variable constitue le variant de boucle ?

Q2) Faites tourner l’algorithme de la fonction produit(a,b) à la main et complétez le tableau suivant:

Itération Valeur de i Valeur de p Condition (i < b)

0

Vrai

1

2

3

…

i

…

i=b

Q3) En déduire l’invariant de boucle.

Considérons maintenant la fonction suivante qui effectue l’élévation à la puissance e d’un nombre n, e et n étant deux nombres entiers avec e>=0 :

def puissance(n : int, e : int) -> int:
    '''Retourne puissance = a^b avec b>=0'''
    if e<0:
        return None
    if e==0:
        return 1
    i = 0
    p = 1
    while i<e:
        p = p * n
        i = i + 1
    return p

Q4) Identifiez le variant et l’invariant de boucle en reprenant les questions Q1) à Q3).

Notebook des exercices

Q5) Dans votre environnement de développement, écrivez un programme qui utilisera la fonction produit(), qui demandera à l’utilisateur de fournir les nombre a et b et qui retournera le résultat de la fonction produit(a,b)

Q6) Ecrivez un programme qui utilisera la fonction puissance(), qui demandera à l’utilisateur de fournir les nombre n et e et qui retournera le résultat de la fonction puissance(n,e)

Correction

Q1) Le nombre i est un entier positif qui croit à chaque itération jusqu’à atteindre la valeur de b donc : i est le variant de boucle.

Q2)

Itération Valeur de i Valeur de p Condition (i < b)

0

Vrai

1

a

Vrai

2

2*a

Vrai

3

3*a

Vrai

…

i

i*a

Vrai

…

i=b

b

b*a

Faux

Q3) la relation p = a*i est un invariant de boucle. Elle est vraie à l’entrée de la boucle, durant les itérations dans la boucle et l’est toujours à la sortie de la boucle.

Q4) Le nombre i est un entier positif qui croit à chaque itération jusqu’à atteindre la valeur de b donc : i est le variant de boucle._En faisant tourner à la main l’algorithme de la fonction puissance() on obtient les états suivants :

Itération Valeur de i Valeur de p Condition (i < e)

0

1

Vrai

1

Vrai

2

n*n

Vrai

3

n*n*n=n^3

Vrai

…

i

n^i

Vrai

…

i=e

e

n^e

Faux

la relation p = n^i est un invariant de boucle. Elle est vraie à l’entrée de la boucle, durant les itérations dans la boucle et l’est toujours à la sortie de la boucle.

Q5) Programme qui utilise la fonction produit()

def produit(a : int, b : int) -> int:
    '''Retourne produit = a*b avec b>=0'''
    if b<0:
        return None
    i = 0
    p = 0
    while i<b:
        p = p + a
        i = i + 1
    return p

if __name__ == '__main__':
    a = int(input("Entrez le nombre a : "))
    b = int(input("Entrez le nombre b : "))
    print(f'p = {produit(a,b)}')

Q6) Programme qui utilise la fonction puissance()

def puissance(n : int, e : int) -> int:
    '''Retourne puissance = n^e avec e>=0'''
    if e<0:
        return None
    if e==0:
        return 1
    i = 0
    p = 1
    while i<e:
        p = p * n
        i = i + 1
    return p

if __name__ == '__main__':
    n = int(input("Entrez le nombre n : "))
    e = int(input("Entrez le nombre e : "))
    print(f'p = {puissance(n,e)}')

5. Test

En python l’instruction assert permet de rajouter des contrôles pour le débogage d’un programme. Ils sont un moyen systématique de vérifier que l’état interne d’un programme est conforme aux attentes du développeur, l’objectif étant de détecter les bogues. En particulier, ils sont utiles pour détecter les fausses hypothèses formulées lors de l’écriture du code. En outre, ils peuvent faire office de documentation en ligne en rendant évidentes les hypothèses du développeur.

Utilisation basique :

assert a_tester == valeur_attendue

Exemple :

a = 3
b = 5
p = a*b
assert p == 15  # le test passe : rien ne s'affiche
assert p == 14  # le test ne passe pas : affichage d'une exception

5.1. Exercices

Q7) Ajoutez dans les fonctions produit() et puissance() trois assertions permettant de vérifiez les invariants de boucle identifiés aux questions Q3) et Q4)

Correction

Q7) Pour la fonction produit() :

def produit(a : int, b : int) -> int:
    '''Retourne produit = a*b avec b>=0'''
    if b<0:
        return None
    i = 0
    p = 0
    assert p == a*i
    while i<b:
        p = p + a
        i = i + 1
        assert p == a*i
    assert p == a*i
    return p

if __name__ == '__main__':
    a = int(input("Entrez le nombre a : "))
    b = int(input("Entrez le nombre b : "))
    print(f'p = {produit(a,b)}')

Les assertions montrent que l’expression p = a*i est vraie à l’entrée de la boucle, durant les itérations dans la boucle et l’est toujours à la sortie de la boucle.

Pour la fonction puissance() :

def puissance(n : int, e : int) -> int:
    '''Retourne puissance = n^e avec e>=0'''
    if e<0:
        return None
    if e==0:
        return 1
    i = 0
    p = 1
    assert p == n**i
    while i<e:
        p = p * n
        i = i + 1
        assert p == n**i
    assert p == n**i
    return p

if __name__ == '__main__':
    n = int(input("Entrez le nombre n : "))
    e = int(input("Entrez le nombre e : "))
    print(f'p = {puissance(n,e)}')

Les assertions montrent que l’expression p = n^i est vraie à l’entrée de la boucle, durant les itérations dans la boucle et l’est toujours à la sortie de la boucle.

6. Complexité

Pour identifier la classe de complexité d’un algorithme, il faut s’intéresser à sa durée d’exécution ou plus précisément à comment sa durée d’exécution augmente lorsque la taille des données augmente.

Ressource : Berkeley Algorithmic Complexity

6.1. Exercices

Vous allez faire tourner la fonction produit() en jouant tour à tour sur les paramètres a et b pour identifier sa classe de complexité :

Q8) Commencez par faire varier le paramètre b. Ajoutez la fonction suivante à votre programme et faites le tourner.

import time
import matplotlib.pyplot as plt

def complexite(nb_fois_algo : int)->None:
    '''nb_fois_algo : produit(10,n) avec n de 0 à  nb_fois_algo '''
    les_produits = []
    les_times = []
    for n in range(0,nb_fois_algo,10):
        start = time.time()
        # code à compléter
        les_produits.append(......)
        end = time.time()
        les_times.append((end-start)*1000)

    plt.plot(les_produits, les_times)
    plt.xlabel('produits de 10*n')
    plt.ylabel('Temps (ms)')
    plt.title("Complexite de l'algorithme de la fonction produit()")
    plt.grid()
    plt.legend()
    plt.show()

def produit(a : int, b : int) -> int:
    ...
if __name__ == '__main__':
    complexite(5000)

Q9) Enregistrez la figure obtenue et identifiez la classe de complexité de l’algorithme.

Q10) Faites varier le paramètre a, faites tourner le programme, enregistrez la figure obtenue et identifier dans ce cas la classe de complexité de l’algorithme.
Expliquez la différence avec le cas précédent.

Correction

Q8) Programme

import time
import matplotlib.pyplot as plt

def complexite(nb_fois_algo : int)->None:
    '''nb_fois_algo : produit(10,n) avec n de 0 à  nb_fois_algo '''
    les_produits = []
    les_times = []
    for n in range(0,nb_fois_algo,10):
        start = time.time()
        les_produits.append(produit(10,n))
        end = time.time()
        les_times.append((end-start)*1000)

    plt.plot(les_produits, les_times)
    plt.xlabel('produits de 10*n')
    plt.ylabel('Temps (ms)')
    plt.title("Complexite de l'algorithme de la fonction produit()")
    plt.grid()
    plt.legend()
    plt.show()

def produit(a : int, b : int) -> int:
    ...

if __name__ == '__main__':
    complexite(5000)

Q9) Classe de complexité de l’algorithme lorsque la taille de b croit.

Lorsque la taille de b croit, la classe de complexité de l’algorithme est linéaire soit \$O(n)\$.

Q10) Classe de complexité de l’algorithme lorsque la taille de a croit

les_produits.append(produit(n,10))

Lorsque la taille de a croit, la classe de complexité de l’algorithme est constante soit \$O(1)\$.

La boucle effectue b fois la somme a avec lui même \$b = 3 => a + a + a\$. Peut importe la valeur de a, c’est b qui détermine le nombre de boucle à faire et donc le temps d’exécution de l’algorithme.

- Si b est constant, on a une complexité constante \$O(1)\$. - Si b croit, on effectue b itérations de boucle dans laquelle on effectue deux additions qui sont des opération de complexités constantes \$O(1)\$. On obtient donc une complexité : \$b*O(1)\$ soit \$O(n)\$.