Aula #06
	Pedro Ribeiro - DCC/FCUP

Principais conceitos abordados na aula

1. Conceitos de Programação Dinâmica (DP - Dynamic Programming):
   • Conheço o princípio minimax para jogos e sei como usar DP para resolver problemas simples de jogos.
   • Conheço o problema das partições lineares e sei como usar DP para obter partições ótimas
   • Conheço o conceito de DAGs e sei como usar DP para resolver problemas em DAGs
   • Conheço o conceito de bitmasks e sei como usá-las em estados de DPs; conheço o problema de TSP e como resolvê-lo em O(n^2 2^n) usando DP e bitmasks
   • Percebo o conceito de fazer contagens com DP

Material de Estudo

Principais referências

• Jogos e principio minimax
• Slides meus de Algoritmos (versão portuguesa de slides de DP - slides 51 a 54 explicam o jogo das pedras)
• Algorithm Games (TopCoder)
• Minimax (South African IOI Camp)
• Game Theory (PG Wiki)
• Partições Lineares
• The Partition Problem (Algorithm Design Manual)
• DP em DAGs
• DP on Trees and DAGs (IOI Training, Philippines)
• Bitmasks e DP
• A bit of fun: fun with bits (TopCoder)
• Dynamic Programming and Bit Masking (HackerEarth)
• A little bit of classics: dynamic programming over subsets and paths in graphs (CodeForces)
• TSP com Programação Dinâmica
• Travelling Salesman Problem (GeeksforGeeks)
• Held-Karp Algorithm (Wikipedia)

[em construção - vou acrescentar aqui mais ligações]

Problemas de Iniciação/Reforço

• UVA 10404 - Bachet's Game (DP with games - minimax principle)
• UVA 11258 - String Partition (DP partitions)
• UVA 10258 - Longest Run on a Snowboard (DP in DAGs)
• SPOJ COURIER - The Courier (DP with bitmasks, TSP)
• UVA 10910 - Marks Distribution (DP counting)

Pedro Ribeiro - DCC/FCUP | Último update: