Programação Dinâmica

setembro 8, 2008 às 11:33 pm | Publicado em Algoritmos | 2 Comentários

Programadores muitas das vezes dão de cara com alguns problemas que devem ser resolvidos com uma solução melhor. A solução de um problema já pode até existir mas pode não ser a melhor ou a mais rápida solução possível, várias companhias estão interessadas em pessoas que conseguem desenvolver algoritmos que aumente a velocidade de execução dos programas.  Se uma companhia qualquer tiver um programa de grande importância que é usado diariamente por vários de seus clientes e o algoritmos que está por trás executa em tempo exponencial, essa companhia com certeza pagará bem por um algoritmo que execute em tempo polinômial. Então procure aprender Programação Dinâmica pra não passar fome! (nem tanto neh…)

Programação Dinâmica muita das vezes é mal interpretado por muitas pessoas pensando que é o nome de um algoritmo, mas na realidade é o nome de uma técnica de programação avançada que você pode usar para escrever um bom algoritmo. Programação dinâmica no começo parece mágica pois conseguimos ver o que está acontecendo mas não sabemos como fazer até aplicarmos a técnica em alguns exemplos. Existem dois tipos de programação dinâmica: (bottom-up) resolve os problemas de pequena dimensão e guarda as soluções; solução de um problema é obtida combinando as de problemas de menor dimensão ou (top-down/divisão e conquista) o problema é partido em subproblemas que se resolvem separadamente; solução obtida por combinação das soluções.

Exemplo: Abaixo está um figura de como seria calcular o n-ésimo numero fibonacci sem a técnica de programação dinâmica, nessa figura seria o n seria 6.

Note que exite grupos de problemas que já foram resolvidos mas que seram calculados novamente. O sub-problema F4 esta sendo calculado do lado esquerdo e direito da árvore. O F3, F2 e F1 também estão sendo recalculados, isto é traduzido para perca de tempo.

Algoritmo usando programação dinâmica (botton-up):

Qualquer dúvida ou se você quizer o algoritmo do top-down
deixe um comentário.

Anúncios

2 Comentários »

RSS feed for comments on this post. TrackBack URI

  1. Você poderia responder para mim este exercício: 1.1 a) pág 51 Bertsekas, vol 1

    Considere o sistema

    x[k+1]=x[k]+u[k]+w[k], k=0,1,2,3
    com estado inicial x[0]=5 e a função custo

    somatório de k=0 a 3 (x[k]ao quadrado + u[k] ao quadrado).

    Aplique o algoritmo de programação dinâmica para este caso:
    o conjunto de restrições de controle U[k](x[k]) é [u | 0 <= x[k] + u <= 5, u: inteiro} para todo x[k] e k e o distúrbio w[k]=0 para todo k.

  2. Poderia colocar o exemplo do algoritmo do top-down


Deixe um comentário

Preencha os seus dados abaixo ou clique em um ícone para log in:

Logotipo do WordPress.com

Você está comentando utilizando sua conta WordPress.com. Sair /  Alterar )

Foto do Google+

Você está comentando utilizando sua conta Google+. Sair /  Alterar )

Imagem do Twitter

Você está comentando utilizando sua conta Twitter. Sair /  Alterar )

Foto do Facebook

Você está comentando utilizando sua conta Facebook. Sair /  Alterar )

Conectando a %s

Crie um website ou blog gratuito no WordPress.com.
Entries e comentários feeds.

%d blogueiros gostam disto: