Comment trouver la boucle invariante à Hoare Triples
-
28-09-2020 - |
Question
Hey je suis nouveau à Hoare Triples, et je ne comprends pas de trouver les invariants de boucle dans l'hypothèse.Par exemple, alors que la boucle
[x>1 & y>1] WHILE x>0 DO x:=x-1; y:=y+2 END [x+y>5].
L'invariant est [2x + Y> 5] mais je ne comprends pas comment le trouver.Une explication étape par étape sur la façon de trouver qu'il sera grandement apprécié.
La solution
Comprendre d'abord le sens de la boucle invariante. Cela signifie une condition qui est vraie dans chaque itération du programme / algorithme au début et à la fin de la boucle. Votre programme est quelque chose comme ça.
$$ x> 1 \ texte {et} y> 1 $$
$$ \ texte {while} x> 0 $$
$$ \ hspace {4cm} \ texte {do} x:= x - 1, y:= y + 2 $$
$$ \ texte {fin} $$
$$ x + y> 5 $$
2x $ + y> 5 $ est un invariant que vous avez décrit. Il est visible du programme que $ x $ et $ y $ sera supérieur à 1 $ $ lors de la première itération de la boucle. Donc, dans la première itération de la boucle 2x $ + y> 5 $ (vous pouvez le prouver). AVIS DANS CHAQUE ITÉRATION DU TIXELET LA VALEUR DE LA VALEUR DE LA $ X $ Obtient une diminution par valeur $ 1 $ et La valeur de Y est d'augmenter par deux l'inégalité de l'inégalité 2x $ + y> 5 $ sera satisfait. Vous pouvez le prouver. Maintenant, venez à la condition de terminaison, à ce stade $ x $ sera un nombre négatif et ma demande est la valeur de $ Y $ va être au moins 5 $ . Ainsi, l'invariant 2X $ + Y> 5 $ SI True TRUET The Itération de la boucle tandis.
Exemple:
let $ x= 2 $ et $ y= 2 $ , alors 2 $ \ fois 2 + 2= 6> 5 $ est satisfait. Maintenant, dans la deuxième itération x= 1, y= 4 $ donc $ 1 \ fois 2 + 4> 5 $ Satisfait. Maintenant $ x= 0, y= 6 $ , boucle terminée, $ 2 \ fois 0 + 6> 5 $ .