o Olá pessoal sou professor Douglas melhor ali na aula de hoje vamos falar sobre demonstração de correção mas correção do que correção de um algoritmo média um programa não tá na hora de a gente tem um método desenvolvido aqui que a gente vai ver porque o Ari eu não sei falar certo nome dele então vou te chamar de Roar mesmo o que tenta avisar é verificar se um algoritmo sem programa está correto ou não então né salas vamos ver a tripa de Coari nós vamos ver o acostumado atribuição e a regra condicional bom então primeiro
o que a gente quer fazer a verificação de um programa que que a verificação do programa é tentar ver de alguma forma se aquele programa de computador se aquele algoritmo ele está correto ou não e tem duas formas da gente vê se o algoritmo Está correto não através de testes ou pela demonstração de correção que a gente vai vir na aula de hoje teste ideia só a gente pegar da entrada as particulares e ver se as respostas são satisfatórios ou não é pegar lá e fazer o teste mesmo na máquina e já demonstração de correção
a gente já usa técnicas que a gente viu no curso de lógica né você já técnicas de um sistema de lógica formal Então a gente vai tentar os algumas coisinhas que a gente não deu entendeu Por exemplo quantificadores e predicados lá na lógica e tentar usar aqui na demonstração da correção para ver se a gente consegue verificar se uma coisa que está correta ou não então demonstração de coisas são utilizadas técnicas de um sistema de lógica formal e é isso que a gente vai ver nessa aula Primeiro vou mudar alguns nomes do que a gente
vai utilizar aqui a gente vai chamar de X a coleção de possíveis entradas que a gente vai poder atribuir a um programa P então programa que a gente vai verificar a validade é o programa p são comandos ali então esse P ele vai transformar a nossa entrada que a gente tá dando para o algoritmo X em uma saída Y como se fosse uma função então no caso aqui o y que a saída é um pbx né o programa P aplicado na entrada x que vai produzir a saída y o que de x é um predicado
que ele vai falar quais são as condições que a entrada deve ter né porque entrada não posso pegar um todos os algoritmos posso pegar qualquer entrada tem algumas condições que me entrada tem que satisfazer essas condições que entraram tem que fazer a gente vai chamar de que já as condições da saída a gente vai chamar Dr porque a saída também tem que ter algumas condições que tem que ser satisfeita dependendo do objetivo do pódio do objetivo do programa e as essa entrada de pensão do XX vai ser tem que satisfazer a condição que já saída
Ela depende da nossa entrada e depende também na nossa saída Lembrando que o Pedro X é um Y que a saída Então vou pegar entrada EA saída e ver se essas duas coisas juntas satisfazem a condição saída às vezes aconteceu saída só depende do Y gente às vezes depende do X do ipes né então no caso que eu coloquei de o x e y caso peixes e Então como que a gente vai escrever o perceba que o que a gente falou até agora é uma forma bem formulada Olha só o programa para todos x com
codificador dedicado ou em conectivo lógico outro predicado Raquel para todos xx7 sais que X então o x entrada e o y que é o peixes que a saída satisfaz o RX se acontecer isso quer dizer que o nosso programa está correto percebe aqui a condição de entrada é um predicado ele sai também outro medicado Não beleza se o meu programa para qualquer tipo de como entradas Yoshi's satisfaz o que que a condição de entrada implica que o x junto que eu ia sair da Y Ken Y peixes vão satisfazer a condição de saída quer dizer
que me o programa está correto Então veja veja que a gente tem uma fórmula bem formulada o Ok então vamos pegar um exemplo então um supor aqui que o nosso x a coleção de possíveis entradas são os números reais e ao nosso programa P ele pega essa entrada x e calcula a raiz quadrada então nosso Y vai ser o que vai ser raiz quadrada do Xis da entrada então o nosso peixes nosso programa pecado no x que vai produzir essa saída Y é pegar a raiz quadrada de x beleza esse é o nosso objetivo nosso
programa faz Quais são as condições de entrada bom eu não posso calcular raiz quadrada de qualquer número real só de números positivos né Pode até ser maior Galzerano não coloquei o Marco Zero mas podia ser também maior igual a zero que existe raízes é vamos supor que eu quero calcular só de raiz quadrada de números positivos tá então nossa condição de entrada ou seja um X tem que ser positivo porque negativo não vai dar certo não dá para calcular raiz quadrada de negativo dentro dos números reais nos complexo só para calcular números raiz quadrada negativa
o gás aqui no caso a beleza essa nossa condição de entrada o X tem que ser positivo e a condição de saída bom são duas coisas na condição de saída então tipo eu tenho entrada x e entrada EA saída Y que é o peixes mais escrever aqui como vocês isso é a mesma coisa você escrever Y B X a mesma coisa qual que é a condição de saída bom quando sair do seguinte a minha saída ao quadrado tem que ser igual a entrada concorda se eu não vou calcular raiz de X esse vai ser a
saída bom a minha saída ao quadrado tem que ser entrada beleza essa é uma condição e tem outra condição o meu Y tem que ser maior que zero também já que o X é Marco Zero o meu isso tem que ser Marco Zero porque por exemplo se eu de comentar a x = 4 a saída tem que ser dois positivo eu só quero é só tem algum número ao quadrado que dá quatro sim os dois ao quadrado da quatro e o menos 2 ao quadrado da quatro só que a gente define Raiz com uma coisa
positiva por isso que a nossas condições saíram nesse caso aqui tem seu número que é o quadrado deu X e esse número tem que ser positivo porque a Raíssa é quadrada é sempre positiva Então beleza o x a nossa coleção do sociais no nosso exemplo o nosso programa pega o x entrada x e calcule a raiz quadrada E aí obtenho essa regra Y minha condição de entrada eu não quero trabalhar com 0 no caso minha concentrado X tem que ser positivo tem que ser maior que zero e minha condição de sair do tem que ter
o que eu tenho que ter que o y ao quadrado tem que ser X para valer essa relação aqui né E além disso o Y tem que ser positivo porque não existe raiz quadrada negativa raiz quadrada definidas em para ser positivo Ah beleza então olha só como que vai ficar aqui eu como ficava de forma geral né para todos x se vale se o x satisfaz que então a nossa entrada x não sai daí Vilson satisfaz R Ok mas como que escreve isso daqui que é de forma geral com o nosso exemplo o nosso exemplo
eu ficar assim ó para todo x Real seu X é positivo implica que Y quadrado tem que ser igual a x e y tem que ser maior que zero Beleza se satisfazer isso quer dizer que meu programa que calcula a raiz quadrada Tá certo se eu pegar qualquer especial se x é positivo implica que a saída ao quadrado e x e esse Y é positivo então com certeza eu consegui que fazer um programa que calcula a raiz quadrada Beleza então tem que fazer isso daqui só que tem outra forma da gente escrever sim e aí
entra a tripla de roary o que que é importante em tudo isso daqui ó tudo que a gente falou aqui ó é importante o importante é o que que a condição de entrada o r que a condição saída são dois predicados e o p q é o programa que que o programa faz isso que são importantes só que o pior programa O que tinha nosso predicado que são as condições de entrada que a gente chama de pré-condição e o r só as condições de sair daqui é outro pecado né gente chama de pós-condição beleza a
gente tinha esquecido desse jeito na tripa de Glória Como que escreve escreve desse jeito ó Então a gente vai colocar aqui a condição de entrada o programa que no caso é um comando que a gente vai fazer no programa EA condição de saída então sempre a gente vai ter uma condição de entrada os nossos comandos e a nossa condição de saída isso daqui a tripa de óleo ele pede raras que são três coisas atrás coisa importante pra gente analisar no programa quando são de entrada O que que a pré-condição o comando que o programa Vai
Fazer a coisa condição de saída né que alto predicado que me chama de posse quando são isso daqui descreve o nosso algoritmo profissionais e se eu tiver aqui eu tô pensando em um comando no programa e se eu tiver vários comandos bom se eu tiver vários comandos que acontece eu tenho uma condição de entrada aí eu tenho um comando eu vejo uma outra condição se pode ser satisfeita aí eu posso ter um outro Comando uma outra condição até chegar no último comando E aí sim tem a última saída do que ela sair do algoritmo no
caso como que eu escreveria escreveria que ela dessa forma perceba que o que é a pré-condição que a condição das entradas e elaa último Henry é a pós-condição que a condição da saída do programa Tony vai entrar com uma condição que vai fazer os comandos s0 S1 esse roxa todos os comandos até o último comando E aí tem que satisfazer A nossa condição de saída então ele só que acontece eu tenho uma condição de entrada e ele tem um condições intermediárias porque a condição de entrada fácil em comando Esse comando tem que fazer depois uma
outra condição faça um outro comando tem que estar sabe fazer uma outra condição e eu vou fazer no comando comando comando até o último comando E aí sim tem que fazer a última condição que a condição de saída que após punção E aí sim eu dou a saída do algoritmo então se você perceber em um programa eu posso ter várias triplas de olha aqui ó eu tenho condição de entrada o primeiro comando e primeira posição intermediária e depois eu tenho a primeira condição intermediária ou segundo comando segundos segundo a condição intermediária eu vou até a
última e também diária o último comando E aí sim eu tenho a condição de saída que a última condição que vocês perceberam tenho vários comandos no caso eu vou ter várias tripas de Coari no mesmo código então eu posso ter o mesmo problema no mesmo código várias pipas de voar em um para cada comando que tiver lá no meu código Ah tá e como que a gente olha gente já entender um pouco da nomenclatura e como a gente representa o código através da tripa devorado tô nesse caso aqui algum pegar um exemplo e vamos tentar
demonstrar a correção que a gente quer demonstrar conheçam ver se o algoritmo tac certo uma forma da gente ver se o algoritmo tac certo é pelo axioma de atribuição na questão de atribuição a gente vai escrever uma tripa The Who are a gente vai começar pela pós-condição a gente vai ver atribuição que foi feita ou seja o comando que foi realizado a gente faz aquele comando e ver se quando a gente faz isso comando a pré-condição e 700 a gente faz trás para frente a gente começa pela pós-condição ver a atribuição feita e aí depois
a gente vê que se sabe sais também lá pré-condição então ele esse programa aqui ó eu tenho uma condição de entrada x maior que 16 eu só posso colocar valores maior que um de entrada ok Oi e aí o programa ele vai fazer o seguinte ele vai pegar a entrada que foi dada vai tirar um e vai atualizar esse valor então eu dei um valor de entrada maior que um que queria fazer vai pegar esse valor tira um e vai atualizar Uma Só Notícias EA condição de saída tem que ser maior que zero então um
casinho sim em caso simples de algoritmo no minhas entradas tem ser todos Marques um a minha atribuição meu comando é esse e minha condição sair daqui tem que ser Marco Zero que você positivo E então é só como que ficaria tripla de Royale no caso tempo demora aqui o que é Nossa pré-condição o p q é nosso comando o r a nossa posse quando são como que eu escreveria tripla de Coari nesse caso aqui ó desse jeito aqui ó a pré-condição é x maior que 1 o comando que a gente vai ter é o x
igual a x menos 1 e após quando são esses Marco Zero Thor nos colocar no lugar do que a pretensão no lugar do p o nosso código um lugar do r a nossa pós-condição como que eu demonstro eu demonstro de trás para frente então seguinte eu começo lá da pós-condição que no caso a gente tem o seguinte que aqui É pré-condição e aqui a pós-condição eu começo lá pela pós-condição começa trás para frente posso condição é o seguinte X tem que ser maior que zero será que quando eu faço essa atribuição aqui eu chego nessa
pré-condição aqui vamos ver X marquise em qualquer atribuição atribuições x receber x menos 1 né então no lugar do X eu troco por x - 1 Ah então tá essa daqui é a pós-condição que que eu fiz aqui eu fiz atribuição a atribuição é trocar o X por Silvano um beleza troquei Será que eu chego na pré-condição vamos ver vou passar o x ou menos um para lá bom o menos um passa para lá positivo x Mark um Então é só quando eu fiz atribuição eu consegui a partir da atribuição chegar nisso daqui isso daqui
é exatamente quem é pré-condição seja conseguir chegar na pré-condição Ah então quer dizer que verifiquei aqui ó tá verificado nesse caso é coerente é coerente o que essa pré-condição com essa pós-condição através dessa atribuição está coerente então perceba que eu comecei de trás para frente eu peguei a pós-condição x Marco Zero eu fiz atribuição Ou seja eu troquei o X por x menos 1 aí eu passei o menos um para lá um ficou exatamente a pré Ou seja quando eu peguei após e fiz atribuição eu consegui chegar na pré-condição pronto verificado aqui esse jeito que
a gente vai fazer vamos ver um outro caso nós vamos pegar esse programa aqui ó esse problema que que tá fazendo Olha só um sempre que é temporário recebe x depois o x recebe o y depois o y recebe esse temporário e esse programa que ele tá fazendo ele tá pegando valores ele tá dando como entrada dos valores e depois a gente tá mudando de lugar então no caso aqui ó ele pega da como entrada dois valores A e B E no caso x vai ser o y vai ser b e ele quer fazer de
um jeito aqui depois ele Troque em vez de ser AB troca a posição fica ba Ou seja no caso x fica bem o y ficar é isso que esse problema tá fazendo bom então perceba que ele vai pegar aqui ó temporário vai receber o valor de X depois o x recebe de Y ou seja x agora vale y e depois o isso não recebe o valor do temporário quem quer temporário x você já teve a troca então no caso esse código aqui esse código para fazer a troca então tem o valor de x e y
e eu consigo trocar o x vale o que vale antes do y y é o que vale antes do X Então esse programa fazer a troca será que esse programa tá correto vamos fazer a demonstração de correção esse problema então é o seguinte só o que que a gente tem a gente tem lá uma pré-condição andando vou colocar aqui que essa daqui ó a pré-condição é isso eu dou como entrada x A Y B e eu vou fazendo vários comandos Qual é o primeiro comando o tempo e recebe x aí vou ter uma outra condição
intermediária o outro comando x = y depois eu vou ter outro intermediária o outro comando Y igual tempo e aí eu a pós-condição no caso aqui ó quê que a gente tem essa daqui é a pós-condição Oi e essa daqui é a pré o que a gente vai entrar com o valor lá para x e o valor B para y e a saída tem que ser o contrário Então como que a gente vai demonstrar Vamos demonstrar que o Sax Tá certo pela técnica do voar utilizar o tempo de Glória que é o acção de distribuição
tão lá Vamos aos a questão da distribuição para fazer demonstração de correção desse algoritmo por onde eu começo eu começo de trás para frente só que eu vou começar de baixo para cima Então vou começar pela pós-condição após condições seguinte o x vale um valor B Oi e o y vale a Ok porque a gente comer após condição é trocar a entrada essa seria entrada essa seria pré essa seria posta Será que se eu começar pela após e fazer as atribuições que estão feitas aqui essa última resposta é a pré se isso acontecer quer dizer
que eu consegui verificar ele a validade do programa consegui fazer a demonstração de correção do problema então lá vamos começar comecei com após né Lembrando que esse daqui é a pós-condição eu posso condição então seguinte o X tem que vai ser o valor de B em casa aqui e o Y tem que ser valor lá tá agora vamos fazer trás para frente você baixo para cima agora eu vou pegar aqui essa atribuição Y recebe o valor de tempo que nós não tem que ser o tempo o x vai mudar aqui não x continua bertaco x
não mudou nessa atribuição só que aqui o y e o tempo e tem que ser o mesmo valor no caso Y é a Então qual que é o valor que o tempo tem que ser bom tempo tem que será também o ok então já que o y tempo tem o mesmo valor Wilson é a então o tempo tem que será também ok cheguei numa outra acontecendo também de área agora eu vou agora de novo subir vamos fazer agora essa atribuição e ver qual que é a outra condição também que era aqui essa condição aqui é
o x = y aqui no caso aqui tem o tempo aqui não então tempo e vai continuar não tem tempo aqui sim mas no caso aqui o X tem que ser igual a y quem que o X é o X Ep então no caso aqui o Shelby como X tem que ser igual y y também tem que saber tá Wilson também tem que saber o ok cheguei aqui numa com centenas de ar Agora sim último passo para ver se a gente chega na praia condição Será que a gente chega no X = Y = B
você chegar realmente a gente conseguiu fazer a demonstração de correção pela pela opção de atribuição agora é o seguinte tempo igual a x aqui o y Gobbi tem aqui não então eles são igual a briga continua e agora que tem o tempo igual a x né o tempo e não é igual a sim se o tempo = x e o tempo é igual a quer dizer que o X tem que ser a talco X tem que ser cheguei eles daqui isso daqui é a pré-condição é é o que a gente queria chegar o x a
e o Y B a gente chegou no x A Y B então Exatamente isso daqui é a pré-condição beleza demonstrem pré é pa e agora mudou a grafia né da condição colocar na grafia atual a pré-condição e foi satisfeita Então vamos pegar a pós-condição e fazendas atribuições dos Comandos que foram que tem no nosso programa a gente chega na pré-condição quer dizer que a gente conseguiu demonstrar pelo a semana atribuição que esse algoritmo aqui é é Barbie do Ken Ok e agora seguinte só pra terminar vão ver a regra condicional regra condicional seguinte que se
a gente tem uma Incondicional nosso programa nessa que a gente tem wi-fi se a gente tiver um ser nosso programa olha só a entrada tem que ser 80 OK agora nós nosso programa eu não sei qual que vai vai acontecer porque era só a gente tem uns E se o y for menor que cinco então o y vai assumir o valor de y mais um senão o y vai ter atribuição 5 em dife EA que a gente tem a condição de saída que o y nesse caso aqui a gente vai ter duas tripas de Rory
e para caso essa condição sente satisfeita e uma caso ela não seja satisfeita então quando eu tenho uma um condicional eu tenho duas tripas de Glória vamos ver aqui as duas Perfect várias seguinte ó a entrada vai ser de São 10 aí eu vou fazer um e vamos supor que essa essa condição seja satisfeita satisfeita então Y igual a zero nas entrada nossa condição de entrada que é o que e y menor que 5 ou seja essa condição foi satisfeita então a o nosso comando vai ser y = y + 1 e a gente vai
ter que ter essa saída Y Ok Isso é uma têmpera de Hari Qual que é a outra tipo de voar a gente vai ter a condição de entrada aqui no casa controle entrada Y = 0 e vamos supor que essa condição não seja satisfeita tô no caso Y não é menor que 5 no caso isso seja maior ou igual a cinco no caso se isso não for maior gua5 aí já atribuição vai ser o y = 5 vai ser diferente e a saída é mesmo bom então perceba que o que a condição de entrada é
mesmo aí 300 a quantos anos a ideia mesma Y igual para igual um daqui porque a gente o exercício deu aqui né O que mudou mudou a que a gente vai ter um E aí a gente vai ver se essa condição essa aqui cento nos casos ele e para o menor que 5 qual que é atribuição realizada casa essa condição seja satisfeita que o Y8 mais um elsie ou seja e se essa não for satisfeita for acontecer o contrário dessa e tomar água cinco qual que é atribuição do El sí y = 5 Mas acontece
que olha só e aqui a condição de entrada não tem que ser ya0 Ok e não e UEL se no caso esquerdo wellson wellson Y maior cinco sim tem como y60 e maior que 5 ao mesmo tempo não então esse e já é falso o que que acontece eu lembro da implicação que a gente tem uma aplicação falso implica falso e falso não fica verdadeiro Não importa se é verdade as implicações verdadeira então nem preciso ver o resto porque esse aqui é falsa não preciso ver o resto agora E no caso aqui é verdadeiro né
porque ela só Y = 0 beleza e também na que sim beleza Isso é verdade então no caso aqui quando tem uma condicional eu vou escrever essas duas tripas de roari que como que é lembrando sempre de várias duas tipo de lá eu coloco a mesma condição de entrada mesmo quando sua saída só quer que eu coloco um e se acontecer condicional e aqui atribuição se acontecer condicional E aí coloca um e se não acontecer condicionar ou seja encontrar a medicação dela e aqui se não acontecer a condicional qualquer atribuição do Elson caso o que
for falso não preciso demonstrar você só demonstrar o que for verdadeiro então no caso aqui eu vou colocar essa tripla de Roar eu vou demonstrar essa turma de Rogério como que eu demonstro eu parto da pós-condição qualquer pó e são Y igual a 1 e o parto da pós-condição Y igual um faço essa atribuição aqui e vejo se eu chego na pré-condição vamos lá Y igual a um ok o Y não é vai reservar o dito mais um sim então vou trocar esse Y como ele pede para mais um eu vou trocar esse tão por
isso mais um Então o que eu não tenho Y = 1 ó eu tenho Y = 1 Ah tá mas o que que eu vou fazer eu vou trocar esse Y vou apagar esse isso e trocar ele por e pessoa mais um oi oi sou mais um e quem só que olha só esse Y mais um aqui ó eu vou trabalhando aqui ou todos daqui é verdade eu vou passar esse nunca lá que que acontece esse um passa - 11 - 1 Oi e aí eu tenho o quê que o y é zero Então olha
só troquei um Y para ele fica mais um esse um eu passei para lá e ficou ou menos 10 ou seja se eu troco nesse caso o Y por isso mais um eu chego no Y = 0 Y = 0 um exatamente a minha condição aqui de entrada assim e a gente não tem que esse y0 também menor que 5 sim Ah então beleza A gente chegou na nossa condição aqui na nossa pré-condição né gente chegou no Y = 0 que era o nosso que e a gente já sabia que esse que já sabe fazia
aqui então eu postei hoje eu posso falar que esse frango a zero é menor que 5 então é que eu demonstrei pela opção de atribuição aí a correção desse algoritmo Então é isso peguei a gente viu só alguns casos simples só para gente ver um pouquinho do uso da do nosso sistema de lógica formal que a gente viu na um pouquinho na comutação né nesse método desenvolvido aí por Rua área que a gente vê a tripa de voar e ver que são de atribuição e tenta fazer a demonstração aí de alguns Alguns comandos aí que
a gente pode fazer em alguns programas no computador Ok então por hoje é isso Até a próxima aula
