Aluno: Victor de Oliveira Colombo
Supervisor: Carlos Eduardo Ferreira
Algoritmos gulosos são uma classe de algoritmos muito importantes para a resolução de problemas de otimização. Nestes algoritmos, cada passo é escolhido visando minimizar localmente o objetivo e, desta forma, espera-se chegar ao mínimo global.
Em geral, esta técnica é muito mais simples de implementar e eficiente quando comparada com, por exemplo, Programação Dinâmica. Por outro lado, nem sempre existe tal algoritmo resultando na solução ótima e, quando existe, a demonstração de corretude pode se mostrar bastante complexa. Além disso, alguns problemas podem apresentar múltiplas estratégias gulosas convincentes, sendo várias dessas subótimas.
Embora este tópico esteja presente na ementa de qualquer curso introdutório de algoritmos, muitos alunos têm dificuldades para discernir quando utilizá-lo em detrimento das demais técnicas. Nestes cursos, normalmente são apresentados apenas problemas clássicos, como Activity selection, com livro texto em língua estrangeira. Além disso, os problemas cobertos são resolvidos exclusivamente por esta técnica, ou seja, não é visto a utilização de algoritmos gulosos aliado a outros algoritmos, limitando a complexidade dos problemas que podem ser abordados.
Neste trabalho, produzirei material didático em português focado no ensino de técnicas por meio de resolução de problemas desafiantes e não usuais, como vistos em competições como ACM ICPC e Google Code Jam, a fim de desenvolver no leitor a capacidade de identificar se um problema tem estratégia gulosa ótima, propor tal solução e implementá-la, transformando este processo em algo sistemático.
| Atividade | Abr | Mai | Jun | Jul | Ago | Set | Out | Nov | |||
|---|---|---|---|---|---|---|---|---|---|---|---|
| Seleção, estudo e análise dos problemas | • | • | • | • | |||||||
| Elaboração da monografia | • | • | • | • | • | ||||||
| Elaboração de materiais suporte (ministração de aulas, gravação de videos, etc) |
• | • | • | ||||||||