O tema dessa semana é bem simples e ao mesmo tempo enganador: algoritmos gulosos. Com eles normalmente resolvemos problemas que parecem tão complicados somente encontrando algum padrão de ordenação nos elementos, todavia podemos nos surpreender em diversos casos nos quais pensamos ter solução gulosa e recebermos Wrong Answer! Portanto, é bom aprender os casos clássicos e ter uma boa noção de provar corretude de algoritmos nesse paradigma.
Assunto: Algoritmos Gulosos
Bibliografia principal:
- Competitive Programming, capítulo 3 (3.4) - Greedy
- Introduction to Algorithms, capítulo 16 - Greedy Algorithms
- Interval Scheduling (Wikipedia)
Bibliografia complementar:
- Algorithm Design (Kleinberg, Tardos), capítulo 4 - Greedy Algorithms
- Top Coder - Greedy is Good
Problemas sugeridos:
- UVa 410 (Station Balance): problema clássico de algoritmos gulosos com mesmo nome do problema.
- UVa 11729 (Commando War): um tipo de problema de escalonamento de intervalos.
- UVa 10382 (Wattering Grass): problema bem interessante de cobertura intervalar mínima com um toque de geometria 2D.
- UVa 11157 (Dynamic Frog): um caso meio ad-hoc de algoritmo guloso, tornando a ideia bem difícil de se obter.
Nenhum comentário:
Postar um comentário