Algorithmique : preuve d’un algorithme

I) Les trois questions: terminaison, correction, complexité
II) La terminaison d’un algorithme
    1) Itération d’une boucle
    2) Cas où l’algorithme ne comporte pas de boucle ou d’appel récursif
    3) Terminaison d’une  boucle “pour”
    4) Peut-on modifier le compteur lors de l’exécution d’une boucle “pour”
    5) Terminaison d’une boucle  “tant que”
    6) Terminaison d’une fonction récursive
III) Démonstration d’un algorithme
    1) Cas où l’algorithme ne comporte pas de boucle ou de fonction récursive
    2) Comment démontrer qu’une boucle ou une fonction récursive produit le résultat attendu
    3) Démonstration qu’une boucle “pour”
    4) Démonstration d’une boucle “tant que”
    5) Démonstration d’une fonction récursive
IV) Autres exemples de preuve d’un algorithme
    1) Suite de Fibonacci
    2) Division euclidienne
    3) Algorithme d’Euclide

I) Les trois questions: terminaison, correction, complexité

  Lors de l’exécution d’un algorithme, les trois questions suivantes se posent:

Quelles que soient les données:
  1) Se termine-t-il ?
  2) Résout-il correctement le problème posé ?
  3) Suivant la taille des données, en combien de temps se termine-t-il ?

→ La première question pose le problème de la terminaison de l’algorithme.
→ La seconde question pose le problème de la correction (on peut dire démonstration) de l’algorithme.
→ La troisième question pose le problème de la complexité de l’algorithme.

  L’étude de la complexité d’un algorithme est traitée dans un autre document. Ici il sera question de correction et de terminaison, autrement dit de la preuve que l’algorithme résout le problème posé en un nombre fini d’étapes.

II) La terminaison d’un algorithme

1) Itération d’une boucle

  On appelle itération d’une boucle une exécution des instructions pour une valeur du compteur (boucle “pour”) ou une exécution des instructions du “tant que”.

2) Cas où l’algorithme ne comporte pas de boucle ou d’appel récursif

L’algorithme se termine en autant d’instructions qu’il est composé.

3) Terminaison d’une  boucle “pour”

  Une boucle du type “pour i variant de a à b: itération” effectue un nombre N fini de fois (N = b-a+1) l’itération. La boucle se termine donc. Sauf si on imagine pouvoir perturber le compteur.

4) Peut-on modifier le compteur lors de l’exécution d’une boucle “pour” ?

  Une boucle effectue des instructions pour des valeurs successives d’un compteur. En modifiant le compteur, peut-on perturber le mécanisme ? On peut alors imaginer qu’en modifiant le compteur lors de l’exécution, une boucle “pour…” ne se termina pas forcément. Mais, par exemple:

def test():
    for i in range(3):
        print(i)
        i = 0
        print(i)

affiche bien 0, 0, 1, 0, 2, 0 et pas 0, 0, 1, 0, 1, 0, 1, 0… et se termine.

  On  peut donc modifier un compteur (ici la variable i) de boucle “pour…” lors de l’exécution de la boucle, mais le compteur reprend bien à chaque itération du “pour…” la valeur prévue au départ, et non la valeur suivante du compteur à l’issue de l’itération précédente.

5) Terminaison d’une boucle  “tant que”

a) Un exemple de “boucle infinie”

while 1==1:
    print(2)

affichera "indéfiniment" 2, 2, 2, 2,…

  Une boucle conditionnelle, “tant que condition: instructions” ne se terminera pas si la condition reste toujours vraie. Ce n’est parfois pas évident de savoir si la condition (modifiée par les instructions) finira par être fausse.

b)  Comment démontrer qu’une boucle “tant que” se termine

  Pour prouver qu’une boucle “tant que” se termine, il suffit de trouver une quantité en rapport avec les valeurs des variables de l’algorithme qui:
    (1) est un entier positif avant l’exécution de la boucle “tant que”
    (2) est un nombre entier positif à la fin de chaque itération du “tant que”
    (3) décroit strictement à chaque itération

  En effet, comme une suite ( u n ) strictement décroissante d’entiers positifs ne peut être définie pour tout entier n, le nombre d’itérations du “tant que” sera fini et la boucle se terminera.

  Cette quantité, souvent le contenu d’une des variables, s’appelle suivant les auteurs un “variant” ou un “convergent” de la boucle.

c) Exemple 1: la division euclidienne

Cette fonction doit calculer le quotient et le reste de la division de l’entier a     0 par l’entier b > 0.

def div_eucl(a, b):
    r, q = a, 0
    while r >= b:
        r, q = r - b, q + 1
    return (q, r)

  La quantité r est un variant correct de la boucle while. Notons r k la valeur de r à la fin de la k ième itération, posons r 0 = a et notons E k l’ensemble des entiers   k N * pour lesquels la k ième itération s’exécute.
    • r 0 = a est un entier et k E k , r k = r k - 1 - b est un entier positif  (récurrence immédiate)
    • La suite ( r k ) est strictement décroissante car k E k , r k - r k - 1 = b > 0 .
  La boucle se termine.

d) Exemple 2

  On définit une fonction f(p) (avec p ∈ N * ).

def f(p):
    c = 0
    while p > 0:
        if c == 0:
            p, c = p - 2, 1
        else:
            p, c = p + 1, 0

Montrons que la quantité q = 2 p + 3 c est un variant correct de la boucle while précédente.
Notons p k , c k les valeurs de p k et c k à la fin de la k ième itération, et posons q k = 2 p k + 3 c k . On a p 0 = p , c 0 = 0 , q 0 = 3 p N *

Lors de la k ième itération (si elle a lieu, p k - 1 > 0 donc q k - 1 > 0 )
    • si c k - 1 = 0 , alors p k = p k - 1 - 2 et c k = 1 . Alors q k = 2 p k + 3 c k = 2 ( p k - 1 - 2 ) + 3 = 2 p k - 1 + 3 c k - 1 - 1 = q k - 1 - 1
    • si c k - 1 = 1 , alors p k = p k - 1 + 1 et c k = 0 . Alors q k = 2 p k + 3 c k = 2 ( p k - 1 + 1 ) + 0 = 2 p k - 1 + 3 c k - 1 - 1 = q k - 1 - 1

  Par récurrence immédiate: tant que la k ième itération a lieu, q k N et q k < q k - 1 , donc q est un variant correct. La boucle while se termine.

6) Terminaison d’une fonction récursive

a)  Comment démontrer qu’une fonction récursive se termine

  C’est analogue au cas d’une boucle “tant que”

  Pour prouver qu’une fonction récursive se termine, il suffit de trouver une quantité en rapport avec les valeurs des paramètres d’appels de la fonction qui:
    (1) est un entier positif avant l’exécution de la fonction
    (2) est un nombre entier positif à la fin de chaque exécution de la fonction
    (3) décroit strictement à chaque appel récursif

  Cette quantité, appelée variant  (ou convergent) est souvent un des paramètres (le paramètre) d’appel de la fonction.

b) Exemple 1: la factorielle

def facto(n):
    if n == 0:
        return 1
    return n * facto(n-1)        # appel récursif

  Le paramètre d’appel n vérifie les conditions: c’est un entier naturel au départ, qui diminue de 1 à chaque appel récursif.

c) Exemple 2 : le pgcd

def pgcd(a, b):
    if b == 0:
        return a
    return pgcd(b, a % b)        # appel récursif

  Le paramètre d'appel b vérifie les conditions: c'est un entier naturel au départ, qui diminue strictement à chaque appel récursif: le reste d’une division euclidienne est strictement plus petit que le diviseur.

III) Démonstration (correction) d’un algorithme

1) Cas où l'algorithme ne comporte pas de boucle ou de fonction récursive

  Il suffit d’exécuter les instructions une par une (avec d’éventuels distinctions de cas s’il y a des “si...”)  et de vérifier qu’il résout le problème quelles que soient les données, par des calculs algébriques usuels.

  On vérifie par exemple que la fonction val_abs(a) ( a ∈ R) suivante est la fonction valeur absolue .

from math import sqrt
def val_abs(a):
    b = (a + 1)**2                    # b = a 2 + 2 a + 1
    c = (b - 2*a)**2                # c = ( a 2 + 1 ) 2 = a 4 + 2 a 2 + 1
    c = c - 2*b + 4*a + 1        # c = a 4 + 2 a 2 + 1 - 2 ( a 2 + 2 a + 1 ) + 4 a + 1 = a 4
    return sqrt(sqrt(c))            résultat = a 4 = a 2 = | a |

2) Comment démontrer qu’une boucle ou une fonction récursive produit le résultat attendu ?

  La démonstration d’une boucle “pour” ou “tant que” ou d’une fonction récursive présente une grande similitude avec un raisonnement par récurrence classique de mathématiques.

3) Démonstration d’une boucle “pour”

a) Théorème

Pour démontrer une boucle “pour...” produit un résultat, il suffit de trouver une propriété P telle que:
    (1) (Initialisation) P est vraie après la première itération de la boucle.
    (2) (Transmission) Pour tout entier n ≥ 2, si P est vraie avant la n ième itération, alors P est encore vraie après cette n ième itération.
    (3) (Sortie) Après la dernière itération, cette propriété P doit permettre de démontrer que la boucle produit le résultat attendu.

b) Défintion : invariant

Cette propriété P s’appelle un invariant de boucle.

c) Rédaction d’une démonstration

Rédaction dans le cas d’une boucle “pour i variant de a à b” :  il est commode de noter P = P(k) la propriété après l’itération pour i = k.
    Initialisation: Prouvons que P(a) est vraie.    
    Transmission: Soit i ∈ {a,..., b-1} un entier pour lequel P(i) est vraie. Démontrons que P(i+1) est vraie.
    Sortie: Déduisons de P(b) (qui est vraie) le résultat attendu de la boucle.

d) Exemple : factorielle version “pour”

  Démontrons que la fonction facto(n) calcule n! pour un entier n ∈ N * :

def facto(n):
    p = 1
    for i in range(2, n + 1):
        p = p * i
    return p    

Pour n = 1 , la boucle n’est pas effectuée, le résultat est p = 1 = 1 ! . Supposons n 2 .

Soit p i la valeur du paramètre p après l’itération pour i = i . On a p 1 = 1 ( p 1 est la valeur de p avant l’itération pour i = 2 ) et p i = p i - 1 * i   pour i { 2 , ... , n } .
Notons la propriété   P ( i ) : p i = i !

Initialisation: ( i = 2 ) p 2 = p 1 * 2 = 2 = 2 ! . Donc P ( 2 ) est vraie
Transmission: Soit i { 2 , ... , n - 1 } . On suppose P ( i ) vraie. Alors p i = i ! , donc p i + 1 = p i ( i + 1 ) = i ! ( i + 1 ) = ( i + 1 ) !   , et P ( i + 1 ) est vraie.
Sortie:   P ( n ) est vraie, donc p = p n = n ! .

4) Démonstration d’une boucle “tant que”

a) Théorème

Pour démontrer une boucle  “tant que condition...” produit un résultat, il suffit de trouver une propriété P telle que:
    (1) (Initialisation) P est vraie avant la première itération de la boucle.
    (2) (Transmission) Pour tout entier n, si P est vraie avant la n ième itération, alors P est encore vraie après cette n ième itération.
    (3) (Sortie) Après la dernière itération, cette propriété P (et la condition qui est fausse pour la première fois) doit permettre de démontrer que la boucle produit le résultat attendu.

b) Invariant de boucle

Cette propriété P s’appelle un invariant de boucle.

c) Rédaction d’une démonstration

  Il est commode de noter P = P(n) la propriété après la n ième itération. P(0) est alors la propriété P après la zero ième itération, c’est à dire avant la première itération. On rédige ainsi:
    Initialisation: Prouvons que P(0) est vraie.
    Transmission: Soit n un entier pour lequel P(n) est vraie. Démontrons que P(n+1) est vraie.
    Sortie: Soit N la dernière itération. Déduisons de P(N) (qui est vraie) et de la condition (qui est fausse pour la première fois) le résultat attendu de la boucle.

d) Exemple : factorielle version “tant que”

  Démontrons que la fonction facto(n) calcule n! pour un entier n ∈ N * :

def facto(n):
    p, q = 1, n
    while q > 0:
        p = p * q
        q = q - 1
    return p    

  Remarquons que la boucle se termine (q est un variant correct). Démontrons sa correction.

Soient p i et q i les valeurs des paramètres p et q après la i ième itération. On aura: { p i + 1 = p i * q i q i + 1 = q i - 1 . Notons   P ( i ) : p i = n ! q i !

Initialisation : pour i = 0 (avant de rentrer dans la boucle), { q 0 = n p 0 = 1 , donc n ! q 0 ! = n ! n ! = 1 = p 0 et P ( 0 ) est vraie.

Transmission: Soit i N pour lequel P ( i ) : p i = n ! q i ! soit vérifiée.
Alors après la ( i + 1 ) ième itération, p i + 1 = p i * q i = n ! q i ! q i = n ! ( q i - 1 ) ! = n ! q i + 1 ! . Donc P ( i + 1 ) et vraie .

Sortie : A la sortie de boucle (pour un certain i ) la condition q > 0 est fausse pour la première fois donc q = 0 et p = n ! 0 ! = n ! .

5) Démonstration d’une fonction récursive

a) Cas ou le paramètre d’appel est un entier n.

def f(n):
    if cas de base:
        return ...
    return ...f()...            # appel(s) récursif(s)

  Pour démontrer qu’une fonction récursive f(n) (n ∈ N) produit un résultat, il faut et il suffit de faire un raisonnement par récurrence:
    (1) (Initialisation) Le résultat est correct pour le (les) cas de base
    (2) (Transmission) Si le résultat est correct pour une valeur de n, elle est encore vraie pour n+1

→ Si dans l’appel récursif il y a uniquement f(n-1), il faut faire une récurrence simple
→ Si dans l’appel récursif il y a f(n-1) et f(n-2), il faut faire une récurrence double.
→ Si dans l’appel récursif il y a des valeurs f(k) avec k < n (k non déterminé), il faut faire une récurrence forte.

b) Cas ou il y a plusieurs paramètres d’appels  

def f(a, b,...):
    if cas de base:
        return ...
    return ...f()...            # appel(s) récursif

  Pour démontrer qu’une fonction récursive f(a, b, ...)  produit un résultat, il faut et il suffit de faire un raisonnement par récurrence sur un variant (une quantité entière positive qui décroit strictement à chaque appel récursif) liés aux paramètres de la fonction:
    (1) (Initialisation) Le résultat est correct pour le (les) cas de base
    (2) (Transmission) Si le résultat est correct pour une valeur n du variant, elle est encore vraie pour n+1.

Il faut faire une récurrence simple, double ou forte suivant les appels récursifs.

c) Exemple 1: toujours la factorielle

def facto(n):
    if n == 0:
        return 1
    return n * facto(n-1)        # appel récursif

On vérifie sans problèmes par récurrence simple que facto(n) = n! pour n ∈ N.

d) Exemple 2 : le pgcd

def pgcdR(a, b):
    if b == 0:
        return a
    return pgcdR(b, a % b)

Le paramètre d'appel b est un variant correct (Vu au II)6)c)). Faisons une récurrence forte sur b pour établir le résultat:

Initialisation: pour b = 0, ∀ a ∈ N, pgcdR(a,b) = pgcdR(a,0) = a = pgcd(a,0) : c’est bon

Transmission: Si pgcdR(a,b) = pgcd(a,b) pour un entier b (ceci ∀ a ∈ N ), alors pgcdR(a, b+1) = pgcdR(b+1, r) avec  
r = a % (b+1). Mais r < b + 1 donc r ≤ b et par hypothèse de récurrence pgcdR(b+1, r) = pgcd(b+1, r).
Or (cours de maths), pgcd(b+1, r) = pgcd(a, b+1) avec a = (b+1) q + r .
Donc  pgcdR(a, b+1) = pgcdR(b+1, r) = pgcd(b+1, r) = pgcd(a, b+1). CQFD, fin de la transmission.

IV) Autres exemples de preuve d’un algorithme

1) Suite de Fibonacci

Cette fonction fibo(n) doit calculer pour n ∈ N le terme ( F n ) de la suite de Fibonacci définie par:
F 0 = F 1 = 1 et n N , F n + 2 = F n + 1 + F n

def fibo(n):
    a, b = 1, 1
    for i in range(2, n + 1):
        b = a + b
        a = b - a
    return b

Pour n = 0 ou n = 1 , la boucle est ignorée et le résultat est b = F 0 = F 1 . Démontrons que fibo(n) = F n pour n 2 .

Notons pour n 2 a k et b k le contenu des variables a et b après l’itération pour i = k et P ( k ) la propriété   P ( k ) : { a k = F k - 1 b k = F k .

En posant { a 1 = 1 b 1 = 1 (valeurs de a et b avant de rentrer dans la boucle), on a  pour tout k 2 : { b k + 1 = a k + b k a k + 1 = b k + 1 - a k = b k .

Initialisation : P ( 2 ) est vraie car a 2 = b 1 = 1 = F 1 et b 2 = 1 + 1 = 2 = F 2 .

Transmission: Soit k 2 . Si P ( k ) : { a k = F k - 1 b k = F k est vraie . Alors { b k + 1 = a k + b k = F k - 1 + F k = F k + 1 a k + 1 = b k = F k   et P ( k + 1 ) est vraie.

Sortie : P ( n ) est vraie donc b = b n = F n . CQFD

2) Division euclidienne

Cette fonction div_eucl(a, b) doit calculer le quotient et le reste de la division de l'entier a 0 par l'entier b > 0.

def div_eucl(a, b):
    r, q = a, 0
    while r >= b:
        r, q = r - b, q + 1
    return (q, r)

Notons r n et q n les valeurs des paramètres r et q après la n ième itération. On aura: { r 0 = a q 0 = 0 et { r n + 1 = r n - b q n + 1 = q n + 1 pour n N .

Notons P ( n ) la propriété: a = b q n + r n

Initialisation: Comme r 0 = a et q 0 = 0 , b q 0 + r 0 = a et P ( 0 ) est vraie.

Transmission: Supposons (pour un entier n ) que a = b q n + r n . alors b q n + 1 + r n + 1 = b ( q n + 1 ) + r n - b = b q n + r n = a , donc P ( n + 1 ) est vraie.

Sortie: La propriété P assure qu’en sortie a = bq+r. De plus on sort de la boucle pour une valeur de r < b (et r ≥ 0) car le r d’avant est ≥ b. Donc en sortie a = b q+r avec 0 ≤ r< b. Par définition, q et r sont bien le quotient et le reste de la division de a par b.

3) Algorithme d’Euclide

Cette fonction pgcd(a, b) doit calculer le pgcd de deux entiers a et b naturels non tous les deux nuls.

def pgcd(a, b):
    x, y = a, b         # Facultatif ; pour rendre plus claire la démonstration
    while y > 0:
        x, y = y, x % y
    return x     

Notons x n et y n les valeurs des paramètres x et y après la n ième itération. On aura: { x 0 = a y 0 = b et { x n + 1 = y n y n + 1 = x n % y n pour n N .

  L’algorithme se termine: y est un variant car ( y n )   est une suite strictement décroissante de N. (Le reste d’une division est strictement plus petit que le diviseur)

Notons P(n) la propriété   pgcd ( x n , y n ) = pgcd ( a , b ) .

Initialisation: Comme x 0 = a et y 0 = b , P ( 0 ) est vraie.

Transmission: Supposons (pour un entier n ) que P ( n ) est vraie. Alors pgcd ( x n , y n ) = pgcd ( a , b ) .

Notons x n = q y n + y n + 1 l’égalité de la divison euclidienne de x n par y n (on a y n > 0 ).
Alors pgcd ( x n + 1 , y n + 1 ) = pgcd ( y n , x n - q y n ) = pgcd ( x n , y n )   d’après les propriétés du pgcd.
Donc pgcd ( x n + 1 , y n + 1 ) = pgcd ( x n , y n ) = pgcd ( a , b )   (HR) et P ( n + 1 ) est vraie.

Sortie: En sortie pour un entier N , la condition y > 0 devient fausse donc y N = 0 .
Alors P ( N ) est vraie) pgcd ( a , b ) = pgcd ( x N , y N ) = pgcd ( x N , 0 ) = x N = x . CQFD

© 2014 - Eric Obermeyer      Powered by