MAC499 - Trabalho de Formatura Supervisionado

Proposta

Aluno

Stefano Tommasini

Orientador

Professor Carlos Eduardo Ferriera

Tema

Programação Dinâmica

Resumo

Programação Dinâmica é uma técnica muito importante para a resolução de problemas de otimização. Ela consiste em quebrar um problema grande em subproblemas menores que se sobrepõem, e obedecem a propriedade de subestrutura ótima. Um problema apresenta uma subestrutura ótima quando uma solução ótima para o problema contém em seu interior soluções ótimas para subproblemas. A superposição de subproblemas acontece quando um algoritmo recursivo reexamina o mesmo problema muitas vezes.

A programação dinâmica pode ser pensada como uma força bruta com memorização, já que reexaminamos um mesmo problema muitas vezes. Desta forma, podemos memorizar a resposta guardando-a numa estrutura de dados, calculando assim cada subproblema uma só vez.

Apesar de ser uma técnica básica, abordada em disciplinas iniciais de Algoritmos e Estruturas de Dados, muitas vezes os alunos têm dificuldades de resolver problemas em que a técnica é necessária. Neste trabalho pretendo criar um material didático em português sobre programação dinâmica para auxiliar o aprendizado do tópico. Pretendo fazer isso atravéz de exemplos, usando problemas de diferentes abordagens e dificuldades. Durante o desenvolvimento, este material será usado em cursos de graduação com o proposito de testá-lo e receber feedback.

Objetivos

• Estudar problemas que ultilizam programação dinâmica na resolução;
• Criar um bom material Didático sobre o tema;
• Implementação de alguns problemas bem documentados;

Atividades já realizadas

• Muitos problemas estudados e implementados.

Cronograma

Estrutura esperada da monografia

Primeira parte:

• Introdução
• Conceitos e tecnologias estudadas
• Atividades realizadas
• Resultados esperados e obtidos
• Conclusão
• Bibliografia

Parte subjetiva:

• Dificuldades e frustrações
• Lista de disciplinas do BCC que foram importantes para o projeto e suas aplicações
• Próximos passos para o trabalho
• Agradecimentos