Aula03-Recorrencias.pptx

Prévia do material em texto

11/11/13	
  
1	
  
Relações	
  de	
  recorrência	
  
Matemá+ca	
  Discreta	
  II	
  
(Rosen	
  –	
  Cap.	
  8)	
  
	
  
André	
  Câmara	
  
Métodos	
  de	
  contagem	
  avançados	
  
•  Adequados	
  quando	
  os	
  métodos	
  vistos	
  
anteriormente	
  não	
  se	
  adequam	
  
•  Relações	
  de	
  recorrência	
  
•  Presente	
  no	
  contexto	
  de	
  paradigmas	
  como	
  
Programação	
  Dinâmica	
  e	
  Dividir	
  para	
  
Conquistar	
  
•  Quebrar	
  um	
  problema	
  em	
  sub-­‐problemas	
  
Relações	
  de	
  Recorrência	
  
•  Def.	
  Uma	
  Relação	
  de	
  Recorrência	
  (R.R.,	
  ou	
  apenas	
  
recorrência)	
  para	
  uma	
  sequência	
  {an}	
  é	
  uma	
  equação	
  
que	
  expressa	
  an	
  em	
  termos	
  de	
  um	
  ou	
  mais	
  elementos	
  
prévios	
  a0,	
  …,	
  an−1	
  da	
  sequência,	
  para	
  todo	
  n≥n0.	
  	
  
	
  
•  Uma	
  sequência	
  par+cular	
  (descrita	
  não	
  
recursivamente)	
  é	
  uma	
  solução	
  da	
  Relação	
  de	
  
Recorrência	
  se	
  ela	
  é	
  consistente	
  com	
  a	
  definição	
  da	
  
recorrência.	
  
•  Obs.	
  	
  
• Uma	
  Relação	
  de	
  Recorrência	
  pode	
  ter	
  muitas	
  
soluções.	
  
Exemplo	
  Coelhos	
  e	
  números	
  de	
  Fibonacci	
  
•  Um	
  casal	
  de	
  coelhos	
  é	
  deixado	
  em	
  uma	
  ilha.	
  
Coelhos	
  só	
  reproduzem	
  após	
  dois	
  meses	
  de	
  
idade.	
  Após	
  isso,	
  cada	
  casal	
  produz	
  um	
  outro	
  par	
  
por	
  mês.	
  Encontre	
  uma	
  relação	
  de	
  recorrência	
  
para	
  o	
  número	
  de	
  coelhos	
  na	
  ilha	
  após	
  n	
  meses,	
  
assumindo	
  que	
  nenhum	
  coelho	
  morre.	
  
Exemplo	
  Coelhos	
  e	
  números	
  de	
  Fibonacci	
  
f1=	
f2=	
fn=no. de casais no mês anterior	
	
 	
 	
 	
 	
+	
 no. de recém nascidos 	
(que é fn-2 pois cada novo par vem de um 
casal com pelo menos 2 meses de idade)	
fn=fn-1 + fn-2	
Exemplo	
  Torre	
  de	
  Hanoi	
  
•  Problema:	
  Mover	
  os	
  discos	
  do	
  pino	
  1	
  para	
  o	
  pino	
  
2.	
  
•  Regras:	
  	
  
a)	
  Mover	
  apenas	
  um	
  disco	
  por	
  vez.	
  
b)	
  Nunca	
  colocar	
  um	
  disco	
  maior	
  sobre	
  um	
  
menor.	
  
Peg #1 Peg #2 Peg #3 
11/11/13	
  
2	
  
Relação	
  de	
  Recorrência	
  Hanoi	
  
•  Seja	
  Hn	
  =	
  #	
  movimentos	
  para	
  uma	
  pilha	
  de	
  n	
  discos.	
  
•  Estratégia	
  ó+ma:	
  
•  Mover	
  n−1	
  discos	
  superiores	
  para	
  pino	
  livre.	
  (Hn−1	
  
movimentos)	
  
•  Mover	
  disco	
  inferior.	
  (1	
  movimentos)	
  
•  Mover	
  n−1	
  superiores	
  para	
  o	
  disco	
  inferior.	
  	
  
(Hn−1	
  movimentos)	
  
•  Note	
  que:	
  	
  	
  	
  	
  	
  Hn	
  =	
  2Hn−1	
  +	
  1	
  
•  O	
  #	
  de	
  movimentos	
  é	
  descrito	
  por	
  uma	
  
recorrência	
  
Resolvendo	
  RR	
  da	
  Torre	
  de	
  Hanoi	
  
Hn	
  =	
  2	
  Hn−1	
  +	
  1	
  
	
  	
  =	
  2	
  (2	
  Hn−2	
  +	
  1)	
  +	
  1	
   	
  =	
  22	
  Hn−2	
  +	
  2	
  +	
  1	
  
	
  	
  =	
  22(2	
  Hn−3	
  +	
  1)	
  +	
  2	
  +	
  1 	
  =	
  23	
  Hn−3	
  +	
  22	
  +	
  2	
  +	
  1	
  
	
  	
  …	
  
	
  	
  =	
  2n−1	
  H1	
  +	
  2n−2	
  +	
  …	
  +	
  2	
  +	
  1	
  
	
  	
  =	
  2n−1	
  +	
  2n−2	
  +	
  …	
  +	
  2	
  +	
  1	
  	
  	
  	
  	
  	
  (uma	
  vez	
  que	
  H1	
  =	
  1)	
  
	
  	
  	
  
	
  =	
  	
  
	
  
	
  	
  =	
  2n	
  −	
  1	
  
∑
−
=
1
0
2
n
i
i
Soma	
  dos	
  termos	
  de	
  uma	
  PG:	
  
RR	
  –	
  Torre	
  de	
  Hanoi	
  
•  Lenda:	
  
•  Monges	
  estão	
  transferindo	
  64	
  discos	
  de	
  ouro	
  de	
  
um	
  pino	
  para	
  o	
  outro,	
  seguindo	
  as	
  regras	
  do	
  
puzzle.	
  A	
  lenda	
  diz	
  que	
  o	
  mundo	
  irá	
  acabar	
  
quando	
  eles	
  terminarem.	
  Quanto	
  tempo	
  levará	
  
para	
  o	
  mundo	
  acabar	
  após	
  eles	
  começarem,	
  se	
  
eles	
  levam	
  1	
  segundo	
  para	
  mover	
  um	
  disco?	
  
•  Pela	
  fórmula:	
  2n	
  -­‐1	
  =	
  18.446.744.073.709.551.615	
  
movimentos.	
  
•  >	
  500	
  bilhões	
  de	
  anos	
  
	
  
Outro	
  Exemplo	
  
•  Encontre	
  uma	
  R.R.	
  e	
  condições	
  iniciais	
  para	
  um	
  
número	
  de	
  strings	
  de	
  bit	
  de	
  comprimento	
  n	
  sem	
  
dois	
  0’s	
  consecu+vos.	
  
•  Podemos	
  resolver	
  dividindo	
  uma	
  string	
  que	
  seja	
  
contada	
  em	
  casos	
  que	
  terminam	
  em	
  0	
  e	
  1.	
  
•  Para	
  cada	
  string	
  terminando	
  em	
  0,	
  o	
  bit	
  anterior	
  deve	
  ser	
  1,	
  e	
  
antes	
  dele	
  pode	
  vir	
  qualquer	
  string	
  de	
  tamanho	
  n−2.	
  
•  Para	
  cada	
  string	
  terminando	
  em	
  1,	
  pode	
  ter	
  uma	
  outra	
  string	
  
de	
  tamanho	
  	
  n−1.	
  
•  A	
  quan+dade	
  de	
  strings	
  de	
  bit	
  de	
  tamanho	
  n	
  
que	
  não	
  podem	
  ter	
  dois	
  0’s	
  consecu+vos	
  é	
  	
  
an	
  =	
  an−1	
  +	
  an−2.	
  	
  (Recorrência	
  de	
  Fibonacci)	
  
•  As	
  condições	
  iniciais	
  são:	
  a1	
  =	
  2	
  (0	
  e	
  1)	
  e	
  a2	
  =	
  3	
  .	
  
1 0 (n−2 bits) 1 (n−1 bits) 
Utilizando	
  a	
  recorrência	
  
•  Como	
  obter	
  a5?	
  
•  a1	
  =	
  2	
  (0,	
  1)	
  
•  a2	
  =	
  3	
  (01,	
  10,	
  11)	
  
•  a3	
  =	
  a2	
  +	
  a1	
  =	
  3+2	
  =	
  5	
  
•  a4	
  =	
  a3	
  +	
  a2	
  =	
  5+3	
  =	
  8	
  
•  a5	
  =	
  a4	
  +	
  a3	
  =	
  8+5	
  =	
  13	
  
Exemplo	
  Contagem	
  de	
  códigos	
  
•  Um	
  sistema	
  computacional	
  considera	
  uma	
  string	
  de	
  dígitos	
  
decimais	
  um	
  código	
  válido	
  se	
  ele	
  contém	
  um	
  número	
  par	
  
de	
  0’s	
  .	
  
•  Por	
  exemplo,	
  1230407869	
  é	
  válido,	
  enquanto	
  
120987045608	
  não	
  é.	
  
•  Solução:	
  	
  
•  Seja	
  an	
  o	
  número	
  de	
  códigos	
  válidos	
  de	
  n	
  bits.	
  
•  a1	
  =	
  9	
  
•  Os	
  outros	
  casos	
  dividem-­‐se	
  em:	
  
•  Qualquer	
  string	
  válida	
  de	
  tamanho	
  n−1,	
  acrescida	
  de	
  qualquer	
  
dígito	
  1-­‐9.	
  (an-­‐1+	
  D,	
  pode	
  ser	
  feito	
  de	
  9	
  formas)	
  
•  Qualquer	
  string	
  inválida	
  de	
  comprimento	
  n−1	
  digits,	
  acrescida	
  
de	
  0.	
  
•  Existem	
  10n-­‐1	
  strings	
  de	
  tamanho	
  n-­‐1.	
  Dessas,	
  an-­‐1	
  são	
  válidas.	
  Portanto:	
  
•  an	
  =	
  9an−1	
  +	
  (10n−1	
  −	
  an−1)	
  	
  	
  =	
  8an−1	
  +	
  10n−1.	
  
•  Caso	
  base:	
  a1	
  =	
  9	
  (1-­‐9).	
  
11/11/13	
  
3	
  
Resolvendo	
  Recorrências	
  
•  Algumas	
  recorrências	
  podem	
  se	
  resolvidas	
  por	
  
iteração	
  ou	
  outro	
  método.	
  Entretanto,	
  existe	
  
uma	
  classe	
  de	
  recorrências	
  que	
  pode	
  ser	
  
explícitamente	
  resolvida	
  de	
  forma	
  sistemá+ca.	
  
•  Def.	
  Uma	
  relação	
  de	
  recorrência	
  homogênea	
  
linear	
  de	
  grau	
  k	
  com	
  coeficientes	
  constantes	
  
(“k-­‐LiHoReCC”)	
  é	
  uma	
  RR	
  da	
  forma	
  
	
  an	
  =	
  c1an−1	
  +	
  …	
  +	
  ckan−k,	
  
onde	
  ci	
  ,	
  i=1...k,	
  são	
  números	
  reais	
  e	
  ck	
  ≠	
  0.•  A	
  solução	
  é	
  determinada	
  unicamente	
  pela	
  RR	
  e	
  	
  
pelas	
  k	
  condições	
  iniciais	
  a0…ak−1.	
  
k-­‐LiHoReCC	
  
•  Exemplos	
  de	
  k-­‐LiHoReCC:	
  
•  fn=fn-­‐1	
  +	
  fn-­‐2	
  	
  	
  	
  	
  	
  	
  (grau	
  2)	
  
•  an=an-­‐5	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  (grau	
  5)	
  
•  Não	
  são	
  	
  k-­‐LiHoReCC:	
  
•  an=an-­‐1	
  +	
  a2n-­‐2 	
  	
   	
  	
  (não	
  é	
  linear)	
  
•  Hn	
  =	
  2Hn−1	
  +	
  1	
  	
   	
  (não	
  é	
  homogênea)	
  
•  Bn	
  =	
  nBn-­‐1	
   	
   	
  (não	
  possui	
  coef.	
  const.)	
  
Resolvendo	
  LiHoReCC’s	
  
•  Ideia	
  principal:	
  buscar	
  soluções	
  do	
  +po	
  an	
  =	
  rn,	
  
onde	
  r	
  é	
  uma	
  constante.	
  
•  Isto	
  requer	
  resolver	
  uma	
  equação	
  caracterís+ca:	
  
	
  rn	
  =	
  c1rn−1	
  +	
  …	
  +	
  ckrn−k,	
  dividindo	
  por	
  rn-­‐k,	
  	
  
	
  rk	
  −	
  c1rk−1	
  −	
  …	
  −	
  ck	
  =	
  0	
  
•  As	
  soluções	
  r	
  para	
  esta	
  equação	
  são	
  chamadas	
  
raízes	
  caracterís+cas	
  da	
  LiHoReCC.	
  
•  Veremos	
  que	
  estas	
  podem	
  ser	
  usadas	
  para	
  dar	
  uma	
  
fórmula	
  explícita	
  para	
  todas	
  as	
  soluções	
  da	
  sequência	
  
an	
  =	
  c1an−1	
  +	
  …	
  +	
  ckan−k	
  
Resolvendo	
  2-­‐LiHoReCCs	
  
•  Considere	
  uma	
  2-­‐LiHoReCC	
  arbitrária:	
  
	
  an	
  =	
  c1an−1	
  +	
  c2an−2	
  
•  Ela	
  possui	
  equação	
  caracterís+ca	
  (E.C.):	
  	
  
	
  r2	
  −	
  c1r	
  −	
  c2	
  =	
  0	
  
•  Teorema.	
  Se	
  uma	
  E.C.	
  possui	
  2	
  raízes	
  r1≠r2,	
  então	
  
uma	
  das	
  soluções	
  para	
  a	
  RR	
  são	
  dadas	
  por:	
  
	
  an	
  =	
  α1r1n	
  +	
  α2r2n	
  	
  para	
  n≥0	
  
para	
  toda	
  e	
  qualquer	
  constantes	
  α1,	
  α2.	
  
Exemplo	
  
•  Resolva	
  a	
  recorrência	
  an	
  =	
  an−1	
  +	
  2an−2	
  dadas	
  as	
  
condições	
  iniciais	
  a0	
  =	
  2,	
  a1	
  =	
  7.	
  
•  Solução:	
  Usando	
  o	
  teorema	
  1:	
  
•  Temos	
  c1	
  =	
  1,	
  c2	
  =	
  2	
  
•  A	
  equação	
  caracterís+ca	
  é:	
  	
  	
  r2	
  −	
  r	
  −	
  2	
  =	
  0	
  
•  Resolvendo:	
  
•  	
  
	
  	
  	
  
•  Portanto,	
  r	
  =	
  2	
  	
  ou	
  r	
  =	
  −1.	
  
•  Dessa	
  forma,	
  an	
  =	
  α1	
  2n	
  +	
  α2	
  (−1)n.	
  	
  	
  	
  	
  
a
acbbx
cbxax
2
4
0
2
2
−±−
=
⇔=++
.1or 2
2
31
2
91
)1(2
)2)(1(4)1()1( 2
−=
±
=
±
=
−−−±−−
=r
Exemplo	
  (cont.)	
  
•  Para	
  achar	
  α1	
  e	
  α2,	
  precisamos	
  resolver	
  as	
  equações	
  para	
  
as	
  condições	
  iniciais	
  a0	
  e	
  a1:	
  	
  
	
   	
  a0	
  =	
  2	
  =	
  α120	
  +	
  α2	
  (−1)0	
  
	
  	
  	
  	
  	
  	
  	
  	
   	
  a1	
  =	
  7	
  =	
  α121	
  +	
  α2	
  (−1)1	
  
•  Simplificando,	
  temos	
  um	
  par	
  de	
  equações:	
  
	
   	
  2	
  =	
  α1	
  +	
  α2	
  
	
   	
  7	
  =	
  2α1	
  −	
  α2	
  
as	
  quais	
  podem	
  se	
  r	
  resolvidas	
  por	
  subs+tuição:	
  
	
   	
  α2	
  =	
  2−α1;	
  	
  	
  7	
  =	
  2α1	
  −	
  (2−α1)	
  =	
  3α1	
  −	
  2;	
  	
  
	
   	
  9	
  =	
  3α1;	
  	
  α1	
  =	
  3;	
  	
  	
  α2	
  =	
  −1.	
  
•  Usando	
  α1	
  e	
  α2,	
  a	
  resposta	
  final	
  é	
  :	
  	
  	
  an	
  =	
  3·∙2n	
  −	
  (−1)n	
  
Check: {an≥0} = 2, 7, 11, 25, 47, 97 … 
11/11/13	
  
4	
  
Raízes	
  degeneradas	
  
•  E	
  se	
  a	
  E.C.	
  r2	
  −	
  c1r	
  −	
  c2	
  =	
  0	
  possui	
  apenas	
  uma	
  raiz	
  
r0?	
  
•  Teorema.	
  Então,	
  
	
  an	
  =	
  α1r0n	
  +	
  α2nr0n,	
  	
  para	
  todo	
  n≥0,	
  
para	
  algumas	
  constantes	
  α1,	
  α2.	
  
Raízes	
  degeneradas	
  Exemplo	
  
•  Resolver	
  an	
  =	
  6an−1−9an−2	
  com	
  a0=1,	
  a1=6.	
  
•  A	
  E.C.	
  é:	
  r2−6r+9=0.	
  
•  Note	
  que	
  b2−4ac	
  =	
  (−6)2−4·∙1·∙9	
  =	
  36−36	
  =	
  0.	
  
•  Portanto,	
  existe	
  apenas	
  uma	
  raiz	
  
	
  −b/2a	
  =	
  −(−6)/2	
  =	
  3.	
  
•  Então	
  an	
  =	
  α13n	
  +	
  α2n	
  3n	
  
•  Para	
  achar	
  α1	
  e	
  α2,	
  precisamos	
  resolver	
  as	
  equações	
  
para	
  as	
  condições	
  iniciais	
  a0	
  e	
  a1:	
  	
  
	
   	
  a0	
  =	
  1	
  =	
  α130	
  +	
  α2	
  .	
  0	
  .	
  (3)0	
  =>	
  3α1	
  =	
  1	
  
	
  	
  	
  	
  	
  	
  	
  	
   	
  a1	
  =	
  6	
  =	
  α131	
  +	
  α2	
  .	
  1	
  .	
  (3)1	
  =>	
  3α1	
  +	
  3α2=	
  6	
  
Subs+tuindo	
  temos,	
  1	
  +	
  	
  3α2=	
  6	
  	
  =>	
  	
  α2=	
  5/3	
  e	
  α1=	
  1/3	
  
Dessa	
  forma,	
  an	
  =	
  (1/3)3n	
  +	
  (5/3)	
  n	
  3n	
  =	
  3n-­‐1	
  +	
  5n	
  3n-­‐1	
  
Exercício	
  
•  Encontre	
  uma	
  fórmula	
  explícita	
  para	
  os	
  números	
  
de	
  Fibonacci	
  
•  Lembrando:	
  fn	
  =	
  fn-­‐1	
  +	
  fn-­‐2	
  ,	
  e	
  f0=0	
  e	
  f1=1	
  
Exercício	
  
•  Encontre	
  uma	
  fórmula	
  explícita	
  para	
  os	
  números	
  
de	
  Fibonacci	
  
•  Lembrando:	
  fn	
  =	
  fn-­‐1	
  +	
  fn-­‐2	
  ,	
  e	
  f0=0	
  e	
  f1=1	
  
•  E.C.:	
  r2	
  –	
  r	
  –	
  1	
  =	
  0	
  ,	
  possui	
  raízes	
  
fn =α1
1+ 5
2
!
"
#
$
%
&
n
+α2
1− 5
2
!
"
#
$
%
&
n
r1 = (1+ 5) / 2 r2 = (1− 5) / 2
f0 =α1 +α2 = 0
f1 =α1
1+ 5
2
!
"
#
$
%
&
n
+α2
1− 5
2
!
"
#
$
%
&
n
=1
α1 =1/ 5
α2 = −1/ 5