Bonjour à tous
Je suis en prépa maths option informatique et on nous apprend à prouver qu'un algorithme termine et est correct, en utilisant notamment des invariants de boucle. J'ai quelques questions concernant ceux-ci. Soit l'algorithme suivant :
Code : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3
4
5
6
7
x ← 1
y ← 1
tant que x ≤ y faire
afficher (x)
x → x ∗ 2
y → y+10
fin tant que
On me demande ce qu'il affichera et de proposer un invariant de boucle. Naturellement, j'ai donné "après n passages, 2^n <= 1 + 10n". Est ce que c'est ce qu'on attend e moi ? Ca peut paraître bête comme question mais je vois pas vraiment quoi mettre d'autre, et non plus en quoi ça peut nous donner ce que l'algorithme affichera (en faisant une résolution sur WolframAlpha, je trouve que le dernier n sera 5, donc ça affichera 1, 2, 4, 8, 16, 32).
Ensuite, pour un programme aussi simple que
Code : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3
tant que 2^n*b ≤ a faire
n → n+1
fin tant que
Que donner comme invariant de boucle ? "2^n*b ≤ a" ?
Merci d'avance