PAA-4-corretudeAlgoritmosRecursivos

Prévia do material em texto

Profa. Thaís Alves Burity Rocha 
CORRETUDE DE ALGORITMOS 
Agenda 
 Corretude de algoritmos 
 Indução matemática 
 Algoritmos recursivos 
 Corretude de algoritmos recursivos 
 Soma 
 Fibonacci 
 Fatorial 
Máximo valor 
Provar corretude de um algoritmo 
 Objetivo de provar que, para todas as instâncias 
do problema, o algoritmo obtém o resultado 
correto 
 Não é tarefa simples 
 “Testes servem para provar que um algoritmo 
tem erros, nunca para provar que está correto” 
(Dijkstra) 
 Abordagens: 
 Prova por indução 
 Invariantes de laço 
 
Indução matemática 
 Técnica de prova usada para mostrar que uma dada 
afirmação é verdadeira para todos os inteiros positivos 
 Uso comum em matemática e ciência da computação 
 Suponha que temos um assertiva P(n) em relação a 
todo n inteiro e positivo 
 Se mostrarmos que (I) e (II) é verdadeiro, então 
provamos que P(n) é verdadeiro para todo n≥0 
i. P(0) é verdadeiro 
ii. Para cada n≥1: Se P(n) é verdadeiro, então P(n+1) é 
verdadeiro 
 
Passos da prova 
 O texto de uma prova por indução consiste de 3 
partes: 
 Especificação da hipótese da indução: 
 P(n) 
O caso base: 
 P(0) 
O passo indutivo: 
 Para todo n≥1, P(n) → P(n+1) 
Exemplo 1: Identidade de Gauss 
 Prove que: 
 
 
 f(1) = 1 
 1 x (1 + 1)/2 = 1 
 
 f(2)= 1 + 2 = 3 
 2 x (2+1)/2 = 3 
 
 f(3) = 1 + 2 + 3 = 6 
 3 x (3+1)/2 = 6 
 
Exemplo 1: Identidade de Gauss 
 Hipótese de Indução (H.I.) 
 A própria identidade: 
 
 Caso base 
 n = 1 
 I(1) = 1 = 1x(1+1)/2 = 1 
 
 Passo indutivo 
 Provar que: 
 Utilizar a H.I. 
Exemplo 1: Prova por indução 
 Se considerarmos que 
 
 Basta provarmos que 
Exemplo 1: Provando por indução 
Exercício 1 
 Prove por indução que: 
Exercício 1: Resolução 
 Hipótese de Indução (H.I.) 
 A própria identidade: 
 
 Caso base 
 n = 1 
 I(1) = (2x1)-1=2-1=1 e 12=1 
 
 Passo indutivo 
 Provar que: 
 Utilizar a H.I. 
 
Exercício 1: Resolução 
 Se considerarmos que: 
 
 
 Basta provarmos que: 
 
 
Exercício 1: Resolução 
Exemplo 2: Número de linhas em uma 
tabela verdade 
Exemplo 2: Número de linhas em uma 
tabela verdade 
Exemplo 3: Árvore binária completa 
 Provar que uma árvore binária completa com n 
níveis tem exatamente nós 
1 
2 3 
4 6 7 
10 11 12 9 8 
5 
13 14 15 
Nível 0 
Nível 1 
Nível 2 
Nível 3 
Exemplo 3: Prova por indução 
 Caso base n=1 
 
 
 S(1) = 21 – 1 = 1 
 
 Passo indutivo 
 Provar que 
 
 
1 
Exemplo 3: Prova por indução 
 Para provar para n+1, considere que uma árvore é 
formada por nós internos (nós com filhos) e externos 
(nós sem filhos) 
Nós internos 
Nós externos 
1 
2 3 
4 6 7 5 
Exemplo 3: Prova por indução 
 Pode-se mostrar que o número de nós externos de 
uma árvore de n+1 níveis é igual a 2n 
 Assim, terminamos a prova se mostrarmos que: 
 Nós internos + Nós externos = S(n+1) = 2n+1-1 
 S(n) + 2n = S(n+1) = 2n+1-1 
 
Nós internos Nós externos 
 
 Desenvolvendo: 2n-1 + 2n = 2n+1 -1 
 
Algoritmos recursivos 
 Algoritmos recursivos chamam a si mesmos (uma ou mais 
vezes) para lidar com subproblemas intimamente 
relacionados 
 
 Bastante usados na solução de problemas computacionais 
 
 Divisão-e- conquista: 
 Dividir o problema em um determinado número de subproblemas 
 Conquistar os subproblemas, resolvendo-os recursivamente 
 Até que os subproblemas sejam pequenos o bastante para serem 
resolvidos de maneira direta 
 Combinar as soluções dadas aos subproblemas, a fim de formar 
a solução para o problema original 
Soma recursiva 
 Exemplo: Algoritmo recursivo que calcula a soma 
dos elementos do vetor A[1..n] 
 
Corretude de algoritmos recursivos 
 Provar por indução 
 Caso base é o caso base da recursão, ou seja, a 
condição de parada da recursão 
 Hipótese indutiva: as chamadas recursivas estão 
corretas 
 Passo indutivo: Usar H.I. para provar que a 
execução corrente é correta 
Soma recursiva: Prova de corretude 
 Caso base: 
 n=0 (i.e., vetor sem nenhum elemento) 
 Hipótese: 
 Assuma que a chamada Soma(n-1,A) está correta 
 Prova: 
 Se Soma(n-1,A) está correto, para n ≠0, a execução 
retornará a soma dos n-1 elementos do vetor mais o 
valor do elemento A[n]: 
 Soma(n-1,A) + A[n] 
 A[1]+A[2]+…+A[n-1]+A[n] = Soma(n,A) 
Sequência de Fibonacci 
Algoritmo de Fibonacci 
Algoritmo de Fibonacci: Prova de 
corretude 
 Caso base: 
 n=0; Fib(0) = 0 
 n=1; Fib(1) = 1 
 Hipótese: 
 Assuma que as chamadas Fib(n-1) e Fib(n-2) estão 
corretas 
 Prova: 
 Se Fib(n-1) e Fib(n-2) estão corretos: Para n>1, o 
algoritmo retornará corretamente Fib(n-1) + Fib(n-2) 
Exercício 1 
 Faça um algoritmo recursivo para calcular o fatorial 
de um número. Qual o caso base? Prove por 
indução que o algoritmo está correto. 
O fatorial de um número é definido como: 
 
 
 
 
 
 (15 minutos) 
 
 
 
Exercício 1: Solução 
 
 
 
 Caso base: 
 n=0 (i.e., vetor sem nenhum elemento) 
 Hipótese: 
 Assuma que a chamada Fat(n-1) está correta 
 Prova: 
 Se Fat(n-1) está correto, para n ≠0, a execução retornará o 
fatorial dos n-1 elementos do vetor vezes n: 
 n x Fat(n-1) 
 n x (n-1)! = n! 
Fat(n) 
se n=0, então retorne 1 
senão, retorne [n x Fat(n-1)] 
Exercício 2 
 Encontrar o maior valor em um vetor A de n elementos 
 
 
 
 
 
 Qual o caso base do algoritmo? 
 Prove por indução 
 
 (5 minutos) 
 
Exercício 2: Solução 
 Caso base: 
 n=1: só há 1 elemento no vetor, o que significa que ele 
possui o maior valor 
 Hipótese: 
 Assuma que a chamada Maximo(n-1) está correta 
 Prova: 
 Se Maximo(n-1) está correto, para n>1, a execução 
retornará o valor máximo entre o sub-vetor A[1...n-1] e 
A[n] 
Exercício 3 
 Implemente e prove a corretude dos seguintes 
algoritmos em sua versão recursiva: 
 
Ordenação por seleção 
 
Ordenação por inserção 
 
Ordenação Bubble Sort 
 
Ordenação Merge Sort 
Referências 
 CORMEN, T. H.; LEISERSON, C. E.; RIVEST, R. L.; 
STEIN, C. Algoritmos: Teoria e prática. Tradução da 
Segunda edição Americana. Editora Campus, 2002. 
 
 GERSTING, Judith L., Fundamentos Matemáticos 
para a Ciência da Computação. LTC -Livros 
Técnicos e Científicos, 1982.