Lista_1

Prévia do material em texto

1)Verificação de programas 
Prove a correção
A)
{x=0}
Z=2*x+1;
Y=z-1;
{y=0}
R:
{x=0}
Z=2(0)+1 -> Z=1
Y=Z-1 -> Y=1-1 -> Y=0 (Pós condição satisfeita)
{Y=0}
B) {x = 7}
 If(x<=0) -> {Q e B}P{R} => {X<=0} Y=7{Y=14} Esta parte não executa
 Y=X;
 Else
 Y=2X; {Q e B}P{R} => {X=0} Y=14 {Y=14} Esta parte executa, então temos:
{Y=14}		{Y=0}
			Y=2x=>y=14
		{Y=14} -> Pós cond satisfeita
2) Utilize indução matemática para provar que: 
A) 4 + 10 + 16 + ... + (6n − 2) = n(3n + 1)
Passo 1: prova-se para a base(1)
(6.1-2)= 1(3.1+1)	
6-2=3+1
4=4
Ou seja:
4+10+...+16 + (6k-2)= k(3k+1)
Passo 2:Supor que valer para k -> vale para k+1
HIPÓTESE:
 4+10+16+...+(6k-2)+[6(k+1)-2] = (k.1).(3k+2)
Passo 3: Simplificar a expressão e ver se a hipótese é verdade
4+10+16+...+(6k-2) + [6(k+1)-2] =
k(3k+1) + [6(k+1)-2] =
3k² + k + 6(k+1)-2=
3k²+k+6k+6-2=
3k²+7k+4=
(k+1).(3k+2) Hipótese provada
B)5+10+15+…+5n = (5n[n+1])/2
Passo 1: Prova-se para a base(1)
5= (5.1.[1+1])/2
5=(5.2)/2
5=10/2
5=5	Base provada
	
 Passo 2: Supor que valer para k -> vale para k+1
 HIPÓTESE: 5+10+15...+5k+5(k+1)=[5(k+1).(k+2)]/2
 Passo 3: Simplificar a expressão e provar a hipótese
 5+10+15...+5k + 5(k+1)
 [5k(k+1)]/2 + 5(k+1)=
 [5k(k+1)]/2 + [2+2.5(k+1)]/2=
 {[5k(k+1)] + [2.5(k+1)]}/2=
 [(5k²+5k)+(10k+10)]/2=
 (5k²+5k+10k+10)/2=
 [5(k+1).(k+2)]/2 Hipótese Provada
 
3)Relações de recorência
A) T(1) = 1 T(n) = 2T(n-1) + 1 para n ≥ 2
T(1)=1
R:
T(N)=2T(n-1)+1 para n>=2
Ou seja:
T(N+1) = 2T(n)+1 para n>=2
Temos na forma recursiva:
T(1)=1
T(2)=2T(1)+1
T(3)=2T(2)+1
...
Anula-se os termos:
T(1)=1
T(2)=2T(1)+1 
T(3)=2T(2)+1
...
Chega-se na fórmula fechada:
1:Termo inicial
n-1 : todas as ocorrências até n, exceto o termo inicial
3: Razão da P.A
T(n)=1+(n-1).3