UNICAMP – Universidade Estadual de Campinas

IC – Instituto de Computação

Disciplina: MO417 – Complexidade de Algoritmos I

Professor: João Meidanis

Ata de Exercícios

Assunto: Programação Dinâmica (Parte 1)

Capítulo do Livro Texto Adotado (*): Capítulo 15 (Itens 15.1 e 15.2)

Data da Aula: 04/04/2003

Data de Entrega da Ata: 06/04/2003

Redator: Marcelo Fantinato

* Livro Texto adotado: Cormen, T.H.;Leiserson, C.E.; Rivest, R.L.; Stein, C.; Algoritmos. Tradução da 2ª edição americana Teoria e Prática. 2002.

Exercícios desta Ata:

1) 1) 15.1-1

2) 2) 15.2-1

3) 3) 15.2-3

15.1-1 (página 265)

Mostre como modificar o procedimento PRINT-STATIONS para imprimir as estações em ordem crescente de número de estação. (Sugestão: Use recursão.)

Aluno chamado para apresentar a solução para a questão: Eduardo Yonekura

Resolução:

PRINT-STATIONS(l, n)

{

PRINT-ORDER(l, n-1, l*);

imprimir “linha = “ l* “, estação = “ n;

}

PRINT-ORDER(l, n, k)

{

se n>= 1

{

PRINT-ORDER(l, n-1, l_k[n + 1]);

imprimir “linha = “ l_k[n + 1] “, estação = “ n;

}

}

15.2-1 (página 271)

Encontre uma colocação ótima dos parênteses de um produto de cadeias de matrizes cuja seqüência de dimensões é <5, 10, 3, 12, 5, 50, 6>.

Aluno chamado para apresentar a solução para a questão: Ricardo Luís Lachi

Resolução:

Exemplo de elemento da matriz m:

Resultado final: ((A₁ A₂)((A₃ A₄)(A₅ A₆)))

15.2-3 (página 271)

Use o método de substituição para mostrar que a solução para a recorrência (15.11) – página 267 do livro – é Omega(2ⁿ).

Aluno chamado para apresentar a solução para a questão: Thiago Alves da Silva

Resolução:

Ainda não foi apresentada uma resposta correta para este exercício.