Lista de exercícios de Algoritmo

Prévia do material em texto

1) Ordene as funções f(n), g(n) e h(n) abaixo.
 	a) f(n) = n! g(n) = n h(n) = 2n 
	b) f(n) = 5 + 2 log n + 3 log2 n 	 g(n) = 3 n + 5 log n + 2 h(n) = log 100000 
	c) f(n) = log n g(n) = n h(n) = n2 
	d) f(n) = n g(n) = en h(n) = 2n 
	e) f(n) = n log n g(n) = log n h(n) = n2
	f) f(n) = n g(n) = n1/2 h(n) = log n 
	g) f(n) = log5 n g(n) = log10 n h(n) = log20 n
	2) Verifique se as afirmativas são verdadeiras ou falsas :
 a) Se ord(f+g) = ord(g) então ord(f) ord(g).
	 b) Ord(kf) = ord(f) onde k real positivo.
	 c) Se ord(f) = ord(g) = ord(h) então podemos afirmar que 
 ord(2f + 3g) = ord(4h). 
 
	 d) 0< c < d , c,d então ord(nc) < ord(nd). 
 e) Seja f,g tal que ord(f.g) = ord(log n) e ord(f) = ord(nlogn). Então podemos afirmar que ord(f) < ord(g).
	 f) Se ord(f) = ord(g) então ord(f2) = ord(g2).
	 g) Se b,c b,c > 1 então ord(nlogbn) = ord(nlogcn).
	 h) 0< c < d , c,d então ord(cn) = ord(dn).
	3) Seja T : Z +R+ tq T(1)=a e T(n)=2 T(n/2) + bn para n = 2K n >1.
		Determine ord(T). 
	
	4) Suponha que T(n) satisfaz a condição inicial T(1)=1, e a sequência de recorrência T(n)=2 T(n-1) +1. Qual a complexidade do algoritmo de hanoi, de acordo com a equação de recorrência dada.
	5) Suponha que T(n) satisfaz a condição inicial T(1)=1 , e a seguinte equação de recorrência T(n) = 2 T(n/2) + n logn. Então pode-se dizer que a ordem é (n logn logn).
	6) As funções n log n e n log n2 , tem a mesma ordem ? 
		 
	7) Faça o algoritmo recursivo e não recursivo e a equação de recorrência para encontrar a sequência de fibonnacci.
	8) Qual a ordem dos algoritmos de pesquisa linear e de pesquisa binária.
	9) Determinada empresa processa, num determinado período do ano, uma grande quantidade de registros. No ano retrasado foram N registros processados ininterruptamente durante 15 dias. No ano passado receberam 2N registros e gastaram 30 dias ininterruptos de processamento. Este ano deverão receber 4N registros e, em função do aumento de registros resolveram trocar o equipamento usado por outro 4 vezes mais rápido. Quantos dias deverão ser gastos no processamento se alterarem também o sistema por um outro que seja da ordem de n2 . 
	10) Considerando que o "Buble Sort" tem a ordem de n2 e o "Merge Sort" tem a ordem de n log n, qual dos algoritmos você escolheria caso necessitasse processar uma quantidade grande de registros ? Justifique , matematicamente, sua resposta.
	 
 	11) A função n3 + n2 log n pode ter ordem igual a n3 ou n4.
	12) Determinado algoritmo tem sua medida (em unidade de tempo de processamento) dada por f(n)= n2 + log n + 1/n2 ( onde n é o número de registros processáveis). Explique matematicamente o que acontecerá com o tempo de processamento se triplicarmos a quantidade de registros.
	13) Encontre a menor função que possui a mesma ordem da função f(n)= 3n2 + 6 n + 9.