1 Lista de exercícios – PAA

Prévia do material em texto

1° Lista de exercícios – PAA 
Professor Elton Lever 23-04-2018 
 
1- Avalie os seguintes somatórios: 
 
a) 
b) 
c) 
d) 
e) 
f) 
g) 
h) 
2- Escrever em notação O, o, Ω, ω, Θ. 
a) 1 
b) n - 1 
c) n2 – n + 30 
d) n(n-3) 
e) n3 + 2 logn + 20 
f) nk+1 
g) 22n 
h) 2nn + 4n O (3n) 
 
3- Utilizando as definições para as notações assintóticas, prove se são 
verdadeiras ou falsas as seguintes afirmativas: 
 
a) 3n3 + 2n2 + n + 1 = O(n3) 
b) 7n2 = O(n) 
c) 2n+2 = O(2n) 
d) 22n = O(2n) 
e) 5n2 + 7n = Θ (n2) 
f) 6n3 + 5n2 ≠ Θ (n2) 
g) 9n3 + 3n = Ω (n) 
h) Se f(n)=n-300 então f(n) é Ω(300n) e f(n)=O(300n) 
i) f(n)=O(u(n)) e g(n)=O(v(n)) implica que f(n)+g(n)=O(u(n)+v(n)) 
 
 
 


n
j
ij
m
i
a
11


n
i
i
1
2


n
i
ia
1


n
i
iia
1



n
i
iia
1


n
i
i
1
2log


n
i i1
1


n
i
ia1
1
 
 
4- Resolva as recorrências. 
 
 
 
a) ( ) {
 
 ( ) 
 
b) ( ) {
 
 ( ) 
 
c) ( ) {
 
 ( ) 
 
d) ( ) {
 
 (
 
 
) (
 
 
) 
e) ( ) {
 
 ( ) 
 
f) ( ) {
 
 (
 
 
) 
g) ( ) {
 
 (
 
 
) √ 
 
h) ( ) {
 
 (
 
 
) Para a=b, a<b e a>b. 
 
 
 
 
 
 
 
5- Faça a análise de custo, ache a fórmula fechada e mostre a 
complexidade dos seguintes: 
 
 
a) 
(1) para i de 1 até n faça 
(2) se (A[i] <= x) 
(3) A[i] = 2*A[i] 
 
b) 
#include <stdio.h> 
main() { 
 
#include <stdio.h> 
main() { 
int vetor[n], indice; 
for (indice=0; indice<n; indice++) { 
printf("\nVetor[%d]: ",indice); 
scanf("%d",&vetor[indice]); 
} 
 
for (indice=0; indice<10; indice++) { 
printf("\n %d ", vetor[indice]); 
} 
 } 
 
 
c) 
VERIFICA_ALGO (int n) { 
Int i, j, n; 
If(n>0) { 
VERIFICA_ALGO(n-1); 
 for(i=0;i<n;i++){ 
 for(j=0;j<i;j++){ 
 faça_algo; 
 } 
 } 
 } 
 }