Activité

activité 12.1

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

VARIABLE
t : tableau d'entiers
i : nombre entier
min : nombre entier
j : nombre entier
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

Déterminer un invariant de boucle pour la boucle boucle 1 (voir code ci-dessus)

Démontrez que l'algorithme de tri par sélection est correct (qu'il trie les tableaux correctement).

activité 12.2

L'algorithme suivant permet de calculer la somme des N premiers entiers, où N est un nombre entier donné :

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

Déterminez un invariant de boucle (on devra trouver une propriété qui concernera la variable i et une propriété qui concernera la variable somme)

En utilisant l'invariant de boucle trouvé ci-dessus, démontrez la correction de cet algorithme.