LogMD Lst06

Prévia do material em texto

FUNDAC¸A˜O CENTRO DE ANA´LISE, PESQUISA E
INOVAC¸A˜O TECNOLO´GICA
FUCAPI
ENGENHARIA E CIEˆNCIA DA COMPUTAC¸A˜O
ENG04NA - Lo´gica e Matema´tica Discreta, 2017/02
Prof. Rainer Xavier de Amorim.
Lista de Exerc´ıcios VI
1. Plote o gra´fico das seguintes func¸o˜es:
a) n
b) n2
c) n3
d) 2n
e) logn
f) k, contante
g) nn
h) nlogn
2. Escreva em notac¸a˜o O, o, Ω ,ω e Θ:
a) n3 − n + 20
b) n2 + 2logn
c) 22n
d) 2nn + 4(3n)
e) nn − 2n + nn−2
f) nk+1
3. Verifique:
a) 2n2 + 1 e´ O(2n)
b) nlogn e´ O(n2)
c) 2n2 + 1 e´ O(n2)
d) 403 e´ O(1)
e) nr e´ O(ns)
f) nk+1 e´ O(nk)
4. Para os itens a seguir, escreva os cinco valores da sequeˆncia:
a) S(1) = 10
S(n) = S(n− 1) + 10 para n ≥ 2
b) S(1) = 1
S(n) = S(n− 1) + 1n para n ≥ 2
c) M(1) = 2
M(2) = 2
M(n) = 2M(n− 1) + M(n− 2) para n > 2
d) W (1) = 2
W (2) = 3
W (n) = W (n− 1)W (n− 2) para n > 2
1
e) T (1) = 1
T (2) = 2
T (3) = 3
T (n) = T (n− 1) + 2T (n− 2) + 3T (n− 3) para n > 3
5. Resolva as relac¸o˜es de recorreˆncia abaixo e prove a sua correc¸a˜o usando induc¸a˜o matema´tica:
a) T (n) =
{
1, para n = 1
2T (n− 1) + 1, para n > 1
b) T (n) =
{
1, para n = 1
T (n− 2) + 1, para n > 1
c) T (n) =
{
1, para n = 1
T (n− 1) + 2n− 1, para n > 1
6. Os primeiros membros da Associac¸a˜o de Pita´goras definiram nu´meros poligonais como sendo o
nu´mero de pontos em determinadas configurac¸o˜es geome´tricas. Os primeiros nu´meros triangulares
sa˜o 1, 3, 6 e 10:
Encontre uma fo´rmula fechada para o n−e´simo nu´mero triangular.
7. O teorema mestre se aplica para:
a) T (n) = 9T (n/3) + n
b) T (n) = 2T (n/2) + nlogn
c) T (n) = 2T (n/3) + 1
d) T (n) = 4T (n/2) + n3
e) T (n) = 3T (n/4) + nlogn
f) T (n) = T (n/5) + 2n
2