Livre_silo 30 août 2013 16:32 Page 102
¨
©
¨
©
¨
©
¨
©
C o p y r i g h t E y r o l l e s
102
Informatique pour tous
En effet :
• Elle est vérifiée pour i = 0 : p 0 = 1 = 2 0 = 2 n−c 0 et c 0 = n ⩾ 0.
• Si on a p i = 2 n−c i et si l’on effectue une itération de plus, on a alors :
p i+1 = 2p i = 2
n−c i +1 = 2
n−c i+1 et c i+1 = c i − 1
Puisqu’on a effectué l’itération, c i > 0 et donc c i+1 ⩾ 0.
Toutefois, lorsque la condition c > 0 n’est plus vérifiée, en sortie de boucle, on a c i = 0 et donc p i = 2 n .
Toute la subtilité de ce raisonnement tient bien entendu dans le choix du bon invariant.
Exercice 4.22 * Démontrer la correction du programme de division euclidienne présenté page 99 à l’aide
d’un invariant de boucle.
4.3.5 Boucle infinie
On a vu comment démontrer qu’une boucle se termine en un nombre fini d’étapes. On
étudie ici ce qui se passe quand ce n’est pas le cas.
On considère la boucle suivante, qui est une variante du calcul de 2
n présenté page 97 :
p = 1
while c != 0:
p = p * 2
c = c - 1
Mis à part le fait que l’on teste c != 0 au lieu de c > 0, on peut penser que ce programme
fonctionne comme le précédent calculant 2
n .
Par exemple, partant de l’état
. .
3 .
c
, on obtient l’état final
. .
0 .
c
. .
8 .
p
.
Cependant, si on part de l’état
. .
-1 .
c
, on obtient successivement les états
. .
-2 .
c
. .
2 .
p
,
puis
. .
-3 .
c
. .
4 .
p
, etc. Il est clair que c aura toujours une valeur différente de 0 puisqu’il
s’agit d’un nombre négatif qui décroît. On dit que l’exécution est dans une boucle infinie,
c’est-à-dire une boucle de laquelle il n’y a pas de possibilité de sortir.
Ce type d’erreur de conception est indétectable par l’ordinateur et il est assez fréquent, car
les conditions et les corps des boucles sont en général plus complexes que dans cet exemple.
Le seul moyen de sortir de la boucle infinie est d’interrompre volontairement l’exécution
du programme, en pressant simultanément les touches Ctrl et C dans l’interpréteur.
Comme on l’a vu, il suffit de remplacer la condition par c > 0 pour corriger le problème :
p = 1
while c > 0:
p = p * 2
c = c - 1
¨
©
¨
©
¨
©
¨
©
C o p y r i g h t E y r o l l e s
102
Informatique pour tous
En effet :
• Elle est vérifiée pour i = 0 : p 0 = 1 = 2 0 = 2 n−c 0 et c 0 = n ⩾ 0.
• Si on a p i = 2 n−c i et si l’on effectue une itération de plus, on a alors :
p i+1 = 2p i = 2
n−c i +1 = 2
n−c i+1 et c i+1 = c i − 1
Puisqu’on a effectué l’itération, c i > 0 et donc c i+1 ⩾ 0.
Toutefois, lorsque la condition c > 0 n’est plus vérifiée, en sortie de boucle, on a c i = 0 et donc p i = 2 n .
Toute la subtilité de ce raisonnement tient bien entendu dans le choix du bon invariant.
Exercice 4.22 * Démontrer la correction du programme de division euclidienne présenté page 99 à l’aide
d’un invariant de boucle.
4.3.5 Boucle infinie
On a vu comment démontrer qu’une boucle se termine en un nombre fini d’étapes. On
étudie ici ce qui se passe quand ce n’est pas le cas.
On considère la boucle suivante, qui est une variante du calcul de 2
n présenté page 97 :
p = 1
while c != 0:
p = p * 2
c = c - 1
Mis à part le fait que l’on teste c != 0 au lieu de c > 0, on peut penser que ce programme
fonctionne comme le précédent calculant 2
n .
Par exemple, partant de l’état
. .
3 .
c
, on obtient l’état final
. .
0 .
c
. .
8 .
p
.
Cependant, si on part de l’état
. .
-1 .
c
, on obtient successivement les états
. .
-2 .
c
. .
2 .
p
,
puis
. .
-3 .
c
. .
4 .
p
, etc. Il est clair que c aura toujours une valeur différente de 0 puisqu’il
s’agit d’un nombre négatif qui décroît. On dit que l’exécution est dans une boucle infinie,
c’est-à-dire une boucle de laquelle il n’y a pas de possibilité de sortir.
Ce type d’erreur de conception est indétectable par l’ordinateur et il est assez fréquent, car
les conditions et les corps des boucles sont en général plus complexes que dans cet exemple.
Le seul moyen de sortir de la boucle infinie est d’interrompre volontairement l’exécution
du programme, en pressant simultanément les touches Ctrl et C dans l’interpréteur.
Comme on l’a vu, il suffit de remplacer la condition par c > 0 pour corriger le problème :
p = 1
while c > 0:
p = p * 2
c = c - 1