Jump to content

Programação Dinâmica - Tutorial/Slides


Recommended Posts

Reparei que nalguns tópicos têm surgido algumas dúvidas e perguntas sobre Programação Dinâmica (PD). Este é um tópico que me é muito "querido" e já fui o autor de muitos problemas de concurso cuja solução passava pelo uso da PD.

Assim, para quem estiver interessando, resolvi disponibilizar aqui no P@P os meus slides de apresentação de PD, que usei por exemplo no ENEI 2010 ou em aulas no DCC-FCUP. Existem N tutoriais disponíveis na net, pelo que esta é apenas "mais uma possível introdução ao mundo da PD", mas está em português e se for útil a alguém ficarei contente.

Slides sobre Programação Dinâmica - PDF (632 KB)

Já agora, mais algumas ligações interessantes sobre o tema:

- PD na Wikipedia: http://en.wikipedia.org/wiki/Dynamic_programming

- Tutorial de PD no TopCoder: http://www.topcoder.com/tc?d1=tutorials&d2=dynProg&module=Static

- Alguns problemas de PD e explicação de suas soluções: http://people.csail.mit.edu/bdean/6.046/dp/

- Aula do Skiena sobre PD (video+slides): http://www.algorithm.cs.sunysb.edu/programmingchallenges/page_21.html

- Livro sobre concursos, com capítulo sobre PD: http://www.comp.nus.edu.sg/~stevenha/database/Art_of_Programming_Contest_SE_for_uva.pdf

Edit (Warrior) : link corrigido

  • Vote 1
Link to comment
Share on other sites

Xisa! Só um link está em Português .... Eu sei ler Ingles mas é chato ter de se estar a ler e a traduzir embora o cérebro o faça automaticamente não nos podemos concentrar tão bem como se tivéssemos a ler em Português!

Cumprimentos, Rodrigo Graça

Isso é o que eu chamo "pobre e mal agradecido!" 🙂


Muito boa informação Pedro Ribeiro!

Obrigado pelo contributo. 😉

Link to comment
Share on other sites

Estive a ver os slides ao bocado e detectei dois erros.

No slide 23 diz "podemos aproveitar P[][]", não devia de haver alguma coisa dentro dos parênteses?

Por fim, no slide 33, tens a dizer, no quinto ponto, "Verificar se o problema obedece ao princípio de optimalidae", tens um erro em "optimalidade", que, por acaso, o firefox também está a dizer que está mal escrito... Mas no google ainda aparecem alguns resultados para essa palavra, por isso penso que a palavra deve de existir no dicionário.

De qualquer forma obrigado pelo acesso aos slides, que pelo menos deixaram-me comparar com os slides que o nosso professor deu aqui na FEUP. 🙂

Não me responsabilizo por qualquer dano ocorrido no seguimento dos meus conselhos. Prontos, a minha pessoa está oficialmente protegida legalmente 😄

Link to comment
Share on other sites

No slide 23 diz "podemos aproveitar P[][]", não devia de haver alguma coisa dentro dos parênteses?

Não é erro. Isso significa aproveitar a matriz P 🙂

Por fim, no slide 33, tens a dizer, no quinto ponto, "Verificar se o problema obedece ao princípio de optimalidae", tens um erro em "optimalidade", que, por acaso, o firefox também está a dizer que está mal escrito... Mas no google ainda aparecem alguns resultados para essa palavra, por isso penso que a palavra deve de existir no dicionário.

Sim, é um gralha, e deveria ler-se "optimalidade". A palavra é detectada como não existente pois é uma espécie de "jargão técnico" (e sim, "jargão" aparece num bom dicionário). É uma aproximação do termo original Principle of Optimality. Isto de "traduzir" em português tem sempre que lhe diga. Por exemplo, que traduções já ouviste para "hash table" em português? 😛

De qualquer forma obrigado pelo acesso aos slides, que pelo menos deixaram-me comparar com os slides que o nosso professor deu aqui na FEUP. 👍

Já agora, quem deu/dá PD na FEUP? Conheço bastante gente por lá, como por exemplo o André Restivo, que deves conhecer se participares em concursos 😄

Link to comment
Share on other sites

Não é erro. Isso significa aproveitar a matriz P 😁

Ah, ok, erro meu 😛

Sim, é um gralha, e deveria ler-se "optimalidade". A palavra é detectada como não existente pois é uma espécie de "jargão técnico" (e sim, "jargão" aparece num bom dicionário). É uma aproximação do termo original Principle of Optimality.

Apesar de saber o que o conceito de "jargon" significa, pensava que a tradução dessa palavra para português era "gíria".

Isto de "traduzir" em português tem sempre que lhe diga. Por exemplo, que traduções já ouviste para "hash table" em português? 🙂

Acho que só ouvi uma. "Tabela de Dispersão" e pelos vistos a wikipedia concorda 😛

No entanto o professor que me deu a matéria de hash tables era Brasileiro, por isso pode ter aprendido diferentes expressões para isso. No entanto, acho que ele só usou o termo tabela de dispersão uma ou duas vezes e depois passou a usar o termo hash table

Já agora, quem deu/dá PD na FEUP?

No meu curso (Engenharia Informática e Computação) demos programação dinâmica juntamente com outros métodos, como os algoritmos gananciosos e backtracking (retrocesso) numa cadeira do 2º ano, que eu acabei de ter, chamada "Concepção e Análise de Algoritmos", ou seja, não tivemos uma cadeira só para o estudo da programação dinâmica. Aliás, só falamos em programação dinâmica para aí em uma ou duas aulas. Por outro lado também falamos, mais para o fim do semestre, no algoritmo de cálculo de distâncias de edição entre strings que tens nos slides (mas isto já foi inserido na matéria de algoritmos de strings).

De qualquer forma, penso que a cadeira deveria ter sido dada pelo professor Rosaldo Rossetti, mas infelizmente penso que esteve doente durante alguns meses, entre o fim do 1º semestre (foi esse o professor Brasileiro de que estava a falar) e o início do 2º Semestre.

Por isso essas aulas iniciais (mais ou menos até às férias da Páscoa) foram dadas pelo professor Nuno Flores, tendo sido as restantes dadas pelo professor Rossetti.

Conheço bastante gente por lá, como por exemplo o André Restivo, que deves conhecer se participares em concursos

Não participo em concursos, por isso não conheço. No entanto estive a ver a página dele, e parece que não vai ter que me aturar para o ano, pois ele deu este ano uma cadeira de 3º ano (Laboratório de Bases de Dados e Aplicações Web) que eu não vou ter, porque fiz uma cadeira no 1º ano que dá equivalência a essa (a faculdade mudou este ano que passou a mudar o plano de estudos).

Por isso teve sorte 😛

Não me responsabilizo por qualquer dano ocorrido no seguimento dos meus conselhos. Prontos, a minha pessoa está oficialmente protegida legalmente 😄

Link to comment
Share on other sites

Eu conhecia o tabela de dispersão. Aliás, conheço a pessoa que, supostamente, primeiro introduziu essa expressão em Portugal. Só estava a fazer notar a dificuldade em traduzir certas palavras que, no meu caso, eu até prefiro usar na sua língua original. Por isso é que em algoritmos "gananciosos", outros falam em "gulosos", mas para mim são greedy e pronto 😁

No resto, também não temos na FCUP cadeira só de PD. Foi mais para saber quem dá as cadeiras de Algoritmia neste momento na LEIC (agora MEIC). Conheço lá muita gente também nos alunos, e até há pouco tempo, não se falava quase nada em PD em LEIC e fiquei curioso em quem introduziu isso nas aulas (e em boa hora o fez).

Não conheço o Rosaldo Rossetti, confesso. Conheço mais pessoas com o Augusto Sousa (penso que ainda seja o director do teu curso) ou a Cristina Ribeiro.

Link to comment
Share on other sites

Por isso é que em algoritmos "gananciosos", outros falam em "gulosos", mas para mim são greedy e pronto 😛

Om nom nom. Por acaso acho que nunca tinha ouvi o termo "algoritmo guloso".

Conheço mais pessoas com o Augusto Sousa (penso que ainda seja o director do teu curso).

E ainda é 😁

Continua a dar aulas de Computação Gráfica (no 2º ano) e penso que também dá aula do Laboratório de Computação Gráfica (no 3º ano), mas isso só vou confirmar para o ano.

Não me responsabilizo por qualquer dano ocorrido no seguimento dos meus conselhos. Prontos, a minha pessoa está oficialmente protegida legalmente 😄

Link to comment
Share on other sites

No post do Pedro Ribeiro já tinha lá esse link 😁

Mas sinceramente prefiro chamar-lhe de algoritmo ganancioso ou greedy, nem que seja só por ser uma tradução melhor de "greedy".

Não me responsabilizo por qualquer dano ocorrido no seguimento dos meus conselhos. Prontos, a minha pessoa está oficialmente protegida legalmente 😄

Link to comment
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now
 Share

×
×
  • Create New...

Important Information

By using this site you accept our Terms of Use and Privacy Policy. We have placed cookies on your device to help make this website better. You can adjust your cookie settings, otherwise we'll assume you're okay to continue.