Material da aula de introdução à programação dinâmica

Resumo da aula

Treinem PD desde cedo, sempre! Procurem se convencer porque ela funciona, não deixem de fazer esse passo!

Fibonacci
Jeito brute-force O(2^n) em tempo; O(1) em espaço

int fib(int n) {
   if (n==0 || n==1) return 1;
   return fib(n-1)+fib(n-2)
}

PD top-down O(n) em tempo; O(n) em espaço

int cache_fib[MAX_F]; /* inicializado com EMPTY (constante que é diferente de qualquer fibonacci possível) */

int fib(int n) {
   if (n==0 || n==1) return 1;
   if (cache_fib[n]==EMPTY)
      cache_fib[n]=fib(n-1)+fib(n-2);
   return cache_fib[n];
}

PD bottom-up O(n) em tempo; O(n) em espaço

int cache_fib[MAX_F];
cache_fib[0]=cache_fib[1]=1;

for (int i=2; i<=n; i++)
   cache_fib[i]=cache_fib[i-1]+cache_fib[i-2];

Note que aqui só usamos os dois últimos caras que calculamos – podemos usar isso para fazer uma otimização de memória, tornando o código O(1) no espaço:

int fibn_1=1, fibn_2=1, fib=1; /* a inicializacao de fib como 1 e pra evitar tratar a primeira iteracao serapado */

for (int i=2; i<=n; i++) {
   fibn_2=fib_n1;
   fibn_1=fib;
   fib=fibn_1+fibn_2;
}

Porque PD tem esse nome? Há, do artigo da Wikipedia, que por sua vez está citando a auto-biografia do Bellman (Eye of the Hurricane: An Autobiography (1984)):

I spent the Fall quarter (of 1950) at RAND. My first task was to find a name for multistage decision processes. An interesting question is, Where did the name, dynamic programming, come from? The 1950s were not good years for mathematical research. We had a very interesting gentleman in Washington named Wilson. He was Secretary of Defense, and he actually had a pathological fear and hatred of the word, research. I’m not using the term lightly; I’m using it precisely. His face would suffuse, he would turn red, and he would get violent if people used the term, research, in his presence. You can imagine how he felt, then, about the term, mathematical. The RAND Corporation was employed by the Air Force, and the Air Force had Wilson as its boss, essentially. Hence, I felt I had to do something to shield Wilson and the Air Force from the fact that I was really doing mathematics inside the RAND Corporation. What title, what name, could I choose? In the first place I was interested in planning, in decision making, in thinking. But planning, is not a good word for various reasons. I decided therefore to use the word, “programming” I wanted to get across the idea that this was dynamic, this was multistage, this was time-varying I thought, lets kill two birds with one stone. Lets take a word that has an absolutely precise meaning, namely dynamic, in the classical physical sense. It also has a very interesting property as an adjective, and that is its impossible to use the word, dynamic, in a pejorative sense. Try thinking of some combination that will possibly give it a pejorative meaning. Its impossible. Thus, I thought dynamic programming was a good name. It was something not even a Congressman could object to. So I used it as an umbrella for my activities.

Nomenclatura:

  • estado: o que queremos guardar e em quais variáveis precisamos iterar

No exemplo de fibonacci, o estado é fib(n)= n-ésimo termo da sequência fibonacci

  • recursão (equação de Bellman): como formar um estado a partir de outros estados previamente calculados

Em fibonacci, a recursão é f(n) = f(n-1)+f(n-2)

  • casos base: todos os casos necessários para rodar a primeira iteração da recursão

Veja que, no caso do fibonacci, você precisa dos dois termos anteriores, o que significa que pra rodar a primeira iteração, precisamos de dois casos base, que são f(0)=1 e f(1)=1

Actually, se vocês estudaram Estruturas Discretas, já viram isso com o nome de indução – pois é, PD é "só" guardar os estados já calculados de uma indução. Aliás, você só precisa guardar as coisas que você sabe que vai usar no futuro, como foi mostrado no exemplo do fibonacci. De qualquer forma, como você guarda coisas ao invés de calcular, podemos dizer que programação dinâmica é uma troca de espaço por performance.

DICA IMPORTANTE: A palavra "subarray" implica adjacência (isso é, um intervalo contínuo) enquanto "subsequência" não

MSA (Maximum Subarray – pessoal, errei o nome na aula, me desculpem):
Jeito brute-force: O(n^3) em tempo; O(1) em espaço
Jeito brute-force com somas parciais (acabei não comentando na aula porque não lembrava o nome correto, mas é o nome da técnica de fazer um vetor onde a[i]=soma do intervalo [0,i], ou [0,i) em alguns casos): O(n^2) em tempo; O(n) em espaço
Jeito divide-and-conquer: O(n log n) em tempo; O(1) em espaço (não tenho tanta certeza sobre, depois tenho que verificar)
Jeito PD (chama-se algoritmo de Kadane, sendo a Wikipedia): O(n) em tempo; O(n) em espaço, O(1) com otimizações de memória
Referência da Wikipedia: http://en.wikipedia.org/wiki/Maximum_subarray_problem

LIS (Longest Increasing Subsequence)
Jeito exponencial (recursivo) e prova de que ele funciona
Guardando informações para diminuir a complexidade
Existe algoritmo melhor? Sim, esse problema pode ser feito em O(n log n)

Knapsack (problema da mochila)
Jeito brute force: O(2^n) em tempo; O(1) em espaço – tenta todas as combinações de objetos na mochila
Jeito PD: O(n*K) em tempo; O(n*K) em espaço, onde K é o peso máximo da mochila
Referência: http://en.wikipedia.org/wiki/Knapsack_problem

Exercícios

Nota sobre esse problema: http://www.wolframalpha.com/input/?i=fib+5000 e http://www.cplusplus.com/reference/climits/ (pensem um pouco ae)

Material complementar

Nota: o material complementar não necessariamente fala sobre os algoritmos dados na aula

De Stanford – Algorithms: Design and Analysis, Part II: https://class.coursera.org/algo2-2012-001/lecture/preview
Todos os vídeos da semana 3, ou seja, do tópico X ao XIII
Do MIT – Introduction to Algorithms (SMA 5503): http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-046j-introduction-to-algorithms-sma-5503-fall-2005/video-lectures/lecture-15-dynamic-programming-longest-common-subsequence/
Do MIT – Introduction to Algorithms 6.006: http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-006-introduction-to-algorithms-fall-2011/lecture-videos/
Ctrl+F em "Dynamic Programming" should do the trick, mas se vocês não quiserem, de 19 a 23

Todos os livros citados na página de informação aos calouros têm partes de programação dinâmica relevante, mas lembro do Tardos ter as explicações especialmente afinadas.

Soluções dos exercícios

(fazer)

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-NonCommercial-ShareAlike 3.0 License