programação dinamica

PROJETO E ANALISE DE ALGORITMOS

Lista de Exercícios: Programação Dinâmica

PARTE I

Para cada uma dos problemas a seguir, determine sua solução utilizando um algoritmo baseado em Programação Dinâmica. Apresente a estrutura de memória auxiliar, com seus valores, utilizada para armazenar as soluções dos subproblemas gerados e suas decisões locais ótimas.

1. Determine a solução do problema de reposição de equipamentos ilustrado nas notas de aula.
2. Determine a solução do problema de alocação de recursos ilustrado nas notas de aula.
3. Determine uma árvore binária de busca ótima para as seguintes probabilidades: p1= 1/20; p2= 1/5; p3= 1/10; p4= 1/20; q0= 1/5; q1= 1/10; q2= 1/5; q3= 1/20; q4= 1/20.
4. Determine uma subcadeia de soma máxima para o vetor a = (-3, 7, -5, 1, 8, -7, 3, -5,1,3,-4,-5,2). OBS.: resolva sobre o grafo de caminhos usado para representar este problema.
5. Determine a distância de edição entre as cadeias X e Y, definidas respectivamente por “aabaababaa” e “babaabab”. Mostre um alinhamento ótimo e também dois roteiros ótimos, um de edição de X em Y e outro de Y em X.

PARTE II

6. Mostre como implementar o algoritmo de PD apresentado para o problema de reposição de equipamentos, de forma a garantir uma complexidade de tempo O(n2), onde n é o tamanho do horizonte de decisão.
7. Apresente um algoritmo recursivo para construir regressivamente a árvore de busca ótima a partir da informação produzida progressivamente pela PD. Mostre que seu algoritmo é O(n).