Aulas 9,10 Fábio Nakano. Definições, teoremas e algoritmos Definição é uma especificação...

Aulas 9,10

Fábio Nakano

Definições, teoremas e algoritmos

• Definição é uma especificação precisa de um objeto.• Um teorema é uma afirmação que pode ser

provada.• Podemos usar o resultado, ou,• Numa demonstração de um teorema, pode-se

construir um objeto ou uma solução genérica com a finalidade de demonstrar o teorema.

• Então a demonstração é um algoritmo para a construção do objeto ou da solução.

Exemplos

• Definição: n!=n*(n-1)! E 0!=1• Construa um método (iterativo) que calcula n!

Por que preciso saber demonstrar?

• Demonstrar é a maneira de ter certeza que algo é verdadeiro ou falso;

• Quando argumentamos com alguém, o que procuramos é uma demonstração de que o que defendemos é verdadeiro.

• Não há argumento contra uma demonstração formal.

• Uma demonstração apresenta um algoritmo para solução do problema.

Técnicas de Demonstração

• Prova Direta• Contradição• Indução

Demonstrações Típicas

• Prove por contradição que 2 não pertence a Q.

• Prove que n<2n para n N.

2 não pertence a Q

• Suponha por absurdo que 2=m/n, com m e n pertencendo a Z e m/n irredutível.

• Elevando ao quadrado temos 2=m2/n2.• Então m2=2*n2. Logo m2 é par, consequentemente, m é par.• Se m é par podemos escrever m como 2*k• Como m2=2*n2 , então, (2*k)2=2*n2.• Então 22*k2=2*n2

• Logo, 2*k2=n2 portanto n também é par• Se m e n são pares, m/n é redutível, o que é uma

contradição.• Portanto 2 não pertence a Q.

n<2n para n N, Prova direta

• Chamemos f(n)=n e g(n)=2n .• Note que as duas funções são crescentes.• Considere n=0: f(n)=0 e g(n)=1, logo g(0)>f(0).• A cada incremento de uma unidade sobre n (n é

Natural, esse incremento faz n passar por todos os elementos do conjunto N), f(n) cresce de 1 e g(n) dobra. Logo g(n) cresce mais rápido que f(n).

• Como inicialmente g(0) é maior que f(0) (note que na sequencia de incrementos, zero é o menor valor), então para todo nN, g(n)>f(n).

Indução matemática• A técnica da indução apresenta uma maneira de resolver

problemas através da resolução de problemas menores!!

• Mecânica– Mostre que funciona para um n0 pequeno– Suponha por hipótese que vale para um n– Demonstre que se vale para n, vale para n+1– Por que funciona??

• Base• Hipótese• Passo

Prove por indução que n^2>2n+1 para n>2

Como um teorema melhora nossa vida...

• Construa um método que calcula a soma dos n primeiros inteiros (“pela definição”)

• Teorema 1: A soma dos n primeiros inteiros, s(n), vale n(n+1)/2

• Construa um método que calcula a soma dos n primeiros inteiros usando o Teorema 1

• Compare as complexidades.

Exemplo suplementarn<2n para n N, Prova por indução

• Base: para algum valor pequeno, mostrar que é verdade: Para n=0, a sentença é 0<1, que é verdadeira.

• Hipótese: para algum k, k<2k

• Passo: k+1<?2k+1

• Prova: k+1<? 2k+2k

• Pela HI, 2k+1? 2k+2k Note que como substituí um valor por outro MAIOR que ele, então posso relaxar a desigualdade . Esta nova desigualdade “tem menos folga”. Se eu conseguir provar esta nova desigualdade, “vô tá bem na fita!”

• Cancelando: 1 ? 2k .• Note que 2k é crescente e para k=0, a desigualdade é verdade, então

para os k>0, ela vai continuar sendo verdade! Portanto n<2n para n N.

Pondo tudo em ordem

• Base: 20>0• Por hipótese, 2k>k• Some 1 a ambos os lados: 2k+1>k+1 • É claro que 2k+2k é maior que 2k+1, então

podemos substituir 1 por 2k pois não alteramos as desigualdades.

• Note que 2k+2k=2k+1

• Logo, 2k+1>k+1.

Recursão

• É um conceito em computação.• É relacionado ao conceito de indução pois• É uma forma indutiva de definir programas.• Nesta, um método chama a si mesmo com os

parâmetros adequados.

Exemplo

• Definição: n!=n*(n-1)! E 0!=1• Construa um método recursivo que calcula n!

Como se implementa recursão em um computador?

• TAD - Pilha• Prog - Pilha de execução• Prog – Chamada de função• Prog - Recursão

Como o método recursivo calcula 4!

Projeto coletivoQuantos grupos já concluiram o projeto?

Tempo de execução (ns)

Número de comparações

comprimento do vetor

8696279276 391986000 2800018627460753 840479500 41000

2888617408 199990000 2000013134217896 903103750 42500

3355019982 231114250 215001048894482 71994000 12000

6107759 499500 1000

São aprox. 11 grupos

• 1 roda problemas de tamanho até 2000 em intervalos de 10

• 2 rodam problemas de 2000 a 20000 em intervalos de 100

• 3 rodam problemas de 20000 até 40000 em intervalos de 200

• 5 rodam problemas de 40000 até 60000 em intervalos de 500

• Roda por algumas horas (6?), pode (deve) paralelizar

Lista para 15.09

• Prove por indução que 2^n>n^2 defina n0, o valor mínimo para que sua demonstração seja válida.

• Dê uma prova direta e uma por indução de que

• Apresente os códigos (ou pseudo-códigos) dos métodos que calculam s(n) pela definição (iterativo e recursivo) e usando o resultado do teorema. Qual a complexidade de tempo de cada método? Apresente a simulação da pilha de execução para n=3.

1,1

*)(1

1

1

rr

ararans

nn

i

i

1,1

*)(1

1

rr

ararans

nn

i

i

Diga se é verdadeiro e justifique usando a definição da notação O-grande

)2(2

23

)()log(*

))log(*(

)(

)(2

22

)(

2

2

2

nn

O

nOnn

nnOn

nOn

nOn

nOn