Aulas e o jogo de aprendizado

Programação dinâmica e otimização

Resolva as decisões mais difíceis de uma missão espacial com tabelas, em um Raspberry Pi 4: de uma escada de acoplagem a um planejador de rotas entre estações espaciais.

O curso

Programação dinâmica e otimização é um curso avançado de Programação em sete aulas, depois de Recursão e backtracking. Cada aula é Python puro no Pi, com a montagem de dois LEDs da galeria e o módulo de semáforo onde algo deve acender. Cada passo é conferido com o que o Pi imprime ou o que seus pinos fazem, e todo número nas aulas é um que o programa realmente imprime.

  1. Overlapping subproblems: a 16-rung docking ladder climbed 1, 2 or 3 rungs at a time. The slow recursion makes 37,921 calls and works out rung 2 3,136 times; a memo cuts it to 49 calls, a table fills it bottom up, and three rolling numbers climb 1000 rungs.
  2. Coin change: thruster burns of 9, 6, 5 and 1 m/s. Greedy uses three burns for 11 m/s where DP finds two (5 and 6), a pick table says which, a second table counts the 6 mixes, and reachability lists the speeds 4 and 7 m/s burns can never make.
  3. Mochila: 10 kg de carga de foguete para a maior ciência. Força bruta em 256 carregamentos, a tabela da mochila 0/1, o carregamento refeito de trás para frente, a versão de uma linha com o bug clássico para frente, e 30 caixas resolvidas em 3.030 células.
  4. Distância de edição: comandos de sonda corrompidos. Por que contar posições falha, a tabela de Levenshtein impressa completa, as edições refeitas de trás para frente, e uma linha de comando que responde "você quis dizer DEPLOY?"
  5. Gulosa vs PD: passagens de satélite por fim mais cedo (comprovadamente certa) contra mais curta primeiro (errada), combustível dividido contra tanques inteiros, e uma verificação de quais sistemas de moedas a gulosa consegue resolver.
  6. Agendamento: passagens que carregam quantidades diferentes de dados. A gulosa consegue 105 MB, uma PD com bisect consegue 120, o agendamento é refeito de trás para frente e tocado no LED vermelho, e uma linha de varredura conta antenas.
  7. Projeto: um planejador de rotas: o final.

O gran final

Um planejador de balsas entre oito estações espaciais. Os tempos mínimos vêm de uma PD na ordem das estações (o mapa só voa para fora, então é um grafo dirigido acíclico): da Terra a Titã em 45 horas. A rota é refeita a partir de came_from, uma segunda tabela responde a melhor rota com no máximo k trechos (rodadas de Bellman-Ford, 49 horas em quatro trechos), e um quiosque recebe um destino pelo Serial Monitor e acende os semáforos: verde para uma rota, vermelho para uma estação que não existe.

O que o motor do Pi faz de diferente

O Pi roda MicroPython 1.29, não CPython:

  • Não há numpy, então toda tabela é uma lista ou uma lista de listas, que é como a PD é ensinada de qualquer forma.
  • Dicts não mantêm a ordem em que as chaves entraram. O planejador lê seus dicts apenas por chave, e tudo que é impresso vem de listas.
  • A recursão para perto de 1.000 chamadas, então uma memoização de cima para baixo não consegue subir uma escada de 1000 degraus. O curso usa isso para mostrar por que tabelas de baixo para cima importam.
  • str.rjust não existe, então a tabela de distância de edição preenche os números com "%2d" % v. bisect, functools e inteiros grandes funcionam como no CPython.