Uma das estratégias de resolução algoritmica de problemas mais difíceis de ser aplicada, na minha opinião, é a programação dinâmica. Mas existem alguns truques que facilitam o desenvolvimento de algoritmos baseados nessa idéia.

A maior dificuldade de se usar este método é encontrar a poderosíssima fórmula de recorrência. Uma vez encontrada, o algoritmo está quase pronto. O problema é que, para encontrar a fórmula de recorrência, é preciso pensar recursivamente, afinal programação dinâmica é praticamente uma recursão memorizada.

Vejamos um exemplo: o jogo da velha (inspirado pelo Rafael Izbicki, que me enviou um jogo da velha). Como fazer a melhor jogada em um determinado momento? Uma solução possível é tentar todas as jogadas possíveis até o fim, usando recursão (a melhor jogada para agora é a que ganha supondo que meu adversário vai fazer a melhor depois da minha, e assim por diante), e então escolher uma que dê um bom resultado. Mas, sem guardar as contas, testaríamos muitas vezes as mesmas jogadas. Então por que não guardar todas as seqüências de jogadas possíveis? Se fizermos isso, podemos até manter uma base de dados com todas as melhores jogadas para cada situação.

Note que, podendo memorizar todos os resultados, basta executar o algoritmo apenas uma vez e já teremos todos os resultados. Sem memorização, além de calcular várias vezes as mesmas jogadas, teríamos que executar o algoritmo a cada jogada.

Lógico que nem todo caso é fácil de resolver que nem o exemplo acima. Mas a idéia fundamental por trás da programação dinâmica é a recursão. Então, quando surgir um problema para o qual você tem uma solução recursiva, veja se não é possível memorizar a recursão.

Veja mais exemplos aqui. Note que, em todos, a idéia é tentar dar um passo, ver o que acontece até o fim e aprender com o resultado.

Posts Relacionados:

Acompanhe-nos por RSS, por Email ou via Twitter.

Eu tenho um problema crônico de memória. Tenho idéia ou preciso fazer algo e cinco minutos mais tarde eu já esqueci. Já tentei usar agenda de papel (não lembrava de dar uma ohada de vez em quando), agendas virtuais (o Google Calendar está praticamente esquecido.).

Passei então a usar drafts no GMail para as coisas que eu precisava lembrar.Isso foi bom até o momento em que fiquei com mais de 30 drafts e a bagunça ficou geral.

Algumas semanas atrás eu estava dando uma olhada no Remember The Milk (O Rafael estava usando na época). Achei simples e funcional, mas esquecia de olhar também.

Até que a equipe do RTM teve a genial idéia de integrá-lo ao GMail. Como você sempre tem uma aba do GMail aberta no Firefox, você pode manter sua agenda sempre aberta. E quando for dar uma olhada no GMail, você vê a sua agenda por tabela e nem precisa lembrar que ela existe (funcionou muito bem pra mim).

Recomendo muito esse addon. Mesmo que você use algum outro tipo de agenda, vale a pena dar uma olhada nele.

Posts Relacionados:

Acompanhe-nos por RSS, por Email ou via Twitter.

Recentemente tive um problema com uma mudança de pacotes no Ubuntu. O antigo TeTex foi substituido pelo TeXLive, que possui uma pequena incompatibilidade no uso de arquivos com encoding UTF-8 (e quando você manda instalar o TeTex, ele instala o TeXLive).

A diferença é realmente pequena, mas me custou algumas horas de dor de cabeça e Google (que não ajudou muito).

No TeTex, para usar UTF-8, você inseria o seguinte comando:

\usepackage[utf-8]{inputenc}

Com o TeXLive fica:

\usepackage[utf8]{inputenc}

O erro gerado (pela ferramente pdflatex), se você colocar o “-”, é o seguinte:

! LaTeX Error: File `utf-8.def' not found.

Type X to quit or <RETURN> to proceed,
or enter new name. (Default extension: def)

A solução eu obtive por sorte. Apenas pra ver o que acontecia resolvi retirar o “-” e funcionou. Espero que evite dores de cabeça para vocês.

Posts Relacionados:

Acompanhe-nos por RSS, por Email ou via Twitter.

Eu acredito que um bom conto seja muito mais difícil de escrever do que um bom romance.

O conto é mais curto e é necessária muita habilidade para em poucas páginas apresentar os personagens e contar a história. Normalmente bons escritores de romances não são muito bons contistas. Tolstóy é uma exceção.

Quando peguei este livro para ler, já fui com altas expectativas. Eu esperava algo no mínimo à altura de Guerra e Paz. O livro superou muito o que eu esperava.

“O Diabo e outras histórias” reune cinco contos maravilhosos, com cenas realmente marcantes (do tipo que passam meses e você ainda lembra como se tivesse visto hoje cedo) e uma grande carga emocional. Chega a ser assustadora a leitura de alguns trechos.

Embora os cinco contos sejam incriveis, os dois últimos contos (”Falso cupom” e “Depois do baile”) merecem destaque.

“Falso cupom” é uma história que começa simples. Um garoto é convencido a enganar uma vendedora pagando com um cupom falsificado (no caso, cupom é quase como um cheque) por ele. Isso começa a desencadear uma série de eventos (um mais destrutivo que o outro) que praticamente vai arrasando o modo de vida das pessoas. Até o momento (pra mim, a cena mais marcante do livro) em que uma pessoa não reage com agressividade quando é vítima do que o cupom criou. Após isso começa uma espécie de caminhada de redenção, onde todos que fizeram algo de errado devem pagar. É muito interessante o ciclo que é formado e como a história é contada.

“Depois do baile” trata da destruição da imagem que podemos ter de uma pessoa. Um jovem vai ao baile, dança a noite inteira com a garota pela qual estava apaixonado e conhece o pai dela (que aparentemente aprova as intenções do jovem). O pai dela, general do exército russo desperta nele muita adimiração. Após o baile, ele não consegue dormir e resolve passear pela noite. Ao amanhecer encontra presos sendo transportados pelo general que conhecera no baile. Não continuo pois destruiria o conto, que é muito bem narrado por Tólstoy.

É um livro que realmente me surpreendreu. Se alguém está apaixonado pela literatura russa como eu, esse livro é obrigatório.

Posts Relacionados:

Acompanhe-nos por RSS, por Email ou via Twitter.