Aller au contenu

Activités III)

Activité III.01

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
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é III.02

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

1
2
3
4
5
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.