Aluno: Victor Sena Molero
Supervisora: Cristina Gomes Fernandes
As matrizes Monge têm propriedades como a monotonicidade total e a monotonicidade, que são exploradas por uma série de algoritmos para a busca de máximos e mínimos em linhas e colunas destas matrizes. Algumas destas técnicas são populares pois são utilizadas para a agilização de problemas clássicos e aparecem com crescente frequência em competições de programação por sua utilidade na solução eficiente de problemas de programação dinâmica.
Busca-se neste trabalho formalizar, compilar e aprofundar os conhecimentos adquiridos sobre estes algoritmos por meio do estudo da literatura já existente (GALIL,1992; BEIN,2009) a fim de facilitar o aprendizado destas técnicas. Além disso, procura-se generalizar os algoritmos inspirando-se em desafios propostos em competições, explorando suas limitações e modificando as formalizações encontradas na literatura para ampliar os escopos tradicionais. Serão disponibilizadas, também, implementações eficientes dos algoritmos estudados que sejam utilizáveis em diversos cenários. Serão criados e fornecidos testes para comparar as velocidades delas quando possível.
| Atividade | Jan | Fev | Mar | Abr | Mai | Jun | Jul | Ago | Set | Out | Nov |
|---|---|---|---|---|---|---|---|---|---|---|---|
| 0 | ✓ | ✓ | |||||||||
| 1 | ✓ | ✓ | |||||||||
| 2 | ✓ | ✓ | |||||||||
| 3 | ✓ | ||||||||||
| 4 | ✓ | ✓ | |||||||||
| 5 | ✓ | ||||||||||
| 6 | ✓ | ✓ | ✓ | ||||||||
| 7 | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | |
| 8 | ✓ | ✓ | |||||||||