Activités — Invariant de boucle — NSI Terminale

Activités — Invariant de boucle

Terminale NSI — Algorithmique — Correction des algorithmes

Exercice 1 Tri par sélection

On rappelle l'algorithme du tri par sélection :

VARIABLE
  t : tableau d'entiers
  i, j, min : nombres entiers

DEBUT
  i ← 1
  tant que i < longueur(t) :   // boucle 1
    j ← i + 1
    min ← i
    tant que j <= longueur(t) :   // boucle 2
      si t[j] < t[min] :
        min ← j
      fin si
      j ← j + 1
    fin tant que
    si min ≠ i :
      échanger t[i] et t[min]
    fin si
    i ← i + 1
  fin tant que
FIN

1 Déterminer un invariant de boucle pour la boucle 1.
2 Démontrer que l'algorithme de tri par sélection est correct (qu'il trie les tableaux correctement) en utilisant cet invariant.

✔ Correction — Exercice 1

Question 1 — Invariant

On divise le tableau t en deux parties à chaque itération de la boucle 1 :
— t[1…i-1] : les i-1 plus petits éléments du tableau, triés.
— t[i…n] : le reste, dont les éléments sont tous supérieurs ou égaux à ceux de t[1…i-1].

Invariant de boucle retenu :

« Le sous-tableau t[1…i-1] contient les i-1 plus petits éléments du tableau original, placés en ordre trié, et chacun d'eux est inférieur ou égal à tous les éléments de t[i…n]. »

Initialisation

Avant la 1^re itération, i = 1, donc t[1…i-1] = t[1…0] est un tableau vide. Un tableau vide est trivialement trié. L'invariant est vrai.

Conservation

Supposons l'invariant vrai en début d'itération : t[1…i-1] est trié et contient les i-1 plus petits éléments.

La boucle 2 parcourt t[i…n] pour trouver l'indice min du plus petit élément de cette partie. On échange ensuite t[i] et t[min] si nécessaire.

Après cet échange, t[i] est le minimum de t[i…n], donc il est inférieur ou égal à tous les éléments restants. Ainsi t[1…i] est trié et contient les i plus petits éléments. Après i ← i+1, t[1…i-1] vérifie à nouveau l'invariant.

Terminaison

La boucle s'arrête quand i ≥ longueur(t), soit i = n. À ce moment, l'invariant garantit que t[1…n-1] contient les n-1 plus petits éléments triés. Il ne reste qu'un seul élément en position n, qui est forcément le plus grand. Le tableau t[1…n] est donc entièrement trié.

Conclusion : L'algorithme de tri par sélection est correct — il trie tout tableau d'entiers quel que soit son contenu.

Exercice 2 Somme des N premiers entiers

L'algorithme suivant calcule la somme des N premiers entiers, où N est un entier donné :

i = 0
somme = 0
while i < N :
    i = i + 1
    somme = somme + i

1 Déterminer un invariant de boucle.
On cherchera une propriété portant sur la variable i et une propriété portant sur la variable somme.
2 En utilisant l'invariant trouvé, démontrer la correction de cet algorithme.

✔ Correction — Exercice 2

Question 1 — Invariant

Observons l'évolution des variables à chaque fin d'itération :

Tour	i après l'itération	somme après l'itération	somme = i×(i+1)/2 ?
0 (init.)	0	0	0×1/2 = 0 ✔
1	1	1	1×2/2 = 1 ✔
2	2	3	2×3/2 = 3 ✔
3	3	6	3×4/2 = 6 ✔
4	4	10	4×5/2 = 10 ✔

Invariant de boucle retenu :
• 0 ≤ i ≤ N
• somme = i × (i + 1) / 2 (c'est-à-dire la somme des entiers de 1 à i)

Initialisation

Avant la première itération, i = 0 et somme = 0.
— Propriété sur i : 0 ≤ 0 ≤ N ✔
— Propriété sur somme : 0 × 1 / 2 = 0 ✔
L'invariant est vrai avant la première itération.

Conservation

Supposons l'invariant vrai en début d'itération : somme = i×(i+1)/2 avec i < N.

Après l'exécution du corps de la boucle :
— i devient i + 1 (notons ce nouvel entier i')
— somme devient somme + i'

On vérifie : somme' = i×(i+1)/2 + (i+1) = (i+1)×(i+2)/2 = i'×(i'+1)/2 ✔

L'invariant est donc conservé à la fin de l'itération.

Terminaison

La boucle s'arrête quand i ≥ N. Comme i est incrémenté de 1 à chaque tour en partant de 0, la boucle se termine avec i = N.

En substituant i = N dans l'invariant :
somme = N × (N + 1) / 2

Conclusion : À la fin de l'algorithme, somme = N×(N+1)/2, ce qui est bien la formule de la somme des N premiers entiers. L'algorithme est correct.