Aller au contenu principal

Rappels d'algorithmique

Algorithmique

À retenir

Un algorithme est une suite finie et non ambiguë d’opérations ou d’instructions à réaliser afin de résoudre un problème.

En informatique, pour qu’un algorithme puisse être implémenté, il est nécessaire de s’assurer que la « suite finie et non ambiguë d’opérations ou d’instructions à réaliser » s’effectue en une durée finie .

À retenir

Lorsqu’on élabore ou étudie un algorithme, il est donc nécessaire de vérifier :

  • Sa finitude : Il doit se terminer en un temps fini.
  • Sa correction : Il doit (généralement) donner le bon résultat.
  • Sa performance : Plusieurs algorithmes peuvent permettre de résoudre une même classe de problèmes. Ils ne nécessiteront cependant pas tous l’utilisation de la même quantité de mémoire ou le même nombre d’étapes de calcul, donc la même durée.

Remarques

  • Ce n’est pas toujours une mauvaise nouvelle si certains algorithmes ont besoin d’un « temps infini » pour résoudre un problème : certains choix en cryptographie reposent sur l’idée que « casser » la protection nécessite une durée de calcul trop grande, pour le matériel dont on dispose aujourd’hui.
  • Pour certains problèmes on doit se contenter d’une solution approchée et pas d’une solution exacte.
À retenir

La performance d’un algorithme porte sur deux aspects : la durée du calcul et la quantité de mémoire nécessaires à la résolution du problème. Malheureusement ces deux points s’opposent . Il est souvent nécessaire d’occuper davantage de mémoire pour gagner en temps de calcul, ou d’écrire plus d’instructions, et donc faire plus de calculs, pour aboutir à une gestion de la mémoire optimale.

Conformément au programme, on limite la performance algorithmique à la complexité algorithmique.

Notion de complexité algorithmique

Introduction

À retenir

La complexité algorithmique donne des informations sur la durée du calcul nécessaire à la résolution du problème. Plus la complexité algorithmique est petite, moins de calculs sont effectués et plus l’algorithme est performant (sous réserve que la gestion de l’espace mémoire utilisé par l’implémentation de l’algorithme ne constitue pas un problème).

Avertissement

On exprime la complexité d’un algorithme en fonction de la taille (nombre) des données qu’il manipule en considérant que chaque instruction élémentaire s’effectue en temps constant.

Il existe plusieurs méthodes pour analyser la complexité d’un algorithme, comme :

  • L’analyse moyenne : Il s’agit d’évaluer comment varie la durée moyenne des calculs à effectuer en fonction du nombre de données manipulées.

  • L’analyse optimiste Il s’agit d’évaluer comment varie le nombre de calculs à effectuer, dans le scénario le plus favorable, en fonction du nombre de données manipulées.
    Par exemple, on cherche une valeur dans une liste et c’est la première qui apparaît lors de cette recherche.

  • L’analyse pessimiste (ou du pire cas) : Il s’agit d’évaluer comment varie le nombre de calculs à effectuer, dans le scénario le moins favorable, en fonction du nombre de données manipulées. Par exemple, on cherche une valeur dans une liste alors qu’elle n’est pas présente dans la liste.

Lorsqu’on utilise le résultat de l’analyse du « pire cas », aucune mauvaise surprise ne peut intervenir, le pire cas à été envisagé à l’avance.

Les complexités des différents algorithmes varient beaucoup. On peut néanmoins regrouper les algorithmes en quelques grandes familles :

  • Complexité constante : Leur notation est de la forme O(1)O(1). Ces algorithmes sont indépendants du nombre de données à traiter.

    Info

    La complexité constante apparaît dans la recherche par index dans un tableau.
    La complexité constante est la plus « performante ».

  • Les algorithmes logarithmiques : Leur notation est de la forme O(log⁡N)O(\log N). Ces algorithmes sont très performants en temps de traitement. Le nombre de calculs dépend du logarithme du nombre de données à traiter.
    Sur la Figure ci-dessous, on peut constater que, plus le nombre de données NN à traiter est important, moins le nombre de calcul à effectuer augmente rapidement — la valeur de la dérivée est de moins en moins grande.
    La fonction logarithme à utiliser dépend du problème étudié mais, comme la complexité est définie à un facteur près, la base du logarithme n’a pas d’importance.

Info

La complexité logarithmique apparaît dans les problèmes dans lesquels l’ensemble des données peut être décomposé en deux parties égales, qui sont elles-mêmes décomposées en 2 (recherche par dichotomie, recherche dans un arbre binaire, etc.).
La complexité logarithmique est très « performante ».

Avertissement

Le logarithme à utiliser est alors la fonction réciproque de f :x⟼2xf : x \longmapsto 2^x, c’est à dire log⁡2\log_{2} (aussi appelé logarithme entier).
Le logarithme entier d’un nombre xx supérieur ou égal à 1 est le nombre de fois qu’il faut le diviser par deux pour obtenir un nombre inférieur ou égal à 1.

  • Les algorithmes linéaires : Leur notation est de la forme O(N)O(N). Ces algorithmes sont rapides. Le nombre de calculs dépend, de manière linéaire, du nombre de données initiales à traiter.
Info

La complexité linéaire apparaît dans les problèmes dans lesquels on parcourt séquentiellement l’ensemble des données pour réaliser une opération (recherche d’une valeur, par exemple).
La complexité linéaire est considérée comme « efficace ».

  • Les algorithmes linéaires et logarithmiques (quasi-linéaire) : Leur notation est de la forme O(Nlog⁡N)O(N \log N).
Info

La complexité linéaire et logarithmique apparaît dans des problèmes dans lesquels on découpe répétitivement les données en deux parties, que l’on parcourt séquentiellement ensuite (tri Quicksort par exemple).
La complexité quasi-linéaire est considérée comme « assez efficace ».

  • Les algorithmes de type polynomiale : Leur notation est de la forme O(Nk)O(N^k) où kk est la puissance.
Info

Une complexité quadratique apparaît, par exemple, lorsqu’on parcourt un tableau à deux dimensions, lorsqu’on effectue un tri par comparaison, etc.
La complexité polynomiale est considérée comme « moyennement efficace ».

  • Les algorithmes exponentiels ou factoriels : Leur notation est de la forme O(eN)O(e^N) ou O(N!)O(N!). Ce sont les algorithmes les plus complexes.
    Le nombre de calculs augmente de façon exponentielle ou factorielle en fonction du nombre de données à traiter. Un algorithme de complexité exponentielle traitera, dans le pire des cas, un ensemble de 10 données en effectuant 22026 calculs ; un ensemble de 100 données en effectuant 2,688⋅1043\pu{2,688e43} calculs !!! On dit généralement que les problèmes produisant ce type d’algorithmes sont « non calculables ».
Info

On rencontre les algorithmes de type exponentiels ou factoriels dans les problématiques liées à la programmation de fonctions humaines comme la vision, la reconnaissance des formes ou l’intelligence artificielle.

Complexité Durée pour N=106N = 10^6
Logarithmique : O(logN)O(log N) 10 ns
Linéaire : O(N)O(N) 1 ms
Quadratique : O(N2)O(N^2) 1/4 heure
Polynomiale : O(Nk)O(N ^k) 30 ans si k=3k=3
Exponentielle : O(2N)O(2^N) plus de 1030000010^{300000} milliards d’années

Ordres de grandeur des durées d’exécution d’un problème de taille 10610^6 sur un ordinateur à un milliard d’opérations par seconde (« Informatique pour tous en CPGE », éditions Eyrolles).

Quelques règles simples permettant de déterminer la complexité d’un algorithme

Nous allons introduire, dans cette partie, quelques règles simples qui permettent de se faire une idée de l’efficacité d’un algorithme :

  • Une affectation ou l’évaluation d’une expression ont un temps d’exécution petit. Cette durée constitue souvent l’unité de base dans laquelle on mesure le temps d’exécution d’un algorithme.
  • Le temps pris pour exécuter une séquence d’instrutions p q est la somme des temps pris pour exécuter les instructions p puis q.
  • Le temps pris pour exécuter un test Si (b) Alors p Sinon q FinSi est inférieur ou égal au maximum des temps pris pour exécuter les instructions p et q, plus une unité qui correspond au temps d’évaluation de l’expression b.
  • Le temps pris pour exécuter une boucle Pour i variant de 1 à m par pas de 1 Faire p FinPour est mm fois le temps pris pour exécuter l’instruction p si ce temps ne dépend pas de la valeur de i. En particulier, quand deux boucles sont imbriquées, le corps de la boucle interne est répété à cause de cette boucle, mais aussi parce qu’elle-même est répétée dans son intégralité. Ainsi, si les deux boucles sont répétées respectivement mm et m′m\rq fois, alors le corps de la boucle interne est exécuté m×m′m \times m\rq fois en tout.
    Quand le temps d’exécution du corps de la boucle dépend de la valeur de l’indice ii, le temps total d’exécution de la boucle est la somme des temps d’exécution du corps de la boucle pour chaque valeur de ii.
  • Le cas des boucles Tantque est plus complexe puisque le nombre d’itérations n’est en général pas connu à priori. Il doit être évalué au cas par cas.
Exercice

Pour chacun des programmes suivants, dire en fonction de nn quel est le nombre d’opérations op que le programme effectue. Justifier votre résultat.

Pour i de 1 à n Faire 
    op
Pour i de 1 à n Faire 
    op; op
Pour i de 1 à n Faire
    Pour j de 1 à n Faire 
        op
Pour i de 1 à n Faire 
    Pour j de 1 à n Faire
        Pour k de 1 à n Faire
            op
Pour i de 1 à n Faire 
    op; op
     Pour j de 1 à n Faire
         op
         Pour k de 1 à n Faire 
            op
Pour i de 1 à n Faire
    Pour j de 1 à i Faire 
        op
i ⟵ 1
j ⟵ 1
TantQue (i ≤ m) et (j ≤ n) Faire
    op
    i ⟵ i + 1 
    j ⟵ j + 1
i ⟵ 1
j ⟵ 1
TantQue (i ≤ m) ou (j ≤ n) Faire
    op
    i ⟵ i + 1 
    j ⟵ j + 1
Tant que n > 0 Faire 
    op
    n ⟵ n // 2

Comment illustrer l’influence du nombre d’éléments passés en entrée

Quelques complexités à tout de suite identifier

En utilisant la fonction time du module time, écrire le code de fonctions qui :

  1. montre que le temps d’accès à un élément d’une liste est en O(1)O(1) ;
  2. montre que la recherche linéaire dans une liste est en O(N)O(N) ;
  3. met en évidence la complexité de l’opérateur Python in ;
  4. montre que la recherche linéaire dans une liste à deux dimensions est en O(N2)O(N^2) ;
  5. montre que la recherche dichotomique dans une liste triée est en O(log⁡(N))O(\log(N)).

Terminaison d’un algorithme itératif : variant de boucle

La structure qui généralement doit retenir l’attention lors de l’analyse de la terminaison d’un algorithme est la structure de boucle.

À retenir

On appelle variant d’une boucle une fonction qui a pour variables les variables du problème, qui retourne une valeur entière positive et qui décroît à chacune des itérations de la boucle, jusqu’à s’annuler ou prendre une valeur constante négative qui dépend de la condition d’arrêt de la boucle.

La découverte d’un variant de boucle permet de conclure que la boucle se termine puisqu’il n’existe aucune suite infinie strictement décroissante d’entiers naturels.

Exemple 1 : Calcul de la plus petite puissance de deux supérieure ou égale à un entier nn


Algorithme 1

Fonction : plusPetitePuissance(n)
Entrée : entier naturel n
Sortie : entier naturel pp dont la valeur est égale à la plus petite puissance de deux supérieure ou égale à nn.
Début
p⟵1p \longleftarrow 1
TantQue p<np < n Faire
p⟵2pp \longleftarrow 2 p
FinTantQue
Fin


Info

La fonction ff d’expression f(p)=n−pf(p) = n - p est-elle un variant de boucle ?

  • f(p)f(p) est un entier positif.
  • Tant que p<np < n, f(p)>0f(p) > 0
  • ff décroît sur l’ensemble des valeurs de pp puisque f(pi+1)−f(p)=n−pi+1−n+pi=pi−pi+1=pi−2pi=−pi<0f(p_{i+1}) - f(p) = n - p_{i+1} - n + p_{i} = p_{i} - p_{i+1} = p_{i} - 2p_{i} = - p_{i} <0
  • Condition d’arrêt : pmax⩾np_{max} \geqslant n, donc f(pmax)⩽0f (p_{max}) \leqslant 0.

La fonction ff est un variant de boucle et la boucle se termine donc bien.

Exemple 2 : Palindrome


Algorithme 2

Fonction : palindrome(m)
Entrée : chaîne de caractères m
Sortie : booléen Vrai si la chaîne de caractères m est un palindrome, Faux sinon
Début
i⟵0i \longleftarrow 0
j⟵longueur(m)−1j \longleftarrow \text{longueur} (m) - 1
TantQue i⩽ji \leqslant j Faire
Si m[i]=m[j]m[i] = m[j] Alors
i⟵i+1i \longleftarrow i + 1
j⟵j−1j \longleftarrow j - 1
Sinon
Renvoyer Faux
FinSi
FintantQue
Renvoyer Vrai
Fin


  1. Décrire au moyen d’un tableau indiquant l’évolution des valeurs des variables le fonctionnement de l’algorithme 2 pour la chaîne de caractères « sauras » puis pour la chaîne de caractères « radar ».
    Remarque : Le premier élément d’une chaîne a pour indice 0.

    Réponse
    • Pour l’entrée « sauras » :
      ii : 0, 1, 2
      jj : 5, 4, 3
      La fonction retourne Faux.

    • Pour l’entrée « radar » :
      ii : 0, 1, 2, 3
      jj : 4, 3, 2, 1
      La fonction retourne Vrai.

  2. Montrer que f(i,j)=j−if(i, j) = j - i est un variant de la boucle TantQue.

    Réponse

    f(i,j)=j−if(i, j) = j - i est-elle un variant de boucle ?

    • Tant que j>ij > i, f(i,j)f(i, j) est un entier positif et f(i,j)=j−i>0f(i, j) = j - i > 0.
    • f(i+1,j−1)=j−1−(i+1)=j−1−i−1=j−i−2=f(i,j)−2<f(i,j)f (i+1, j-1) = j - 1 - (i + 1) = j - 1 - i - 1 = j - i - 2 = f(i, j) - 2 < f(i, j).
      La fonction est donc décroissante sur l’ensemble des valeurs de ii et de jj.
    • Condition d’arrêt : i>ji > j, donc f(i,j)=j−i<0f(i, j) = j - i < 0

  3. En déduire que la boucle TantQue se termine.

    Réponse

    La fonction ff est un variant de boucle. La boucle se termine donc bien.

Correction d’un algorithme itératif : invariant de boucle

À retenir

On appelle invariant d’une boucle une propriété qui, si elle est vraie avant l’exécution d’une itération, le demeure après l’exécution de l’itération. Un invariant de boucle doit être vrai avant de commencer la boucle et est alors garanti de rester correct après chaque itération de la boucle. En particulier, l’invariant sera toujours vrai à la fin de la boucle.

Les boucles et la récursivité étant fondamentalement similaire, il y a peu de différence entre démontrer un invariant de boucles et prouver qu’un programme est correct en utilisant un raisonnement par récurrence.

Exemple 3 : Calcul de 2n2^n


Algorithme 3

Fonction : calculPuissanceDeux(n)
Entrée : entier naturel nn
Sortie : entier naturel pp dont la valeur est égale à 2n2^n
Début
p⟵1p \longleftarrow 1
Pour kk allant de 1 à nn faire
p⟵2pp \longleftarrow 2 p
FinPour
Fin


Info

La propriété « À chaque tour de boucle pp est une puissance de 2 » est un invariant de boucle. En effet :

  • Initialisation : Avant d’entrer dans la boucle : p=1=20p = 1 = 2^0.

  • Conservation : On suppose l’invariant vérifié au tour ii de la boucle : p=2ip = 2^i. Au tour i+1i + 1, pi+1=pi×2=2i×2=2i+1p_{i + 1} = p_{i} \times 2 = 2^i \times 2 = 2^{i + 1}.

  • Terminaison : La boucle réalise nn tours ; au dernier tour p=2n−1×2=2np = 2^{n - 1} \times 2 = 2^n

La proposition est donc bien un invariant de boucle et on peut conclure que l’algorithme est correct.

Exemple 4 : Quotient et reste de la division euclidienne d’un entier positif par un entier strictement


Algorithme 4

Fonction : division(a, b)
Entrée : entiers naturels aa et bb
Sortie : Quotient qq et reste rr de la division euclidienne de l’entier naturel aa par l’entier naturel bb
Début
q⟵0q \longleftarrow 0
r⟵ar \longleftarrow a
TantQue r⩾br \geqslant b Faire
q⟵q+1q \longleftarrow q + 1
r⟵r−br \longleftarrow r - b
FinTantQue
Renvoyer q,rq, r
Fin


  1. Décrire le fonctionnement de l’algorithme pour l’entrée (a = 17, b = 5) au moyen d’un tableau indiquant l’évolution des valeurs des variables au fil des itérations.

    Réponse
    a17171717b5555q0123r171272\begin{array}{c : c : c : c : c} a & 17 & 17 & 17 & 17\cr \hdashline b & 5 & 5 & 5 & 5 \cr \hdashline q & 0 & 1 & 2 & 3 \cr \hdashline r & 17 & 12 & 7 & 2 \cr \end{array}

  2. Montrer que la boucle TantQue se termine en utilisant un variant de boucle.

    Réponse

    La fonction f(r)=r−bf(r) = r - b peut-elle être un variant de boucle ?

    • f(r)=r−bf(r) = r -b est un entier.
    • Pour n’importe quel tour de boucle r⩾br \geqslant b, donc f(r)=r−b⩾0f(r) = r -b \geqslant 0.
    • Soit r2=r1−br_2 = r_1 - b.
      f(r2)=r2−b=r1−b−b=f(r1)−b⩽f(r1)f(r_2) = r_2 - b = r_1 - b - b = f(r_1) - b \leqslant f(r_1).
      La fonction ff est décroissante.
    • Condition d’arrêt : r<br < b, donc f(r,b)=r−b<0f(r, b) = r - b < 0.

    La fonction ff est bien un variant de boucle et cette boucle se termine.

  3. Montrer que la propriété a=bq+ra =bq+ r est un invariant de la boucle TantQue, en déduire que l’algorithme produit le résultat attendu.

    Réponse

    Si la propriété a=bq+ra =b q+ r est un invariant de boucle, elle doit être vraie avant d’entrer dans la boucle, à chaque tour de boucle et une fois la boucle terminée.

    • Initialisation : Avant d’entrer dans la boucle, q=0q=0 et r=ar=a. Donc on a bien a=0×b+aa = 0 \times b + a.
    • Conservation : On suppose la propriété vraie au rang kk quelconque de la boucle : a=bqk+rka = b q_k + r_k.
      Au rang k+1k+1, qk+1=qk+1q_{k+1} = q_{k} + 1 et rk+1=rk−br_{k+1} = r_k - b. Donc a=bqk+1+rk+1=bqk+b+rk−b=bqk+rka = b q_{k+1} + r_{k+1} = b q_{k} + b + r_k - b = b q_k + r_k.
    • Terminaison : La boucle s’arrête lorsque r<br < b. Au dernier tour de la boucle on a donc bien a=bq+ra=b q + r.

    La propriété a=bq+ra =bq+ r est bien un invariant de boucle et le programme est correct.

  1. Écrire le code Python implémentant l’algorithme 4. La spécification de la fonction est la suivante :
def division_euclidienne(a: int, b: int) -> tuple[int, int]:
    """
    Calcule la division euclidienne de l'entier naturel a par l'entier naturel b.
    Retourne les entiers naturels q et r, quotient et reste de cette division.
    """
Réponse
def division_euclidienne(a: int, b: int) -> tuple[int, int]:
    """
    Calcule la division euclidienne de l'entier naturel a par l'entier naturel b.
    Retourne les entiers naturels q et r, quotient et reste de cette division.
    """
    q = 0
    r = a
    while r >= b:
        q = q + 1
        r = r - b
    return q, r
  1. Écrire un jeu de tests pour la fonction division_euclidienne.
    Réponse
    assert division_euclidienne(1, 2) == (0, 1)
    assert division_euclidienne(2, 1) == (2, 0)
    assert division_euclidienne(17, 5) == (3, 2)

Exercices

Exercice

On considère la fonction suivante :

def power(n: int) -> int:
    p = 1
    i = 0
    while i < n:
        p = p * 2
        i = i + 1
    return p
  1. Quel calcul ce code réalise-t-il ?

  2. Écrire un jeu de test pour cette fonction.

  3. Démontrer que l’algorithme se termine.

  4. Démontrer que l’algorithme est correct.

  5. Déterminer la complexité de cet algorithme.

Réponses
  1. power calcule 2n2^n.

assert power(0) == 0
assert power(1) == 2
assert power(10) == 1024
  1. f(i)=n−if(i) = n - i est-il un variant de boucle ?

    • f(0)=nf(0) = n est un entier naturel.
    • f(i+1)−f(i)=n−i−1−n+i=−1f(i+1) - f(i) = n - i - 1 - n + i = -1
      La suite est strictement décroissante.
    • imax=ni_{max} = n donc f(imax)=n−imax=n−n=0f(i_{max}) = n - i_{max} = n - n = 0.
      f(i)f(i) est un variant de boucle, l’algorithme se termine.
  2. Invariant de boucle : “À l’issue de chaque itération, p=2ip=2^i.”

    • Initialisation : À l’entrée de la boucle, i=0i=0, 2i=20=1=p2^i = 2^0 = 1 = p.
    • Conservation : On suppose qu’à l’issue du tour de boucle de compteur kk, pk=2kp_k = 2^k.
      pk+1=pk×2=2k×2=2k+1p_{k+1} = p_k \times 2 = 2^k \times 2 = 2^{k+1}.
    • Terminaison : Lors du dernier tour de boucle, i=n−1i = n - 1, le calcul effectué est donc p=2n−1×2=2np = 2^{n-1} \times 2= 2^n.
      L’algorithme est correct.
Exercice

On considère la suivante :

def maxer(s: list[float]) -> float:
    while len(s) > 1:
        if s[0] > s[1]:
            s.pop(1)
        else:
            s.pop(0)
    return s.pop(0)
  1. Quelle opération ce code réalise-t-il ?

  2. Écrire un jeu de test pour cette fonction.

  3. Démontrer que l’algorithme se termine.

  4. Démontrer que l’algorithme est correct.

  5. Déterminer la complexité de cet algorithme.

  6. Existe-t-il un ou des algorithmes qui réalisent la même opération plus efficacement ?

Réponses
  1. la fonction trouve le plus grand élément dans la liste passée en argument.

  2. f(i)=i−1f(i) = i - 1 avec i=len(s)i=\text{len}(s) est-il un variant de boucle ?

    • f(i0)=len(s)−1f(i_0) = len(s) - 1 est un entier naturel si la liste s n’est pas vide.
    • f(ik+1)−f(ik)=len(s[1:])−1−len(s)+1=len(s[1:])−len(s)<0f(i_{k+1}) - f(i_k) = len(s[1:]) - 1 - len(s) + 1 = len(s[1:]) - len(s) < 0
      La fonction ff est strictement décroissante.
    • ider=1i_{der} = 1, f(ider)=1−1=0f(i_{der}) = 1 - 1 = 0.
      ff est un variant de boucle et la boucle se termine.
  3. Invariant de boucle :

Exercice

On considère la fonction somme_premiers_entiers qui implémente l’algorithme :

Algorithme 5

Fonction : somme_premiers_entiers(n)
Entrée : entier naturel nn
Sortie : somme des n premiers entiers naturels
Début
somme⟵0\text{somme} \longleftarrow 0
i⟵1i \longleftarrow 1
TantQue i⩽ni \leqslant n Faire
somme⟵somme+1\text{somme} \longleftarrow somme + 1
i⟵i+1i \longleftarrow i + 1
FinTantQue
Renvoyer somme
Fin

  1. Implémenter en Python l’algorithme proposé. Ne pas oublier la spécification de la fonction.

  2. Écrire un jeu de test pour cette fonction.

  3. Prouver que la boucle se termine à l’aide du variant de boucle f(n,i)=n−if(n, i) = n - i où ii est le compteur de la boucle.

  4. Prouver que la proposition : « au début du tour du kième tour de la boucle, la variable somme est égale à la somme des k−1k-1 premiers entiers naturels » est un invariant de boucle. En déduire que l’algorithme est correct.

  5. Quelle est la complexité de cet algorithme ?

Réponses
def somme_premiers_entiers(n: int) -> int:
    """
    Calcule la somme des n premiers entiers.
    
    HYPOTHÈSE : n entier naturel
    """
    somme = 0
    i = 0
    while i <= n:
        somme = somme + i
        i = i + 1
    return somme
assert somme_premiers_entiers(0) == 0
assert somme_premiers_entiers(1) == 1
assert somme_premiers_entiers(12) == 12 * (12 + 1) / 2
  • Pour n’importe quel tour de boucle, on a i⩽ni \leqslant n. Donc f(n,i)=n−i⩾0f(n, i) = n - i \geqslant 0 ;
  • Au rang k+1k+1, ik+1=ik+1i_{k+1} = i_k + 1 donc f(n,ik+1)=n−ik+1=n−ik−1=f(n,ik)−1<f(n,ik)f(n, i_{k+1}) = n - i_{k+1} = n - i_k - 1 = f(n, i_k) - 1 < f(n, i_k). La fonction ff décroit lorsque la boucle progresse.
  • condition d’arrêt : i>ni>n, donc f(n,i)=n−i<0f(n,i) = n - i < 0.

La fonction ff est positive, décroissante lorsque la boucle « tourne » et finalement prend une valeur négative lorsque la boucle est terminée ; c’est un variant de boucle.
La présence d’un variant de boucle nous assure que la boucle se termine.

  • Initialisation : Avant d’entrer dans la boucle, somme=0\text{somme} = 0.
  • Conservation : On suppose que somme=0+1+…+k−1\text{somme} = 0 + 1 + \ldots + k -1 au début de la kième boucle. Pendant la kième boucle, on a somme=somme+k=0+1+…+k−1+k\text{somme} = \text{somme} + k = 0 + 1 + \ldots + k -1 + k.
    Au début de la k+1k+1ième boucle, on a donc bien somme=0+1+…+k\text{somme} = 0 + 1 + \ldots + k.
  • Terminaison : La boucle s’arrête dès que i>ni > n. Donc au début du n+1n+1ième tour (tour de boucle qui n’aura jamais lieu), on a bien somme=0+1+…+n\text{somme} = 0 + 1 + \ldots + n.

La proposition est bien un invariant de boucle, elle nous assure que le programme est corret.