View
2
Download
0
Category
Preview:
Citation preview
2016-I
Programação Dinâmica
COM11087-Tópicos Especiais em Programação Iedmar.kampke@ufes.br
Introdução
2016-I2
� Programação Dinâmica é uma forma poderosade resolver problemas combinatórios quepossuem elementos ordenados da esquerdapara direita (Strings)
� Após o entendimento se torna relativamentefácil
� Parece mágica até se ver muitos exemplos
Coeficientes Binomiais
2016-I3
Coeficientes Binomiais
2016-I4
Programação Dinâmica
2016-I5
� Problemas combinatórios exigem que se ache amelhor solução possível respeitando asrestrições
� Backtracking busca todas as soluções possíveis eretorna a melhor. Ou seja, retorna a respostacorreta porém para problemas grandes éinviável
� Algoritmos Gulosos, tomam as melhoresdecisões naquele instante. Ou seja, é eficienteporém não apresenta corretude
Programação Dinâmica
2016-I6
� Problemas combinatórios exigem que se ache amelhor solução possível respeitando asrestrições
� Backtracking busca todas as soluções possíveis eretorna a melhor. Ou seja, retorna a respostacorreta porém para problemas grandes éinviável
� Algoritmos Gulosos, tomam as melhoresdecisões naquele instante. Ou seja, é eficienteporém não apresenta corretude
Programação Dinâmica
2016-I7
� Programação Dinâmica nos fornece então apossibilidade de projetar algoritmos que vãoexplorar todas as possibilidades (corretude) eevitam computação redundante (eficiência)
� Definem assim recursividadeA solução do problema original vai depender dasolução de problemas menores
� Lembra Backtracking, mas não é!
Programação Dinâmica
2016-I8
� Um possível defeito da busca recursiva é acomputação redundante
� Solução: Armazenar informações sobre a busca
� Por que a Busca em Largura é finita?
� O Backtracking é ineficiente pois testa todas aspossibilidades não somente as inéditas.
Programação Dinâmica
2016-I9
� Assim Programação Dinâmica é uma técnicapara acelerar algoritmos recursivos
� Dica: Perceber se o algoritmo recursivocomputa o mesmo subproblema repetidamente
� Se isso acontece pode se armazenar osresultados já calculados.
� Depois que construímos um algoritmo recursivocom corretude é que nos preocupamos emacelerar
Outros Exemplos
2016-I10
� Fatorial
� Fibonacci
� Problema da Mochila (Binário)
� Casamento Inexato de padrões
� Maior Subsequência comum
� Maior Subsequência Monotônica
� Cadeia de Multiplicação de Caracteres
Programação Dinâmica
2016-I11
� Observe que Programação Dinâmica é aplicávela problemas que possuem as seguintespropriedades:
- Problema pode ser dividido em problemasmenores e a combinação dessas soluções é asolução do problema original
- O espaço de subproblemas é pequeno e hárepetição.
� Melhor aplicada em algoritmos recursivos
Programação Dinâmica
2016-I12
� Não confundir Programação Dinâmica comDividir para Conquistar
� Melhor usar Programação Dinâmica quando adistância entre os subproblemas e o problemaoriginal não for muito grande
� As estruturas adequadas para armazenar oresultado dos subproblemas é muito importante
Programação Dinâmica
2016-I13
� VantagensEconomizam computação em problemas quepossuem superposição de subproblemas (Ganhoem desempenho).
� DesvantagensO número de soluções armazenadas na tabelapode crescer rapidamente caso o espaço desoluções não seja pequeno (Exigindo assim muitamemória).
Mais Exemplos
2016-I14
� Soma de Subconjuntos
� Troco de Moedas
� Soma Máxima em uma Linha
Exercícios
2016-I15
• Is Bigger Smarter?
• Cutting Sticks
• Distinct Subsequences
• Weights and Measures
• Chopsticks
2016-I
Programação Dinâmica
COM11087-Tópicos Especiais em Programação Iedmar.kampke@ufes.br
Recommended