Lista 3 - Matemática Discreta UFMG

Prévia do material em texto

Lista 3 -- identificar e resolver
recorrências
 
Matemática Discreta -- Prof. Jeroen van de Graaf
Leitura recomendada 
Slides elaborados pelo professor;
Rosen 7.1+7.2+7.3
Observações e lembretes 
Questões discursivas 
1. O que é uma relação de recorrência (RdR)?
2. Qual é a sequência de Fibonacci?
3. O que é a Torre de Hanoi?
4. O que é uma RdR linear, homogêneo um coeficientes constantes?
5. Como se verifica se uma fórmula fechada é solução para uma determinadaa RdR?
6. O que é a equação característica de uma RdR? As raízes características? Qual é a
importâncias dessas raízes?
7. Qual é o método de encontrar uma fórmula fechada para uma RdR?
8. O que acontece se a equação característica tem raizes com multiplicidade?
9. O que é uma RdR heterogênea? O que é uma solução particular?
10. O que é um algoritmo do tipo Divisão e Conquista?
11. Qual é a característica em comum na complexidade computacional desses algoritmos?
12. O que diz o Teorema Mestre?
 
Exercícios 
F=fácil, M=médio, D=difícil
 
Os números se referem ao livro de Rosen.
1. [F] Exercício 7.1.12
2. [M] Exercício 7.1.19
3. [M] Exercício 7.1.23
4. [M]Exercício 7.1.29
5. [M] Exercício 7.2.4 e+f
6. [M] Exercício 7.2.7
7. [M] Exercício 7.2.14
8. [M] Exercício 7.2.24
9. [M] Exercício 7.2.26 b+d+f
10. [F] Exercício 7.3.8
11. [M] Exercício 7.3.12
12. [D] Exercício 7.3.19
af://n172
af://n175
af://n181
af://n183
af://n211
	Lista 3 -- identificar e resolver recorrências
	Leitura recomendada
	Observações e lembretes
	Questões discursivas
	Exercícios