Lista de exercicios 2 - 1o estagio

Prévia do material em texto

Universidade Federal de Campina Grande 
Centro de Engenharia Eletrica e Informática 
Departamento de Sistemas e Computação 
Graduação em Ciência da Computação 
Aula de exercícios sobre análise de algoritmos e algoritmos de ordenação 
1. Mostre que, para quaisquer constantes reais a e b, onde b > 0, . Dica: tente usar 
inducao. Caso seja necessário use a seguinte propriedade 
 . 
 
2. Prove que ∑ ∑ 
 . Dica: comece simplificando o somatório interno e caso seja 
necessário use a propriedade dada abaixo. 
 
 
 
3. O limite é uma boa solução para a relação (
 
 
) (
 
 
) ? Argumente 
usando o método iterativo. 
 
4. Utilize os métodos iterativo e mestre para resolver as seguintes equações abaixo: 
 (
 
 
) 
 (
 
 
) 
 (
 
 
) 
 
5. Use o método mestre para mostrar que a solucao da relacao de recorrencia (
 
 
) 
da busca binária é . 
 
 
6. Proponha um algoritmo que calcule o MDC de dois numeros dados e encontre o tempo de 
execução desse algoritmo. Dica: procure entender a idéia do algoritmo de Euclides. Isso vai levar 
voce a um algoritmo mais eficiente. 
 




n
i
nnn
ni
1
2222
6
)12)(1(
21 