Baixe o app para aproveitar ainda mais
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
Compartilhar