Resposta correta: A) {Q[x := E]} x := E {Q}
Justificativa: pela axiomática da atribuição, a pós-condição Q após x := E requer que Q seja verdadeiro quando x é substituído pela expressão E antes da atribuição.
Resposta correta: B) I deve ser verdadeiro antes da primeira iteração e mantido em cada iteração.
Justificativa: o invariante precisa permanecer verdadeiro ao longo de todas as iterações para assegurar a correção do laço.
Resposta correta: B) A terminação envolve provar que há uma medida que decrementa a cada iteração, levando a uma conclusão finita.
Justificativa: além de manter I, é comum introduzir uma função de término que diminui a cada passagem para assegurar que o laço não é infinito.
i := 0; sum := 0;
while i < n do
sum := sum + i
i := i + 1
end
Quais as proposições que formam a invariante correta?
Resposta correta: B) sum = i(i-1)/2 e i ≤ n.
Justificativa: ao final de cada iteração, i avança de 0 a n, somando os termos 0,1,2,...,i-1. A soma desses termos é i(i-1)/2, e i permanece ≤ n durante as iterações.
Olá, alunas e alunos do curso de Fundamentos Matemáticos para a Contitação.
Nesta video-áulago vou falar de a demonstração de correção parte 2.
Para isso eu vou relembrar o conceito de triple de rory, falado ao acessão da atribuição e da regra condicional.
Para que possamos dessa forma começar a abordar o assunto da aula de hoje que é a regra do acessão.
Bom, no atribula de rory ela é representada por uma precondição um trecho de código e um nococho condição, certo? Nesse caso nós passamos a enxergar o código com uma secona, cada trecho sendo uma proposição e temos predicados antes e depois dessas proposições que precisam ser verificados, que precisam ser varicos.
Então, dessa forma, nós chamamos essa sequência de predicados aqui também de acessões onde a última acessão que seria a posca condição, em geral, serve para ser utilizada de trás para frente para verificarmos se as proposições vão nos levar a precondição, a precondição vai estar sendo mantida e todas as na verdade, precondições em cada uma dessas proposições estão ocorrendo.
Bom, dessa forma, em um programa ele vai ser considerado correto, se cada um desses condicionais são varicos que nós representamos e tratamos cada um deles como uma atribula de rory.
Bom, e para tratar cada um desses casos a gente faz uso, por exemplo, do acessão de atribuição, onde era a dada dica, vimos isso na semana passada, de avançar do fim, para o início de que forma.
Nós começamos pela posca condição, fazemos a atribuição o sentido inverso, então temos o x igual a b mantido, mas o temp recebe a, depois temos o y recebendo o b, o temp mantido e aí, por último temos o x recebendo a com y mantido em b, dessa forma a precondição se verifica.
No caso da regra condicional, nós tínhamos uma proposição que envolvia se uma condição ocorre, então executamos um p, caso contrário executamos outro trecho, dado uma pré e uma posse condição.
Então, a atribula nesse caso, ela vai ter a precondição e a condição a ser verificada nesse trecho de código.
Se essa condição se mostra a válida, esse trecho vai ser, essa proposição vai ser avaliada e, após a condição, é esperada ser contrida.
Além disso, temos que verificar o caso que essa condição não ocorre, nós temos ela negada e é isso de disparo outro trecho de código, a ser executado para que possamos verificar após e a pré-condição.
Nesse caso, que, desse exemplo, nós temos que dado que x é igual a 4, essa condição do código x, dado que a pré-condição x é igual a 4, essa condição do código é comprida x é menor que 5, então eu vou executar esse trecho e verificar isso que espera essa atifaseira, esta posse condição.
Então, nesse caso, dado que a verdadeira essa condição, essa explitcada, o que nós vamos fazer? Nós vamos usar o acción de atribuição para novamente em sentido inverso, partindo da precondição, verificamos que x menos 1 tem que ser igual a 3, o que não leva x nos leva x igual a 4, que é a pré-condição.
Bom, na regra do laço, nós temos uma estrutura de código diferente, então, dessa forma, nós vamos ter que verificar o predicado antes do trecho do código, considerando que a condição dada no laço é satisfeita e verificando que a pré-condição se mantém não é alterada pela execução desse trecho repetido de código.
E da mesma forma, verificamos quando a pré-condida ir deduzindo, quando a pré-condição também não é a condição do laço, não é mais o dedecido.
Bom, esse trecho de código, então, ele vai ter essa forma que dizem, enquanto uma determinada condição de estar acontecendo, eu executo um trecho de código.
Quando ela não for mais satisfeita, eu saio e a minha pré-condição ainda precisa ser que não seja mais avaliada, só que nesse caso, essa pré-condição que eu correi, quando eu estou no laço e quando eu já não estou mais nesse laço, ela é chamada de invariante de laço, é a propriedade que é verdadeira, cada vez que a condição do laço é avaliada.
Reparei, ela é avaliada, podemos se ver da deira ou falsa.
A propriedade que é verdadeira, essa propriedade é invariante de laço, se quisim, que ele é verdadeiro antes e depois de cada interação do laço.
Então, a propriedade de um invariante de laço acaba sendo satisfeita, independente de qual a interação do laço está sendo executado.
Então, três aspectos, precisam ser considerados quando a gente está analisando um invariante de laço.
Primeiro, a inicialização.
A invariante de laço é verdadeiro antes da primeira interação do laço, na nução.
Se for verdadeiro antes de uma interação do laço, ele permanece verdadeiro antes da próxima interação.
E terminação, no invariante de laço, nos dá uma propriedade útil que ajuda a mostrar que o algoritmo está correto quando o laço termina.
Bom, então, aqui nós temos um problema, nós precisamos mostrar que esse invariante de laço está correto, que ele é realmente enlárigo.
Para isso vamos lançar a mão da indução matemática de que forma.
Provamos um passo básico que consiste em provar queipotes de indução ocorre para os valores de entrada do laço.
Depois, nós vamos fazer aquela velha hipótese de que, serpotes de indução ocorre para carieterações, ela também é verificada após camais unidas interações.
Então, nós vamos supor que cada uma das execuções do laço, então é uma indução forte.
A un invariante de laço se mostra verdadeiro para de uma até caísma interação.
E aí vamos provar para cá mais um.
Por último, utilizamos a hipótese de indução para comprovar que o algoritmo está correto ao final do laço.
Bom, a hipótese de indução é invariante de laço.
É o que nós queremos provar que ocorre para garantir a corretude do trecho.
Então, nesse exemplo, qual que seria entrada? Nós vamos ter como entrada x e y.
Nós vamos ter como saída.
O j, mas isso tem um significado maior, essa saída não, porque é que esse j.
Para gente responde essa pergunta, vamos verificar a propriedade do laço, variante do laço.
O que está acontecendo nesse trecho de código? Eu estou toda hora acrescentando um pro í que começa em zero, e até ele seja diferente do j.
Então, vamos tomando o í que está somando o í que consiste em isso, e em vez de ir vezes y.
Então, nesse caso, quando eu estou incrementando esse í, até ele bater em x, eu vou estar ao final retornando esse í após x interações.
Ou seja, j igual a x vezes y é o produto, a minha saída é o produto de x vezes y.
Então, eu posso representar isso usando as triples de rory da seguinte forma.
Eu tenho que o meu invariante de laço é j igual a y, que é esse que é que a gente chama de precondição.
A minha condição do laço é o í diferente de x, e a parte disso eu consigo usando essa notação, escrever as condições de quando eu estou no laço, quando a minha condição está sendo verdadeira, e quando ela deixa de ocorrer, ela passa sem negar.
Bom, o invariante do laço, então, eu vou começar a fazer a provar a validade dele, eu vou para o passo base usando indução, que é antes do inicio do laço como mencionado.
Antes do inicio do laço, eu tenho y igual a zero, j igual a zero, logo a propriedade vai se verificar, porque se j tem igual a y, porque eu quero verificar, eu tenho que ir para zero, e um y está um valor de entrada qualquer, eu vou ter o produto zero, que bate com o valor inicial do j, que é zero.
Então, o passo base está provado.
Assim, eu posso partir para o passo indu tipo, que é supor que na caesima interação, e observa que eu estou contando de zero, então, o meu í na caesima interação, ele vale 1, e eu vou ter j igual a k menos 1 vezes i, no início da caesima interação, nessa linha do código.
Essa é minha hipótesia de indução, assim, no meu passo indu tipo, no início da interação k mais 1, nós vamos ter j igual a k menos 1 vezes i, e aí na linha 4, eu acrescento um í na caesima interação, o que me leva colocando a i, a k vezes i, ou seja, o meu j é k vezes i, e na linha 5, eu tenho igual a i, mais 1, que me leva a k menos 1, mais 1k, tudo coerente com os valores da caesperados para interação k mais 1.
Dessa forma, eu consigo ter essa propriedade triplas, valendo para esse invariante de laço, esse variante de laço é válido, e eu posso sumir para verificar o meu critério de terminação.
Como provado por indução, nós temos que j vai estar valendo x menos 1 vezes i, e igual x menos 1, no início da interação x.
Quando eu for os equipes da interação, eu vou ter j, mas j está mais y na linha 4, que vai me levar a x vezes y, e o meu í sendo acrescentado de x menos 1, mais 1, se tornando x, ou seja, na linha 5, eu disparo meu critério de parada, eu atualizo o valor de i, o que vai disparar o meu critério de parada na linha 3, levando a condição bem negável.
Aí, eu saio do aço, retornando o valor de j, que é o produto de x vezes y na linha 6.
De essa forma, chegando nessa condição aqui, da tripla.
Qualquer o valor de entrada, vamos para mais um exemplo.
Qualquer valor de entrada nesse tricho de código.
Nós temos c aqui, e o valor de saída vai ser b, mas qual é a relação nesse caso, para essa saída começar a fazer mais sentido? Nós vamos verificar a prioridade do aço.
Observe que eu acabei entregando aqui, mas observem que, por aqui, já estava para ver.
Se eu tenho a mais b, igual a c, a mesma coisa aqui, eu tiro o valor do a e acrescento com o valor de, considerando que o a no inicia c, então a soma desses termos vai dar c entre c.
Por isso, em variante do aço, você identifica aqui como a mais b, igual a c.
Considerando esse variante do aço, nós temos agora, considerando quando a condição é satisfeita, e depois que ela não é satisfeita.
O invariante do aço está estabelecido aqui, vamos para o passo básico e antes do início do aço, nós temos a igual a c, b, igual a zero, como eu já vi, é dito, que nos leva a mais b, igual a c, mais zero, que igual a c, ou seja, a mais b, igual a zero, se verifica o invariante do aço está satisfeito, no passo básico.
Agora, por indução, nós vamos assumir, então que a mais b, igual a c, é numa caísima interação, ou seja, o a vai ser igual a c menos k, e o b vai ser igual a k, de modo que a mais b, igual a c, está mantido na caísima interação.
No passo induitivo, então, supondo o válido na caísima interação, quando vamos para interação k mais 1, usamos a hipóteses de indução, então, nós partimos do fato de que o a valia c menos k, e eu estou retirando um d, na linha 4, e o b valia k, e eu estou acrescentando a ele mais 1, na linha 5.
Dessa forma, ao somar a mais b, após essas duas alterações, dessas duas proposições, eu verifica que somando a mais b, o meu invariante do aço está mantido, ele vai ir continuar resultando em c.
Então, eu provei que esse invariante do aço está valia, ele não é violato, na terminação, então, eu assume que eu vou estar chegando num ponto aqui, onde o meu a vai estar valendo 1, e o meu b vai estar valendo c, menos 1, na pelútea interação, e aí, quando vou executar a última interação, eu tenho a igual a a, menos 1, que torna a 0, o b igual a b mais 1 na linha 5, e isso faz com que eu tenha, na verdade, b igual a c menos 1, mais 1, o que me leva a c, dessa forma, com a valendo 0, eu tenho o critério de parada satisfeito, ou seja, na condição b negada a menor ou igual a 0, isso faz com que eu retorne b igual a c na linha 6, ou observe que o critério está mantido, o invariante de laço está mantido, porque eu tenho, a mais b igual a c, pois o a valizer o b valizer logo a mais b igual a c.
Bom, eu espero que vocês tenham entendido os exemplos e os conceitos foram retirados da sessão 2,3 do nosso livro texto, espero que vocês leionem, e nos vemos na próxima aula, muito obrigado pela atenção.