Métodos Computacionais 2021: Aula 6 - Exercícios resolvidos e Outros

 

Abaixo temos os exemplos apresentados em sala de aula:

Medição empírica da complexidade computacional

Referências Adicionais para essa aula:

Introduction to Algorithms - Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest e Clifford Stein [Capítulo 3]

Introduction to the Design and Analysis of Algorithms - Anany Levitin [Capítulo 2]

Soluções da série de exercícios:

1. Como calcular a complexidade computacional das implementações recursivas da série de fibonacci?

2. Qual a complexidade computacional de um algoritmo recursivo que satisfaz a relação de recorrência?

3. Qual a complexidade computacional dessas relações de recorrência de acordo com o Teorema Mestre (master theorem)?

4. Capı́tulo 3 ”Runtime analysis of recursive algorithms“ do livro ”Introduction to
Recursive Programming“

3.1 

3.1 

3.2 

3.3 

3.4

3.5 

3.6 

3.7 

3.8 

3.10

3.11 

3.12 

3.13 

3.14

3.17 

3.18 (a)

3.18 - item b (1ª Edição, 2018) 

3.18 (d)

3.18 (f) 

3.18 (h) (1ª Edição, 2018)

5. Você pode resolver qualquer problema apresentado no Capítulo 8 do livro
”Combinatorial Optimization: Algorithms and Complexity“ de Christos H. Papadimitriou e Kenneth Steiglitz.

 8.1 (2ª Edição, 1998)

 8.3 (2ª Edição, 1998)