PAA_Aula8_10_04_19

Prévia do material em texto

Técnicas de Análise de Algoritmos
Corretude de Algoritmos
UNIVERSIDADE DO ESTADO DO RIO GRANDE DO NORTE – UERN
FACULDADE DE CIÊNCIAS EXATAS E NATURAIS
DEPARTAMENTO DE INFORMÁTICA
MESTRADO EM CIÊNCIA DA COMPUTAÇÃO
Disciplina: Projeto e Análise de Algoritmos
Professores: Francisco Chagas de Lima Júnior
Carlos Heitor Pereira Liberalino
Mossoró, Abril de 2018
Sumário
❑ Indução Matemática 
❑ Corretude de Algoritmos
▪ Recursivos
▪ Não recursivos 
❑ Invariante de Laço
Indução Matemática
❑ A indução matemática é uma técnica de prova
poderosa, usada para obter resultados em uma
grande variedade de objetos discretos, tais com:
▪ Complexidade de Algoritmos
▪ Corretude de Algoritmos
▪ Teoremas sobre grafos e árvores
▪ E uma grande quantidade de inequações.
Indução Matemática
❑ Princípio:
Seja P(n) uma sentença definida para os inteiros n, e
seja n0 um inteiro fixo. Suponha que as duas afirmações
seguintes sejam verdadeiras:
❑ P(n) é verdadeira (TRUE)
❑ Para todos os inteiros k  n0, se P(k) é V então P(k+1) é V
Logo, a afirmação para todos os inteiros n  n0, P(n) é
(TRUE).
Indução Matemática
❑ A prova por indução matemática de que P(n) é
verdadeira para todo inteiro n consiste de dois
passos:
▪ Passo base:
A proposição P(1) é verdadeira
▪ Passo indutivo:
A condicional P(k)→ P(k+1) é verdadeira para
todos os inteiros positivos k.
Indução Matemática
❑ O princípio da indução matemática pode ser
expresso pela seguinte regra de inferência:
[𝑃 𝑛0 ∧ ∀𝑘 𝑃 𝑘 → 𝑃 𝑘 + 1 ) → ∀𝑛𝑃 𝑛 .
❑ Numa prova por indução matemática não é
assumido que P(k) é verdadeiro para todos os
inteiros. É mostrado que se for assumido que
P(k) é verdadeiro, então P(k+1) também é
verdadeiro.
Indução Matemática
❑Exemplo 0:
Mostre que o numero de linhas em uma tabela verdade,
para qualquer n  N proposições, e dado por 2n.
Indução Matemática
◼ Exemplo 0 (Cont.):
◼ Passo Base: P(1) = 21 = 2 e verdade, pois uma
proposições tem dois valores possíveis.
◼ Passo Indutivo: Supor que P(k) = 2k
◼ Provar que: P(k + 1) = 2k+1
Pela hipótese de indução tem-se:
𝑃(𝑘 + 1) = 2𝑃(𝑘)
𝑃(𝑘 + 1) = 2(2𝑘)
𝑃(𝑘 + 1) = 2𝐾+1
Pela hipótese de indução tem-se:
Indução Matemática
❑ Exemplo 1:
Prove que para todos inteiros 𝑛 ≥ 1, σ𝑖=1
𝑛 𝑖 =
𝑛(𝑛+1)
2
▪ Passo Base:
𝑃(1) , para 𝑛0 = 1 , P(1) = 1(1 + 1)/2 = 1 , logo a
fórmula é verdadeira para 𝑛0 = 1
▪ Passo Indutivo:
Se a fórmula é verdadeira para n = k então deve ser
verdadeira para 𝑛 = 𝑘 + 1, ou seja,
𝑃(𝑘) → 𝑃(𝑘 + 1) é (𝑇𝑅𝑈𝐸).
Indução Matemática
❑Exemplo 1 (Cont.):
▪ Supondo que a fórmula é verdadeira para 𝑛 = 𝑘 então
𝑃 𝑘 : 1 + 2 +⋯+ 𝑘 =
𝑘 𝑘+1
2
,
para algum inteiro 𝑘 > 1.
▪ Deve-se mostrar então que:
𝑃 𝑘 : 1 + 2 +⋯+ (𝑘 + 1) =
𝑘 + 1 (𝑘 + 2)
2
Indução Matemática
1 + 2 +⋯+ 𝑘 + 𝑘 + 1 =
𝑘 𝑘 + 1
2
+ (𝑘 + 1)
=
𝑘 𝑘+1 +2𝑘+2
2
=
𝑘2+𝑘+2𝑘+2
2
=
𝑘2+3𝑘 +2
2
=
(𝑘+1)(𝑘+2)
2
Exemplo1 (Cont.):
Indução Matemática
EXERCÍCIOS:
1. Verifique para todo 𝑛 > 1 que, 𝑃 𝑛 : σ𝑖=0
𝑛 𝑖 =
𝑛(𝑛+2)
2
2. Para todos os inteiros n 0 e todos os reais 𝑟, 𝑟 ≠ 1 prove
que, 𝑃 𝑛 : σ𝑖=0
𝑛 𝑟𝑖 =
𝑟𝑛+1−1
𝑟−1
3. Prove que P(n): 22𝑛
− 1é divisível por 3, para todo n 1.
4. Prove que, para n 0, 𝑃 𝑛 : σ𝑖=0
𝑛 2𝑖 = 2𝑛+1 − 1
5. Prove que 𝑃(𝑛): 𝑛3 − 𝑛 é divisível por 3 , para todo
𝑛 ≥ 1.
6. Provar que uma árvore binária completa com n níveis tem
exatamente 2𝑛 − 1 nós.
Corretude de Algoritmos
◼ Quando esta maquina está correta
◼ E quando não está?
Corretude de Algoritmos
❑Corretude Parcial - Um algoritmo e
parcialmente correto se, para todas as instâncias
do problema, ele termina com a resposta
correta.
❑Como ter certeza que um algoritmo sempre
produz a resposta correta?
▪Testes exaustivos.
▪Técnicas de demonstração Matemática.
“Testes servem apenas para provar que um algoritmo tem erros, nunca
para provar que está correto.” (Dijkstra)
Corretude de Algoritmos
❑ A preocupação com a corretude de um algoritmo tem
como objetivo garantir que em qualquer possível
execução deste, cada bloco execute exatamente o que
se espera que ele faça.
❑ Para isso se faz necessário:
▪ Identificar o que deve ser feio por cada bloco
▪ Identificar o estado antes do bloco executar
▪Avaliar o efeito do bloco sobre o estado
▪Caracterizar o estado após a execução do bloco
Corretude: Algoritmos Recursivos
❑Existe uma analogia entre os algoritmos
recursivos e o princípio da indução Matemática.
❑Assim, para resolver um problema P desenvolve-
se o projeto de algoritmo em dois passos:
1.Exibir a resolução de uma ou mais instâncias
pequenas de P (caso base);
2.Exibir como a solução de toda instância de P pode
ser obtida a partir da solução de uma ou mais
instâncias menores de P.
Corretude: Algoritmos Recursivos
❑O desenvolvimento de projeto análogo ao
processo indutivo resulta em algoritmos
recursivos, onde:
▪A base da indução:
Corresponde à resolução dos casos base da recursão;
▪A aplicação da hipótese de indução:
Corresponde a uma ou mais chamadas recursivas;
▪O passo da indução:
Corresponde ao processo de obtenção da resposta para
o caso geral, a partir daquelas devolvidas pelas
chamadas recursivas.
Corretude: Algoritmos Recursivos
❑ São benefícios imediatos do projeto baseado no
processo indutivo:
▪ Possibilidade de provar a corretude do
algoritmo.
▪ A complexidade do algoritmo resultante é
expressa numa recorrência.
▪ Frequentemente o algoritmo é eficiente,
embora existam exemplos simples em que
isso não acontece.
Corretude: Algoritmos Recursivos
❑ Corretude de algoritmos usando indução:
1. Definir a proposição a ser provada
2. Caso base: Condição de parada da recursão
3. Assumir que as chamadas recursivas estão
corretas
4. Usar esse argumento para provar que a
execução corrente é correta (passo indutivo).
Corretude: Algoritmos Recursivos
❑ Exemplo 1: Corretude de Fatorial Recursivo:
▪Conjectura: FAT(n) = n!, para n>0.
▪Passo base: Se n = 0, então FAT(n) = 1. Isso e correto
já que 0!=1.
▪Hipótese Indutiva: Assumir que FAT(k)=k!:
▪Provar que: 𝐹𝐴𝑇(𝑘 + 1) = (𝑘 + 1)!:
𝐹𝐴𝑇(𝑘 + 1) = (𝑘 + 1)𝐹𝐴𝑇(𝑘)! pela hipótese indutiva:
𝐹𝐴𝑇(𝑘) = 𝑘!, então:
𝐹𝐴𝑇(𝑘 + 1) = (𝑘 + 1)𝑘! = (𝑘 + 1)!
Corretude: Algoritmos Recursivos
❑ Exemplo 2: Corretude do algoritmo que retorna o
máximo de um vetor A de n elementos.
▪ Conjectura: Para todo 𝑛 ≥ 1:
𝑀𝐴𝑋𝐼𝑀𝑂(𝐴, 𝑛) = 𝑀𝑎𝑥{𝑀𝐴𝑋𝐼𝑀𝑂(𝐴, 𝑛 − 1), 𝐴[𝑛]}.
▪ Passo base: Se 𝑛 = 1, então:
𝑀𝐴𝑋𝐼𝑀𝑂(𝐴, 1) = 𝑀𝑎𝑥{𝐴[1]}. Verificação trivial.
▪ Hipótese Indutiva: Assumir que:
𝑀𝐴𝑋𝐼𝑀𝑂(𝐴, 𝑘) = 𝑀𝑎𝑥{𝑀𝐴𝑋𝐼𝑀𝑂(𝐴, 𝑘 − 1) , 𝐴[𝑘]} é verdade.
Corretude: Algoritmos Recursivos
❑ Exemplo 2: Corretude do algoritmo que retorna o
máximo de um vetor A de n elementos (Cont.).
▪ Provar que:
𝑀𝐴𝑋𝐼𝑀𝑂 𝐴, 𝑘 + 1 = 𝑀𝑎𝑥 𝑀𝐴𝑋𝐼𝑀𝑂 𝐴, 𝑘 , 𝐴 𝑘 + 1
Pela hipótese de indução
𝑀𝐴𝑋𝐼𝑀𝑂(𝐴, 𝑘) = 𝑀𝑎𝑥{𝑀𝐴𝑋𝐼𝑀𝑂(𝐴, 𝑘 − 1) , 𝐴[𝑘]}, assim:
𝑀𝐴𝑋𝐼𝑀𝑂(𝐴, 𝑘 + 1) = 𝑀𝑎𝑥{𝑀𝐴𝑋𝐼𝑀𝑂(𝐴, 𝑘), 𝐴[𝑘 + 1]}
Corretude: Algoritmos Recursivos
❑Exemplo 3: Corretude de Fibonnaci Recursivo:
▪𝐹0 = 0, 𝐹1 = 1, 𝑛 ≥ 2, 𝐹𝑛 = 𝐹𝑛−1 + 𝐹𝑛−2
Algoritmo Fib(n)
Se (n  1) então
Return n
Else
Return Fib(n-1)+Fib(n-2)
Corretude: Algoritmos Recursivos
❑ Exemplo 2: Corretude de Fibonnaci Recursivo:
▪ Conjectura: Para todo , 𝑛 ≥ 2,
𝐹𝑛 = 𝐹𝑛−1 + 𝐹𝑛−2 𝐹𝑛 = 𝐹𝑛+2 − 1
Passo base: Se 𝑛 = 0, então:
𝐹0 = 𝐹2 − 1 0 = F2 − 1 F2= 1,
Se 𝑛 = 1, então:𝐹1 = 𝐹3 − 1 1 = F3 − 1 F3 = 2, Hipótese
Indutiva: Assumir que:
𝐹𝑘 = 𝐹𝑘+2 − 1 é verdade, para todo 𝑘 > 2. 
Ou seja: 𝐹1 + 𝐹2 +⋯𝐹𝑘 = 𝐹𝑘+2 − 1
Corretude: Algoritmos Recursivos
❑ Exemplo 2: Corretude de Fibonacci Recursivo:
▪ Provar que:
𝐹𝑘+1 = 𝐹 𝑘+1 +2 − 1 ou seja:
𝐹𝑘+1 = 𝐹1 + 𝐹2 +⋯+ 𝐹𝑘 + 𝐹𝑘+1 = 𝐹𝑘+3 − 1
Pela hipótese de indução 𝐹𝑘 = 𝐹𝑘+2 − 1, então:
𝐹𝑘+1 = 𝐹1 + 𝐹2 +⋯+ 𝐹𝑘+2 − 1 + 𝐹𝑘+1 mas na séria de
Fibonacci
𝐹𝑘+2 + 𝐹𝑘+1 = 𝐹𝑘+3 , portanto:
𝐹1 + 𝐹2 +⋯+ 𝐹𝑘 + 𝐹𝑘+1 = 𝐹𝑘+2 − 1 + 𝐹𝑘+1 = 𝐹𝑘+3 − 1.
Corretude: Algoritmos Não Recursivos
Os algoritmos iterativos devem ter sua corretude verificada através
do uso de invariante de laço.
A estratégia “típica” para mostrar a corretude de um algoritmo
iterativo através de invariantes segue os seguintes passos:
1. Mostre que o invariante vale no início da primeira iteração
2. Suponha que o invariante vale no início de uma iteração
qualquer e prove que ele vale no início da próxima iteração.
3. Conclua que se o algoritmo pára e o invariante vale no início
da última iteração, então o algoritmo está correto.
Invariante de Laço
❑ Um invariante de laço (ou laço invariante) é uma propriedade que
relaciona as variáveis do algoritmo a cada execução completa de
uma laço de repetição no algoritmo.
❑ Um invariante de laço deve ser utilizado de modo que, ao término
do laço, tenha-se uma propriedade útil para mostrar a corretude do
algoritmo.
❑ A prova de corretude de um algoritmo requer que sejam
encontrados e provados invariantes para os vários laços que o
compõem.
❑ Em geral, é mais difícil descobrir um invariante apropriado do que
mostrar sua validade se ele for dado.
Invariante de Laço
❑ Para provar que uma Invariante I sobre um laço está
correta, deve-se:
1.Declarar a Invariante
▪ Propriedade relevante para se provar a corretude
2.Verificar o caso base:
▪ Deve valer antes de executar o laço
▪ e para o primeiro valor da variável de controle
3.Verificar se a propriedade se mantém a cada passo;
4.Aplicar a invariante ao caso final.
▪ Isto é, para o valor final da variável de controle
Invariante de Laço: Exemplo 0
Vamos assumir que para qualquer i, as linhas 2 a 4 calculam
a soma de V[1..i]. Assim, temos a seguinte abstração:
Algoritmo Média Acumulada:
Invariante de Laço: Exemplo 0 (cont.)
Se soma é o acúmulo de i valores, então M[i], após a
execução da linha 5, é necessariamente a média desses
valores. Isto nos leva a uma outra abstração.
◼ Algoritmo Média Acumulada:
◼ Abstração linhas 2-4:
Invariante de Laço: Exemplo 0 (cont.)
Analisando a abstração na linha 2-5, podemos definir qual
invariante de laço será útil.
Definição da invariante:
I : M[1..i-1] armazena as médias acumuladas de V[1..i-1].
◼ Algoritmo Média Acumulada:
◼ Abstração linhas 2-4:
Invariante de Laço: Exemplo 0
❑Algoritmo Média Acumulada:
VERIFICAÇÃO:
❑ Antes do início do laço (caso base):
▪para i=1, a condição I é trivialmente verdade, pois
M[1..0] e V[1..0] são vazios.
❑ Durante a manutenção do laço: (k-ésima execução)
▪Antes do laço deve-se assumir que I é verdade, ou
seja, que M[1..k-1] está ok.
▪Durante o laço, calcula-se M[k] corretamente ao atingir
o ponto da invariante, M[1..k] estará ok. Assim ao sair
do laço passo k+1, I também será verdadeira.
Invariante de Laço: Exemplo 1
Recebe dois números naturais m e n e devolve o máximo 
divisor comum dos mesmos (mdc(m, n)).
◼ Algoritmo do MDC (Euclides):
Invariante de Laço: Exemplo 1
Considere o caso: 𝑚 = 26 e
𝑛 = 44 e os valores de x e y
no inicio da iteração da
linha 3, dados na tabela ao
lado:
Definição da Invariante I: No início da iteração da linha 3 vale: 
𝑀𝐷𝐶(𝑚, 𝑛) = 𝑀𝐷𝐶(𝑥, 𝑦)
Propriedade fundamental: 𝑀𝐷𝐶 𝑥, 𝑦 = 𝑀𝐷𝐶(𝑦, 𝑥 𝑚𝑜𝑑 𝑦)
◼ Algoritmo do MDC (Euclides):
Invariante de Laço: Exemplo 1
❑ Algoritmo do MDC (Euclides):
VERIFICAÇÃO:
❑ Antes do início do laço (caso base):
Na primeira iteração, x = m e y = n, verificação imediata.
❑ Durante a manutenção do laço:
Suponha que vale o invariante em uma iteração. Ou seja,
MDC(m, n) = MDC(x, y).
Os novos valores de x e y na próxima iteração serão 𝑥′ = 𝑦 e
𝑦′ = 𝑥 𝑚𝑜𝑑 𝑦. Pela propriedade, segue que
𝑚𝑑𝑐(𝑚, 𝑛) = 𝑚𝑑𝑐(𝑥, 𝑦) = 𝑚𝑑𝑐(𝑥′, 𝑦′)
Invariante de Laço: Exemplo2 (cont.)
Lembrete: MDC(m, 0) = MDC(0,m) = m, para todo m ∈ N, m > 0.
Invariante de Laço: Exemplo 2
❑ Algoritmo Busca em Vetor:
Algoritmo Busca_em_Vetor(x, A)
Entrada: Um elemento x e um vetor A com n elementos
Saída: o índice i, tal que x=A[i], ou -1 se x não está em A.
1. i 0;
2. Enquanto i<n faça
3. Se x=A[i] então
4. Retorne i
5. senão
6. ii+1
7. Retorne -1
Definição da invariante I : x não é igual aos i primeiros elementos de A.
Invariante de Laço: Exemplo 2
❑Algoritmo Busca em Vetor:
VERIFICAÇÃO:
❑ Antes do início do laço:
▪ A afirmação I é verdadeira no início da primeira iteração do laço,
já que não existem elementos entre os primeiros i=0 elementos
de A.
❑ Durante a manutenção do laço:
▪ Na iteração i, compara-se o elemento x com o elemento A[i] e
retorna-se o índice i se eles forem iguais, o que é correto e
completa o algoritmo. Se os elementos x e A[i] não são iguais
então incrementa-se o valor de i, e portanto I será verdadeira no
início da próxima iteração.
Invariante de Laço: Exemplo2 (cont.)
❑Algoritmo Busca em Vetor:
VERIFICAÇÃO (Cont.):
❑ Na saída do laço:
Se o laço Enquanto termina sem retornar um índice em
A, então teremos i=n, logo I será verdadeira no final do
laço, ou seja, não existem elementos em A que sejam
iguais a x. Assim, o algoritmo estará correto, pois
retornará o valor -1 que é válido como índice.
Invariante de Laço: Exemplo 3
Definição da invariante: I : O subvetor A[1...j-1] do vetor original 
A, está ordenado.
◼ Algoritmo Ordenação Por Inserção:
Invariante de Laço: Exemplo 3
❑ Algoritmo Ordenação Por Inserção:
VERIFICAÇÃO:
❑ Antes do início do laço:
▪ Neste caso, temos 𝑗 = 2 e o invariante simplesmente
afirma que 𝐴[1 . . . 1] está ordenado, o que é evidente.
❑ Durante a manutenção do laço:
▪ Validade de uma iteração para outra: O algoritmo desloca
os elementos maiores que a chave para seus lugares
corretos e ela é colocada no espaço vazio.
Invariante de Laço: Exemplo3 (cont.)
❑Algoritmo Ordenação Por Inserção:
VERIFICAÇÃO (Cont.):
❑ Na saída do laço:
▪Na última iteração, tem-se 𝑗 = 𝑛 + 1 e logo
𝐴[1 . . . 𝑛] está ordenado com os elementos originais
do vetor. Portanto, o algoritmo está correto.
❑ A prova se baseia no fato de que no começo de cada
iteração do laço para das linhas 1– 8 , o subvetor
𝐴[1… 𝑗 − 1] é uma permutação ordenada do vetor
original 𝐴[1… 𝑛].
Invariante de Laço: Exemplo3 (cont.)
❑ Invariantes auxiliares – laço enquanto:
▪ 𝐼1: 𝐴[1 . . . 𝑖 ] e 𝐴[𝑖 + 2 . . . 𝑗 ] contém os elementos de 
𝐴[1 . . . 𝑗 ] antes de entrar no laço que começa na linha 5.
▪ 𝐼2 ∶ 𝐴[1 . . . 𝑖 ] e 𝐴[𝑖 + 2 . . . 𝑗 ] são crescentes.
▪ 𝐼3 ∶ 𝐴 1 . . . 𝑖 ≤ 𝐴[𝑖 + 2 . . . 𝑗 ]
▪ 𝐼4 ∶ 𝐴[𝑖 + 2 . . . 𝑗 ] > 𝑐ℎ𝑎𝑣𝑒.
Invariantes (I2) a (I4)
+ condição de parada na linha 5  Invariante (I)
+ atribuição da linha 7
Invariante de Laço: Múltiplos Laços
1. Analisar um laço por vez, começando pelo mais
interno se houver aninhamento de laços.
2. Para cada laço determinar um invariante de laço.
3. Provar que o invariante de laço é válido.
4. Mostrar que o algoritmo termina.
Invariante de Laço: Múltiplos Laços (Cont.)
5. Usar o invariante de laço para provar que o
algoritmo retorna o valordesejado.
6. Restringir a algoritmos com um laço:
▪ O valor do identificador x após a i-ésima
iteração de um laço é xi (i=0 indica o valor
de x imediatamente antes de iniciar o laço).
10/04/17 PAA - Corretude de 
Algoritmos
46
Invariante de Laço: Detalhes Importantes
❑ Considere dois elementos básicos:
1. Guarda: expressão booleana que indica se o corpo
do laço deve ou não ser executado.
2. Variante: expressão numérica que mede o quanto de
execução ainda falta.
Guarda: i  A.length
Variante: A.length - i +1
Invariante de Laço: Detalhes Importantes
❑ Um laço estará correto se as seguintes condições
forem satisfeitas:
1. Início: O invariante é verdadeiro antes de entrar no laço.
2. Invariância: o corpo do laço preserva o invariante.
3. Progresso: o corpo do laço diminui a variante.
4. Limitação: quando a variante atinge certo valor, a guarda
se torna falsa.
5. Saída: a negação da guarda e o invariante descrevem o
objetivo do laço.
Corretude Algoritmos: Técnicas
❑ Resumindo:
❑ Algoritmos recursivos: 
▪ Prova por indução
❑ Algoritmos iterativos:
▪ Invariantes de laço + indução