Como encontrar o invariante de loop em triplos hoare
-
28-09-2020 - |
Pergunta
Ei, sou novo em triplos Hoare e não consigo entender como encontrar os invariantes de loop na hipótese.Por exemplo, este loop while
[x>1 & y>1] WHILE x>0 DO x:=x-1; y:=y+2 END [x+y>5].
O invariante é [2x + y > 5], mas não entendo como encontrá-lo.Uma explicação passo a passo sobre como encontrá-lo será muito apreciada.
Solução
Primeiro entenda o significado do loop invariante.Significa uma condição que é verdadeira em cada iteração do programa/algoritmo no início e no final do loop.Seu programa é algo assim.
$$ x > 1 ext{ e } y >1 $$
$$ ext{Enquanto } x >0 $$
$$\hspace{4cm} ext{ Do } x:= x - 1, y:=y+2$$
$$ exto{Fim}$$
$$x + y > 5$$
$2x+y >5$ é um invariante como você descreveu.É visível no programa que ambos $x$ e $y$ será maior que $1$ durante a primeira iteração do loop.Então, na primeira iteração do loop while $2x+y > 5$(você pode provar isso).Observe em cada iteração do loop while o valor do $x$ obtém diminuição em valor $1$ e o valor de y está aumentando em dois, então a desigualdade $2x+y >5$ ficará satisfeito.Você pode provar isso.Agora vamos para a condição de término, neste ponto $x$ será um número negativo e minha reivindicação é o valor de $y$ vai ser pelo menos $5$.Assim o invariante $2x+y > 5$ si true durante a iteração do loop while.
Exemplo :
Deixar $x=2$ e $y=2$, então $2 \vezes 2+2 = 6 > 5$ é satisfeito.Agora na segunda iteração $ x = 1, y = 4$ então $1 \vezes 2+4 > 5$ satisfeito.Agora $ x = 0, y = 6 $, loop encerrado, $2 \vezes 0+6 > 5$.