Análise de Algoritmos - Aula 05 (Guilherme)

Prévia do material em texto

Ana´lise de
Algoritmos
113859
Aula 5
Roteiro
Induc¸a˜o Finita
Avaliac¸a˜o de
Polinoˆmios
Exerc´ıcio
Roteiro da Aula 5
1 Induc¸a˜o Finita
Reforc¸ando a hipo´tese de induc¸a˜o
Sobre qual varia´vel?
2 Avaliac¸a˜o de Polinoˆmios
Primeira tentativa
Segunda tentativa
Terceira tentativa
3 Exerc´ıcio
Ana´lise de
Algoritmos
113859
Aula 5
Roteiro
Induc¸a˜o Finita
Reforc¸ando a
hipo´tese de
induc¸a˜o
Sobre qual
varia´vel?
Avaliac¸a˜o de
Polinoˆmios
Exerc´ıcio
Induc¸a˜o Finita
Mostrar que a propriedade P vale para todo n
• Base da induc¸a˜o: P (1);
• Passo da induc¸a˜o: P (n)
︸ ︷︷ ︸
Hipo´tese
=⇒ P (n + 1)
︸ ︷︷ ︸
Tese
, ∀n ≥ 1.
Ana´lise de
Algoritmos
113859
Aula 5
Roteiro
Induc¸a˜o Finita
Reforc¸ando a
hipo´tese de
induc¸a˜o
Sobre qual
varia´vel?
Avaliac¸a˜o de
Polinoˆmios
Exerc´ıcio
Induc¸a˜o Finita
Mostrar que a propriedade P vale para todo n
• Base da induc¸a˜o: P (1);
• Passo da induc¸a˜o: P (n)
︸ ︷︷ ︸
Hipo´tese
=⇒ P (n + 1)
︸ ︷︷ ︸
Tese
, ∀n ≥ 1.
1 3 4 5 6 7 8 9 10 11 n2
n + 1n
Base
Passo
Ana´lise de
Algoritmos
113859
Aula 5
Roteiro
Induc¸a˜o Finita
Reforc¸ando a
hipo´tese de
induc¸a˜o
Sobre qual
varia´vel?
Avaliac¸a˜o de
Polinoˆmios
Exerc´ıcio
Induc¸a˜o Finita
• Base da induc¸a˜o: P (1);
• Passo da induc¸a˜o: P (n− 1)
︸ ︷︷ ︸
Hipo´tese
=⇒ P (n)
︸ ︷︷ ︸
Tese
, ∀n > 1.
Ana´lise de
Algoritmos
113859
Aula 5
Roteiro
Induc¸a˜o Finita
Reforc¸ando a
hipo´tese de
induc¸a˜o
Sobre qual
varia´vel?
Avaliac¸a˜o de
Polinoˆmios
Exerc´ıcio
Induc¸a˜o Finita
• Base da induc¸a˜o: P (1);
• Passo da induc¸a˜o: P (n− 1)
︸ ︷︷ ︸
Hipo´tese
=⇒ P (n)
︸ ︷︷ ︸
Tese
, ∀n > 1.
• Base da induc¸a˜o: P (1), P (2);
• Passo da induc¸a˜o: P (n)
︸ ︷︷ ︸
Hipo´tese
=⇒ P (n + 2)
︸ ︷︷ ︸
Tese
, ∀n ≥ 1.
1 3 4 5 6 7 8 9 10 11 n2
n
Base
Passo
n + 2
Ana´lise de
Algoritmos
113859
Aula 5
Roteiro
Induc¸a˜o Finita
Reforc¸ando a
hipo´tese de
induc¸a˜o
Sobre qual
varia´vel?
Avaliac¸a˜o de
Polinoˆmios
Exerc´ıcio
Induc¸a˜o Forte
• Base da induc¸a˜o: P (1);
• Passo da induc¸a˜o: P (i),∀i ≤ n− 1
︸ ︷︷ ︸
Hipo´tese
=⇒ P (n)
︸ ︷︷ ︸
Tese
, ∀n ≥ 1.
1 3 4 5 6 7 8 9 10 11 n2
Base
n− 1
Ana´lise de
Algoritmos
113859
Aula 5
Roteiro
Induc¸a˜o Finita
Reforc¸ando a
hipo´tese de
induc¸a˜o
Sobre qual
varia´vel?
Avaliac¸a˜o de
Polinoˆmios
Exerc´ıcio
Exemplo
• T (n) = T (n− 1) + 1, T (1) = 1
• Propriedade a ser provada: ∃c, n0{T (n) ≤ cn, ∀n ≥ n0}
Ana´lise de
Algoritmos
113859
Aula 5
Roteiro
Induc¸a˜o Finita
Reforc¸ando a
hipo´tese de
induc¸a˜o
Sobre qual
varia´vel?
Avaliac¸a˜o de
Polinoˆmios
Exerc´ıcio
Exemplo
• T (n) = T (n− 1) + 1, T (1) = 1
• Propriedade a ser provada: ∃c, n0{T (n) ≤ cn, ∀n ≥ n0}
• Hipo´tese: T (n− 1) ≤ c(n− 1)
• Tese: T (n) ≤ cn
Ana´lise de
Algoritmos
113859
Aula 5
Roteiro
Induc¸a˜o Finita
Reforc¸ando a
hipo´tese de
induc¸a˜o
Sobre qual
varia´vel?
Avaliac¸a˜o de
Polinoˆmios
Exerc´ıcio
Exemplo
• T (n) = T (n− 1) + 1, T (1) = 1
• Propriedade a ser provada: ∃c, n0{T (n) ≤ cn, ∀n ≥ n0}
• Hipo´tese: T (n− 1) ≤ c(n− 1)
• Tese: T (n) ≤ cn
T (n) = T (n− 1) + 1
Ana´lise de
Algoritmos
113859
Aula 5
Roteiro
Induc¸a˜o Finita
Reforc¸ando a
hipo´tese de
induc¸a˜o
Sobre qual
varia´vel?
Avaliac¸a˜o de
Polinoˆmios
Exerc´ıcio
Exemplo
• T (n) = T (n− 1) + 1, T (1) = 1
• Propriedade a ser provada: ∃c, n0{T (n) ≤ cn, ∀n ≥ n0}
• Hipo´tese: T (n− 1) ≤ c(n− 1)
• Tese: T (n) ≤ cn
T (n) = T (n− 1) + 1
≤ c(n− 1) + 1 subst. a hipo´tese
Ana´lise de
Algoritmos
113859
Aula 5
Roteiro
Induc¸a˜o Finita
Reforc¸ando a
hipo´tese de
induc¸a˜o
Sobre qual
varia´vel?
Avaliac¸a˜o de
Polinoˆmios
Exerc´ıcio
Exemplo
• T (n) = T (n− 1) + 1, T (1) = 1
• Propriedade a ser provada: ∃c, n0{T (n) ≤ cn, ∀n ≥ n0}
• Hipo´tese: T (n− 1) ≤ c(n− 1)
• Tese: T (n) ≤ cn
T (n) = T (n− 1) + 1
≤ c(n− 1) + 1 subst. a hipo´tese
= cn− c+ 1
Ana´lise de
Algoritmos
113859
Aula 5
Roteiro
Induc¸a˜o Finita
Reforc¸ando a
hipo´tese de
induc¸a˜o
Sobre qual
varia´vel?
Avaliac¸a˜o de
Polinoˆmios
Exerc´ıcio
Exemplo
• T (n) = T (n− 1) + 1, T (1) = 1
• Propriedade a ser provada: ∃c, n0{T (n) ≤ cn, ∀n ≥ n0}
• Hipo´tese: T (n− 1) ≤ c(n− 1)
• Tese: T (n) ≤ cn
T (n) = T (n− 1) + 1
≤ c(n− 1) + 1 subst. a hipo´tese
= cn− c+ 1
≤ cn desde que c ≥ 1
T (n) = O(n)
Ana´lise de
Algoritmos
113859
Aula 5
Roteiro
Induc¸a˜o Finita
Reforc¸ando a
hipo´tese de
induc¸a˜o
Sobre qual
varia´vel?
Avaliac¸a˜o de
Polinoˆmios
Exerc´ıcio
Tentativa de baixar a cota superior
• Tentativa: ∃c, n0{T (n) ≤ c logn, ∀n ≥ n0}
• Hipo´tese: T (n− 1) ≤ c log(n− 1)
• Tese: T (n) ≤ c logn
Ana´lise de
Algoritmos
113859
Aula 5
Roteiro
Induc¸a˜o Finita
Reforc¸ando a
hipo´tese de
induc¸a˜o
Sobre qual
varia´vel?
Avaliac¸a˜o de
Polinoˆmios
Exerc´ıcio
Tentativa de baixar a cota superior
• Tentativa: ∃c, n0{T (n) ≤ c logn, ∀n ≥ n0}
• Hipo´tese: T (n− 1) ≤ c log(n− 1)
• Tese: T (n) ≤ c logn
T (n) = T (n− 1) + 1
Ana´lise de
Algoritmos
113859
Aula 5
Roteiro
Induc¸a˜o Finita
Reforc¸ando a
hipo´tese de
induc¸a˜o
Sobre qual
varia´vel?
Avaliac¸a˜o de
Polinoˆmios
Exerc´ıcio
Tentativa de baixar a cota superior
• Tentativa: ∃c, n0{T (n) ≤ c logn, ∀n ≥ n0}
• Hipo´tese: T (n− 1) ≤ c log(n− 1)
• Tese: T (n) ≤ c logn
T (n) = T (n− 1) + 1
≤ c log(n− 1) + 1 subst. a hipo´tese
Ana´lise de
Algoritmos
113859
Aula 5
Roteiro
Induc¸a˜o Finita
Reforc¸ando a
hipo´tese de
induc¸a˜o
Sobre qual
varia´vel?
Avaliac¸a˜o de
Polinoˆmios
Exerc´ıcio
Tentativa de baixar a cota superior
• Tentativa: ∃c, n0{T (n) ≤ c logn, ∀n ≥ n0}
• Hipo´tese: T (n− 1) ≤ c log(n− 1)
• Tese: T (n) ≤ c logn
T (n) = T (n− 1) + 1
≤ c log(n− 1) + 1 subst. a hipo´tese
= c log(n− 1) + log 2
Ana´lise de
Algoritmos
113859
Aula 5
Roteiro
Induc¸a˜o Finita
Reforc¸ando a
hipo´tese de
induc¸a˜o
Sobre qual
varia´vel?
Avaliac¸a˜o de
Polinoˆmios
Exerc´ıcio
Tentativa de baixar a cota superior
• Tentativa: ∃c, n0{T (n) ≤ c logn, ∀n ≥ n0}
• Hipo´tese: T (n− 1) ≤ c log(n− 1)
• Tese: T (n) ≤ c logn
T (n) = T (n− 1) + 1
≤ c log(n− 1) + 1 subst. a hipo´tese
= c log(n− 1) + log 2
= log(2n− 2) se c = 1
...
Na˜o vai dar...
Ana´lise de
Algoritmos
113859
Aula 5
Roteiro
Induc¸a˜o Finita
Reforc¸ando a
hipo´tese de
induc¸a˜o
Sobre qual
varia´vel?
Avaliac¸a˜o de
Polinoˆmios
Exerc´ıcio
Subindo a cota inferior
• Tentativa: ∃c, n0{T (n) ≥ cn, ∀n ≥ n0}
Ana´lise de
Algoritmos
113859
Aula 5
Roteiro
Induc¸a˜o Finita
Reforc¸ando a
hipo´tese de
induc¸a˜o
Sobre qual
varia´vel?
Avaliac¸a˜o de
Polinoˆmios
Exerc´ıcio
Subindo a cota inferior
• Tentativa: ∃c, n0{T (n) ≥ cn, ∀n ≥ n0}
• Hipo´tese: T (n− 1) ≥ c(n− 1)
• Tese: T (n) ≥ cn
Ana´lise de
Algoritmos
113859
Aula 5
Roteiro
Induc¸a˜o Finita
Reforc¸ando a
hipo´tese de
induc¸a˜o
Sobre qual
varia´vel?
Avaliac¸a˜o de
Polinoˆmios
Exerc´ıcio
Subindo a cota inferior
• Tentativa: ∃c, n0{T (n) ≥ cn, ∀n ≥ n0}
• Hipo´tese: T (n− 1) ≥ c(n− 1)
• Tese: T (n) ≥ cn
T (n) = T (n− 1) + 1
Ana´lise de
Algoritmos
113859
Aula 5
Roteiro
Induc¸a˜o Finita
Reforc¸ando a
hipo´tese de
induc¸a˜o
Sobre qual
varia´vel?
Avaliac¸a˜ode
Polinoˆmios
Exerc´ıcio
Subindo a cota inferior
• Tentativa: ∃c, n0{T (n) ≥ cn, ∀n ≥ n0}
• Hipo´tese: T (n− 1) ≥ c(n− 1)
• Tese: T (n) ≥ cn
T (n) = T (n− 1) + 1
≥ c(n− 1) + 1 subst. a hipo´tese
Ana´lise de
Algoritmos
113859
Aula 5
Roteiro
Induc¸a˜o Finita
Reforc¸ando a
hipo´tese de
induc¸a˜o
Sobre qual
varia´vel?
Avaliac¸a˜o de
Polinoˆmios
Exerc´ıcio
Subindo a cota inferior
• Tentativa: ∃c, n0{T (n) ≥ cn, ∀n ≥ n0}
• Hipo´tese: T (n− 1) ≥ c(n− 1)
• Tese: T (n) ≥ cn
T (n) = T (n− 1) + 1
≥ c(n− 1) + 1 subst. a hipo´tese
= cn− c+ 1
Ana´lise de
Algoritmos
113859
Aula 5
Roteiro
Induc¸a˜o Finita
Reforc¸ando a
hipo´tese de
induc¸a˜o
Sobre qual
varia´vel?
Avaliac¸a˜o de
Polinoˆmios
Exerc´ıcio
Subindo a cota inferior
• Tentativa: ∃c, n0{T (n) ≥ cn, ∀n ≥ n0}
• Hipo´tese: T (n− 1) ≥ c(n− 1)
• Tese: T (n) ≥ cn
T (n) = T (n− 1) + 1
≥ c(n− 1) + 1 subst. a hipo´tese
= cn− c+ 1
≥ cn desde que c < 1
T (n) = Ω(n)
Portanto, T (n) = Θ(n)
Ana´lise de
Algoritmos
113859
Aula 5
Roteiro
Induc¸a˜o Finita
Reforc¸ando a
hipo´tese de
induc¸a˜o
Sobre qual
varia´vel?
Avaliac¸a˜o de
Polinoˆmios
Exerc´ıcio
Reforc¸ando a hipo´tese de induc¸a˜o
• T (n) = 2T (n2 ) + 1, T (1) = 1
• Propriedade a ser provada: ∃c, n0{T (n) ≤ cn, ∀n ≥ n0}
• Hipo´tese: T (n2 ) ≤ c(
n
2 )
• Tese: T (n) ≤ cn
Ana´lise de
Algoritmos
113859
Aula 5
Roteiro
Induc¸a˜o Finita
Reforc¸ando a
hipo´tese de
induc¸a˜o
Sobre qual
varia´vel?
Avaliac¸a˜o de
Polinoˆmios
Exerc´ıcio
Reforc¸ando a hipo´tese de induc¸a˜o
• T (n) = 2T (n2 ) + 1, T (1) = 1
• Propriedade a ser provada: ∃c, n0{T (n) ≤ cn, ∀n ≥ n0}
• Hipo´tese: T (n2 ) ≤ c(
n
2 )
• Tese: T (n) ≤ cn
T (n) = 2T (
n
2
) + 1
Ana´lise de
Algoritmos
113859
Aula 5
Roteiro
Induc¸a˜o Finita
Reforc¸ando a
hipo´tese de
induc¸a˜o
Sobre qual
varia´vel?
Avaliac¸a˜o de
Polinoˆmios
Exerc´ıcio
Reforc¸ando a hipo´tese de induc¸a˜o
• T (n) = 2T (n2 ) + 1, T (1) = 1
• Propriedade a ser provada: ∃c, n0{T (n) ≤ cn, ∀n ≥ n0}
• Hipo´tese: T (n2 ) ≤ c(
n
2 )
• Tese: T (n) ≤ cn
T (n) = 2T (
n
2
) + 1
≤ 2c(
n
2
) + 1 subst. a hipo´tese
Ana´lise de
Algoritmos
113859
Aula 5
Roteiro
Induc¸a˜o Finita
Reforc¸ando a
hipo´tese de
induc¸a˜o
Sobre qual
varia´vel?
Avaliac¸a˜o de
Polinoˆmios
Exerc´ıcio
Reforc¸ando a hipo´tese de induc¸a˜o
• T (n) = 2T (n2 ) + 1, T (1) = 1
• Propriedade a ser provada: ∃c, n0{T (n) ≤ cn, ∀n ≥ n0}
• Hipo´tese: T (n2 ) ≤ c(
n
2 )
• Tese: T (n) ≤ cn
T (n) = 2T (
n
2
) + 1
≤ 2c(
n
2
) + 1 subst. a hipo´tese
= cn+ 1
na˜o e´ ≤ cn para nenhum c
Ana´lise de
Algoritmos
113859
Aula 5
Roteiro
Induc¸a˜o Finita
Reforc¸ando a
hipo´tese de
induc¸a˜o
Sobre qual
varia´vel?
Avaliac¸a˜o de
Polinoˆmios
Exerc´ıcio
Reforc¸ando a hipo´tese de induc¸a˜o
• Hipo´tese: T (n2 ) ≤ c(
n
2 )− b
• Tese: T (n) ≤ cn− b
Ana´lise de
Algoritmos
113859
Aula 5
Roteiro
Induc¸a˜o Finita
Reforc¸ando a
hipo´tese de
induc¸a˜o
Sobre qual
varia´vel?
Avaliac¸a˜o de
Polinoˆmios
Exerc´ıcio
Reforc¸ando a hipo´tese de induc¸a˜o
• Hipo´tese: T (n2 ) ≤ c(
n
2 )− b
• Tese: T (n) ≤ cn− b
T (n) = 2T (
n
2
) + 1
Ana´lise de
Algoritmos
113859
Aula 5
Roteiro
Induc¸a˜o Finita
Reforc¸ando a
hipo´tese de
induc¸a˜o
Sobre qual
varia´vel?
Avaliac¸a˜o de
Polinoˆmios
Exerc´ıcio
Reforc¸ando a hipo´tese de induc¸a˜o
• Hipo´tese: T (n2 ) ≤ c(
n
2 )− b
• Tese: T (n) ≤ cn− b
T (n) = 2T (
n
2
) + 1
≤ 2c(
n
2
− b) + 1 subst. a hipo´tese
Ana´lise de
Algoritmos
113859
Aula 5
Roteiro
Induc¸a˜o Finita
Reforc¸ando a
hipo´tese de
induc¸a˜o
Sobre qual
varia´vel?
Avaliac¸a˜o de
Polinoˆmios
Exerc´ıcio
Reforc¸ando a hipo´tese de induc¸a˜o
• Hipo´tese: T (n2 ) ≤ c(
n
2 )− b
• Tese: T (n) ≤ cn− b
T (n) = 2T (
n
2
) + 1
≤ 2c(
n
2
− b) + 1 subst. a hipo´tese
= cn− 2b+ 1
Ana´lise de
Algoritmos
113859
Aula 5
Roteiro
Induc¸a˜o Finita
Reforc¸ando a
hipo´tese de
induc¸a˜o
Sobre qual
varia´vel?
Avaliac¸a˜o de
Polinoˆmios
Exerc´ıcio
Reforc¸ando a hipo´tese de induc¸a˜o
• Hipo´tese: T (n2 ) ≤ c(
n
2 )− b
• Tese: T (n) ≤ cn− b
T (n) = 2T (
n
2
) + 1
≤ 2c(
n
2
− b) + 1 subst. a hipo´tese
= cn− 2b+ 1
= cn− b− b + 1
Ana´lise de
Algoritmos
113859
Aula 5
Roteiro
Induc¸a˜o Finita
Reforc¸ando a
hipo´tese de
induc¸a˜o
Sobre qual
varia´vel?
Avaliac¸a˜o de
Polinoˆmios
Exerc´ıcio
Reforc¸ando a hipo´tese de induc¸a˜o
• Hipo´tese: T (n2 ) ≤ c(
n
2 )− b
• Tese: T (n) ≤ cn− b
T (n) = 2T (
n
2
) + 1
≤ 2c(
n
2
− b) + 1 subst. a hipo´tese
= cn− 2b+ 1
= cn− b− b + 1
≤ cn− b para b = 1
De fato, T (n) = O(n)
Ana´lise de
Algoritmos
113859
Aula 5
Roteiro
Induc¸a˜o Finita
Reforc¸ando a
hipo´tese de
induc¸a˜o
Sobre qual
varia´vel?
Avaliac¸a˜o de
Polinoˆmios
Exerc´ıcio
Induc¸a˜o sobre qual varia´vel?
• Qual e´ a altura h m´ınima de uma a´rvore bina´ria com n
folhas?
h
n folhas
h− 1
A intuic¸a˜o diz que h ≥ log n
Ana´lise de
Algoritmos
113859
Aula 5
Roteiro
Induc¸a˜o Finita
Reforc¸ando a
hipo´tese de
induc¸a˜o
Sobre qual
varia´vel?
Avaliac¸a˜o de
Polinoˆmios
Exerc´ıcio
Induc¸a˜o sobre qual varia´vel?
Induc¸a˜o sobre n e´ mais complicado...
Ao contra´rio, fazemos induc¸a˜o sobre h
Ana´lise de
Algoritmos
113859
Aula 5
Roteiro
Induc¸a˜o Finita
Reforc¸ando a
hipo´tese de
induc¸a˜o
Sobre qual
varia´vel?
Avaliac¸a˜o de
Polinoˆmios
Exerc´ıcio
Induc¸a˜o sobre qual varia´vel?
Induc¸a˜o sobre n e´ mais complicado...
Ao contra´rio, fazemos induc¸a˜o sobre h
• Propriedade a ser provada: n = m(h) ≤ 2h, ∀h ≥ 1
• Hipo´tese: m(i) ≤ 2i, ∀i ≤ h− 1
• Tese: m(h) ≤ 2h
Ana´lise de
Algoritmos
113859
Aula 5
Roteiro
Induc¸a˜o Finita
Reforc¸ando a
hipo´tese de
induc¸a˜o
Sobre qual
varia´vel?
Avaliac¸a˜o de
Polinoˆmios
Exerc´ıcio
Induc¸a˜o sobre qual varia´vel?
Induc¸a˜o sobre n e´ mais complicado...
Ao contra´rio, fazemos induc¸a˜o sobre h
• Propriedade a ser provada: n = m(h) ≤ 2h, ∀h ≥ 1
• Hipo´tese: m(i) ≤ 2i, ∀i ≤ h− 1
• Tese: m(h) ≤ 2h
m(h) ≤ 2m(h− 1) por queˆ?
Ana´lise de
Algoritmos
113859
Aula 5
Roteiro
Induc¸a˜o Finita
Reforc¸ando a
hipo´tese de
induc¸a˜o
Sobre qual
varia´vel?
Avaliac¸a˜o de
Polinoˆmios
Exerc´ıcio
Induc¸a˜o sobre qual varia´vel?
Induc¸a˜o sobre n e´ mais complicado...
Ao contra´rio, fazemos induc¸a˜o sobre h
• Propriedade a ser provada: n = m(h) ≤ 2h, ∀h ≥ 1
• Hipo´tese: m(i) ≤ 2i, ∀i ≤ h− 1
• Tese: m(h) ≤ 2h
m(h) ≤ 2m(h− 1) por queˆ?
≤ 22h−1 subst. a hipo´tese
Ana´lise de
Algoritmos
113859
Aula 5
Roteiro
Induc¸a˜o Finita
Reforc¸ando a
hipo´tese de
induc¸a˜o
Sobre qual
varia´vel?
Avaliac¸a˜o de
Polinoˆmios
Exerc´ıcio
Induc¸a˜o sobre qual varia´vel?
Induc¸a˜o sobre n e´ mais complicado...
Ao contra´rio, fazemos induc¸a˜o sobre h
• Propriedade a ser provada: n = m(h) ≤ 2h, ∀h ≥ 1
• Hipo´tese: m(i) ≤ 2i, ∀i ≤ h− 1
• Tese: m(h) ≤ 2h
m(h) ≤ 2m(h− 1) por queˆ?
≤ 22h−1 subst. a hipo´tese
= 2h
Enta˜o, ∀h{n = m(h) ≤ 2h}; assim, h ≥ log n
Ana´lise de
Algoritmos
113859
Aula 5
Roteiro
Induc¸a˜o Finita
Avaliac¸a˜o de
Polinoˆmios
Primeira
tentativa
Segunda
tentativa
Terceira
tentativa
Exerc´ıcio
Projetando algoritmos com induc¸a˜oAvaliac¸a˜o de Polinoˆmios
• Entrada: Dados uma sequ¨eˆncia de nu´meros reais
an, an−1, . . . , a1, a0, e um nu´mero real x;
• Sa´ıda: O valor do polinoˆmio
Pn(x) = anx
n + an−1x
n−1 + · · ·+ a1x+ a0.
Custo dos algoritmos:
nu´mero de multiplicac¸o˜es e adic¸o˜es realizadas
Ana´lise de
Algoritmos
113859
Aula 5
Roteiro
Induc¸a˜o Finita
Avaliac¸a˜o de
Polinoˆmios
Primeira
tentativa
Segunda
tentativa
Terceira
tentativa
Exerc´ıcio
Primeira tentativa
Pn(x) = anx
n + an−1x
n−1 + · · ·+ a1x+ a0
Ana´lise de
Algoritmos
113859
Aula 5
Roteiro
Induc¸a˜o Finita
Avaliac¸a˜o de
Polinoˆmios
Primeira
tentativa
Segunda
tentativa
Terceira
tentativa
Exerc´ıcio
Primeira tentativa
Pn(x) = anx
n + an−1x
n−1 + · · ·+ a1x+ a0
Como resolver uma entrada de tamanho n
a partir da soluc¸a˜o de uma de tamanho n− 1?
Ana´lise de
Algoritmos
113859
Aula 5
Roteiro
Induc¸a˜o Finita
Avaliac¸a˜o de
Polinoˆmios
Primeira
tentativa
Segunda
tentativa
Terceira
tentativa
Exerc´ıcio
Primeira tentativa
Pn(x) = anx
n + an−1x
n−1 + · · ·+ a1x+ a0
Como resolver uma entrada de tamanho n
a partir da soluc¸a˜o de uma de tamanho n− 1?
Pn(x) = anx
n
︸ ︷︷ ︸
retirar este termo
+ an−1x
n−1 + · · ·+ a1x+ a0
︸ ︷︷ ︸
sobra um outro polinoˆmio
Ana´lise de
Algoritmos
113859
Aula 5
Roteiro
Induc¸a˜o Finita
Avaliac¸a˜o de
Polinoˆmios
Primeira
tentativa
Segunda
tentativa
Terceira
tentativa
Exerc´ıcio
Primeira tentativa
Pn(x) = anx
n + an−1x
n−1 + · · ·+ a1x+ a0
Como resolver uma entrada de tamanho n
a partir da soluc¸a˜o de uma de tamanho n− 1?
Pn(x) = anx
n
︸ ︷︷ ︸
retirar este termo
+ an−1x
n−1 + · · ·+ a1x+ a0
︸ ︷︷ ︸
sobra um outro polinoˆmio
• Hipo´tese de induc¸a˜o: Sabemos avaliar um polinoˆmio de
grau n− 1 no ponto x
Ana´lise de
Algoritmos
113859
Aula 5
Roteiro
Induc¸a˜o Finita
Avaliac¸a˜o de
Polinoˆmios
Primeira
tentativa
Segunda
tentativa
Terceira
tentativa
Exerc´ıcio
Primeira tentativa
Pn(x) = anx
n
︸ ︷︷ ︸
retirar este termo
+ an−1x
n−1 + · · ·+ a1x+ a0
︸ ︷︷ ︸
Pn−1(x)
Passo da induc¸a˜o: Como calcular Pn(x) a partir de Pn−1(x)?
Ana´lise de
Algoritmos
113859
Aula 5
Roteiro
Induc¸a˜o Finita
Avaliac¸a˜o de
Polinoˆmios
Primeira
tentativa
Segunda
tentativa
Terceira
tentativa
Exerc´ıcio
Primeira tentativa
Pn(x) = anx
n
︸ ︷︷ ︸
retirar este termo
+ an−1x
n−1 + · · ·+ a1x+ a0
︸ ︷︷ ︸
Pn−1(x)
Passo da induc¸a˜o: Como calcular Pn(x) a partir de Pn−1(x)?
• E´ fa´cil: Pn(x) = anx
n + Pn−1(x)
Ana´lise de
Algoritmos
113859
Aula 5
Roteiro
Induc¸a˜o Finita
Avaliac¸a˜o de
Polinoˆmios
Primeira
tentativa
Segunda
tentativa
Terceira
tentativa
Exerc´ıcio
Primeira tentativa
Pn(x) = anx
n
︸ ︷︷ ︸
retirar este termo
+ an−1x
n−1 + · · ·+ a1x+ a0
︸ ︷︷ ︸
Pn−1(x)
Passo da induc¸a˜o: Como calcular Pn(x) a partir de Pn−1(x)?
• E´ fa´cil: Pn(x) = anx
n + Pn−1(x)
• Custo: T (n) = T (n− 1) + n
︸︷︷︸
multiplicac¸o˜es
+ 1
︸︷︷︸
adic¸o˜es
Ana´lise de
Algoritmos
113859
Aula 5
Roteiro
Induc¸a˜o Finita
Avaliac¸a˜o de
Polinoˆmios
Primeira
tentativa
Segunda
tentativa
Terceira
tentativa
Exerc´ıcio
Primeira tentativa
Pn(x) = anx
n
︸ ︷︷ ︸
retirar este termo
+ an−1x
n−1 + · · ·+ a1x+ a0
︸ ︷︷ ︸
Pn−1(x)
Passo da induc¸a˜o: Como calcular Pn(x) a partir de Pn−1(x)?
• E´ fa´cil: Pn(x) = anx
n + Pn−1(x)
• Custo: T (n) = T (n− 1) + n
︸︷︷︸
multiplicac¸o˜es
+ 1
︸︷︷︸
adic¸o˜es
• Assim, T (n) = Θ(n2)
Ana´lise de
Algoritmos
113859
Aula 5
Roteiro
Induc¸a˜o Finita
Avaliac¸a˜o de
Polinoˆmios
Primeira
tentativa
Segunda
tentativa
Terceira
tentativa
Exerc´ıcio
Segunda tentativa (reforc¸ando a hipo´tese)
Pn(x) = anx
n + an−1x
n−1 + · · ·+ a1x+ a0
Ana´lise de
Algoritmos
113859
Aula 5
Roteiro
Induc¸a˜o Finita
Avaliac¸a˜o de
Polinoˆmios
Primeira
tentativa
Segunda
tentativa
Terceira
tentativa
Exerc´ıcio
Segunda tentativa (reforc¸ando a hipo´tese)
Pn(x) = anx
n + an−1x
n−1 + · · ·+ a1x+ a0
• Hipo´tese de induc¸a˜o: Sabemos avaliar um polinoˆmio de
grau n− 1 no ponto x e calcular xn−1
Ana´lise de
Algoritmos
113859
Aula 5
Roteiro
Induc¸a˜o Finita
Avaliac¸a˜o de
Polinoˆmios
Primeira
tentativa
Segunda
tentativa
Terceira
tentativa
Exerc´ıcio
Segunda tentativa (reforc¸ando a hipo´tese)
Pn(x) = anx
n + an−1x
n−1 + · · ·+ a1x+ a0
• Hipo´tese de induc¸a˜o: Sabemos avaliar um polinoˆmio de
grau n− 1 no ponto x e calcular xn−1
Passo da induc¸a˜o: Como calcular Pn(x) a partir de Pn−1(x) e x
n−1?
Ana´lise de
Algoritmos
113859
Aula 5
Roteiro
Induc¸a˜o Finita
Avaliac¸a˜o de
Polinoˆmios
Primeira
tentativa
Segunda
tentativa
Terceira
tentativa
Exerc´ıcio
Segunda tentativa (reforc¸ando a hipo´tese)
Pn(x) = anx
n + an−1x
n−1 + · · ·+ a1x+ a0
• Hipo´tese de induc¸a˜o: Sabemos avaliar um polinoˆmio de
grau n− 1 no ponto x e calcular xn−1
Passo da induc¸a˜o: Como calcular Pn(x) a partir de Pn−1(x) e x
n−1?
• E´ fa´cil tambe´m: Pn(x) = anxx
n−1 + Pn−1(x)
Ana´lise de
Algoritmos
113859
Aula 5
Roteiro
Induc¸a˜o Finita
Avaliac¸a˜o de
Polinoˆmios
Primeira
tentativa
Segunda
tentativa
Terceira
tentativa
Exerc´ıcio
Segunda tentativa (reforc¸ando a hipo´tese)
Pn(x) = anx
n + an−1x
n−1 + · · ·+ a1x+ a0
• Hipo´tese de induc¸a˜o: Sabemos avaliar um polinoˆmio de
grau n− 1 no ponto x e calcular xn−1
Passo da induc¸a˜o: Como calcular Pn(x) a partir de Pn−1(x) e x
n−1?
• E´ fa´cil tambe´m: Pn(x) = anxx
n−1 + Pn−1(x)
• Custo: T (n) = T (n− 1) + 2
︸︷︷︸
multiplicac¸o˜es
+ 1
︸︷︷︸
uma adic¸a˜o
Ana´lise de
Algoritmos
113859
Aula 5
Roteiro
Induc¸a˜o Finita
Avaliac¸a˜o de
Polinoˆmios
Primeira
tentativa
Segunda
tentativa
Terceira
tentativa
Exerc´ıcio
Segunda tentativa (reforc¸ando a hipo´tese)
Pn(x) = anx
n + an−1x
n−1 + · · ·+ a1x+ a0
• Hipo´tese de induc¸a˜o: Sabemos avaliar um polinoˆmio de
grau n− 1 no ponto x e calcular xn−1
Passo da induc¸a˜o: Como calcular Pn(x) a partir de Pn−1(x) e x
n−1?
• E´ fa´cil tambe´m: Pn(x) = anxx
n−1 + Pn−1(x)
• Custo: T (n) = T (n− 1) + 2
︸︷︷︸
multiplicac¸o˜es
+ 1
︸︷︷︸
uma adic¸a˜o
• No total: 2n multiplicac¸o˜es e n adic¸o˜es
• Assim, T (n) = Θ(n)
Ana´lise de
Algoritmos
113859
Aula 5
Roteiro
Induc¸a˜o Finita
Avaliac¸a˜o de
Polinoˆmios
Primeira
tentativa
Segunda
tentativa
Terceira
tentativa
Exerc´ıcio
Terceira tentativa
Ao inve´s de retirar o primeiro termo,
retiramos o u´ltimo!
Pn(x) = anx
n + an−1x
n−1 + · · ·+ a1x+ a0
Ana´lise de
Algoritmos
113859
Aula 5
Roteiro
Induc¸a˜o Finita
Avaliac¸a˜o de
Polinoˆmios
Primeira
tentativa
Segunda
tentativa
Terceira
tentativa
Exerc´ıcio
Terceira tentativa
Ao inve´s de retirar o primeiro termo,
retiramos o u´ltimo!
Pn(x) = anx
n + an−1x
n−1 + · · ·+ a1x+ a0
Pn(x) = (anx
n−1 + an−1x
n−2 + · · ·+ a1)
︸ ︷︷ ︸
P ′
n−1
(x)
x+ a0
︸︷︷︸
retirar esse termo
Ana´lise de
Algoritmos
113859
Aula 5
Roteiro
Induc¸a˜o Finita
Avaliac¸a˜o de
Polinoˆmios
Primeira
tentativa
Segunda
tentativa
Terceira
tentativa
Exerc´ıcio
Terceira tentativa
Ao inve´s de retirar o primeiro termo,
retiramos o u´ltimo!
Pn(x) = anx
n + an−1x
n−1 + · · ·+ a1x+ a0
Pn(x) = (anx
n−1 + an−1x
n−2 + · · ·+ a1)
︸ ︷︷ ︸
P ′
n−1
(x)
x+ a0
︸︷︷︸
retirar esse termo• Hipo´tese de induc¸a˜o: Sabemos avaliar um polinoˆmio de
grau n− 1, representado pelos coeficientes
an, an−1, . . . , a1, no ponto x
Ana´lise de
Algoritmos
113859
Aula 5
Roteiro
Induc¸a˜o Finita
Avaliac¸a˜o de
Polinoˆmios
Primeira
tentativa
Segunda
tentativa
Terceira
tentativa
Exerc´ıcio
Terceira tentativa
Passo da induc¸a˜o: Pn(x) = xP
′
n−1(x) + a0
Ana´lise de
Algoritmos
113859
Aula 5
Roteiro
Induc¸a˜o Finita
Avaliac¸a˜o de
Polinoˆmios
Primeira
tentativa
Segunda
tentativa
Terceira
tentativa
Exerc´ıcio
Terceira tentativa
Passo da induc¸a˜o: Pn(x) = xP
′
n−1(x) + a0
• Custo: T (n) = T (n− 1) + 1
︸︷︷︸
multiplicac¸a˜o
+ 1
︸︷︷︸
uma adic¸a˜o
Ana´lise de
Algoritmos
113859
Aula 5
Roteiro
Induc¸a˜o Finita
Avaliac¸a˜o de
Polinoˆmios
Primeira
tentativa
Segunda
tentativa
Terceira
tentativa
Exerc´ıcio
Terceira tentativa
Passo da induc¸a˜o: Pn(x) = xP
′
n−1(x) + a0
• Custo: T (n) = T (n− 1) + 1
︸︷︷︸
multiplicac¸a˜o
+ 1
︸︷︷︸
uma adic¸a˜o
• No total: n multiplicac¸o˜es e n adic¸o˜es
• Assim, T (n) continua sendo Θ(n), mas na pra´tica...
Ana´lise de
Algoritmos
113859
Aula 5
Roteiro
Induc¸a˜o Finita
Avaliac¸a˜o de
Polinoˆmios
Primeira
tentativa
Segunda
tentativa
Terceira
tentativa
Exerc´ıcio
Terceira tentativa
Mas claro, na˜o ha´ necessidade de a implementac¸a˜o ser recursiva!
double a[N+1];
...
double thirdAttempt( int n, double *a, double x ){
double res;
res = a[n];
for ( int i = 1; i < n+1; i++ )
res = x*res + a[n-i];
return res;
}
Este algoritmo e´ conhecido como Regra de Horner
Ana´lise de
Algoritmos
113859
Aula 5
Roteiro
Induc¸a˜o Finita
Avaliac¸a˜o de
Polinoˆmios
Exerc´ıcio
Exerc´ıcio
• Projete um algoritmo indutivo de divisa˜o-e-conquista para
o problema de avaliac¸a˜o de polinoˆmios. Qual e´ o custo do
seu algoritmo? Ele e´ melhor (assintoticamente e/ou na
pra´tica) do que nossa terceira tentativa?
• Desafio: Prove por induc¸a˜o que, num conjunto qualquer
de n + 1 nu´meros dentre os primeiros 2n naturais
(1, 2, . . . , 2n) sempre existem dois nu´meros tal que um
divide o outro.
	Roteiro
	Indução Finita
	Reforçando a hipótese de indução
	Sobre qual variável?
	Avaliação de Polinômios
	Primeira tentativa
	Segunda tentativa
	Terceira tentativa
	Exercício