Cadeias de Markov – Exemplo prático

Pode-se chamar de processo de Markov um sistema finito e discreto  formado por estados, onde existem probabilidades de transição entre os estados. Uma cadeia de Markov é a execução repetida de um processo de Markov.

Por exemplo, imagine um sistema formado pelos estados A, B e C. A transição de A-> B tem uma probabilidade C1, de A->C tem probabilidade C2, A->A (se manter no estado A) C3, e assim por diante. Um fato importante nesta definição de processo de Markov (de primeira ordem, como tratado aqui) é que a probabilidade de transição depende somente do estado atual.

Um exemplo de utilização está no cálculo das probabilidades de que, partindo de um estado inicial A, qual é a probabilidade de um novo estado B ser alcançado após K iterações? Para isto, monta-se uma matriz M, onde o valor da célula Mi,j corresponde à probabilidade da transição i->j. Para saber a chance de se alcançar o estado Z partindo do estado X após K iterações, deve-se consultar a célula Mx,z após o cálculo de M^K (exponenciação).

Um tutorial completo (escrito pelo Fabrício Bueno) pode ser acessado em Cadeias de Markov: Práticas e Aplicações .

O problema Vampiros da sub-regional da maratona de programação de 2008 servirá como exemplo. Não descreverei o problema aqui, favor consultar o link =) .

1º Passo: simplificação da energia vital e capacidade de dano

A capacidade de dano D  é a mesma para os dois vampiros, então pode-se simplificar o problema, reduzindo o dano para 1 e ajustando a energia vital de cada vampiro. Por exemplo, se EV1 = 3, EV2 = 4 e D = 2, então pode-se reduzir o problema para: Ev1 = 2, EV2 = 2 e D = 1.

2º Passo: simplificação dos estados

Para que o vampiro 1 ganhe a batalha, a energia vital do vampiro 2 precisa ser reduzida para 0. Como o vampiro que ganhou um turno ganha uma  quantia de energia igual ao dano causado, pode-se dizer que o vampiro 1 ganha quando ficar com EV = EV1 + EV2. Esta simplificação permite que a batalha seja modelada utilizando a energia vital do vampiro 1 como estados.

3º Passo: modelagem

A energia vital do vampiro 1 será utilizada na modelagem, onde cada estado corresponde à um valor de energia, que vai de 0 (o vampiro 2 ganhou) até EV1 + EV2 (o vampiro 1 ganhou). O estado 0 (correspondente à EV = 0) acarreta na derrota, e não pode-se sair dele, logo, se o vampiro está no estado 0, ele permanecerá lá, então a transição 0->0 tem probabilidade 1. O mesmo ocorre para o estado EV1 + EV2, pois se o vampiro já ganhou, ele permanece vitorioso. Nos outros estados, a chance de transição do estado Sn para Sn+1 é igual a AT / 6, e de Sn para Sn-1 é de 1 – (AT / 6).

Visualização:

Tomando o 2º caso de teste (1 2 1 1) temos o seguinte processo de Markov:

Processo de Markov para o exemplo

A matriz de transição M fica assim:

Matriz de transição

Respondendo à pergunta do problema: qual é a chance do vampiro 1 vencer neste caso? Bem, a batalha pode ocorrer até o fim dos tempos, então temos que limitar o número de rodadas para um valor factível, que devolva uma resposta dentro da precisão estabelecida.  Como a exponenciação de matrizes pode ser implementada em ~ O(log K) em relação ao número de transições K, pode-se fixar o K como 1000.

Então, modela-se o problema, montando a matriz M. Computa-se então M^K (M elevado à K) e verifica-se o valor de Ma,b, onde a é a vida inicial e b é a vida correspondente à batalha ganha (EV1 + EV2).

A mesma ideia de exponenciação de matrizes pode ser utilizada para a contagem de caminhos de A para B com tamanho K em um determinado  grafo. Neste caso, M é a matriz de adjacências, onde Mi,j vale 1 se existir o caminho i->j, e 0 se o caminho não existir.

GoGear Vibe + GNU / Linux

Problema:

Transferir músicas do computador para o aparelho, de forma que o aparelho possa ler os metadados como artista, album e nome da música.

Solução:

Diferente de outras versões, o GoGear Vibe consegue extrair os metadados, não sendo necessário utilizar programas como o openGogear. Só é necessário respeitar algumas limitações. No caso de áudio no formato mp3, é necessário que os metadados (id3) estejam na versão 2.3 e que seja utilizada a codificação ISO-8859-1. Pode ser que o aparelho também aceite outra versão / codificação, não cheguei a testar.

Programas:

Para realizar esta conversão de versão / codificação, utilizei o programa easytag. Outra alternativa é o eyeD3.
O aparelho pode ser acessado como se fosse um pendrive comum, sendo possível a transferência dos arquivos pelos gerenciadores de arquivos comuns.

Tutorial: nginx + Lua

Objetivo: configurar um servidor web que sirva conteúdo dinâmico utilizando a linguagem de programação Lua.
Pilha: Arch Linux, nginx, wsapi, fastcgi e Lua.

1º Passo: instalação dos pacotes

# pacman -Sy nginx fcgi
$ yaourt -S wsapi spawn-fcgi

2º Passo: configuração do nginx (web server)

Adicionar o seguinte conteúdo na seção http->server do arquivo /etc/nginx/conf/nginx.conf :

location ~ \.lua$ {
    root html;
    fastcgi_pass 127.0.0.1:9000;
    fastcgi_index  index.lua;
    fastcgi_param SCRIPT_FILENAME /srv/http/nginx$fastcgi_script_name;
    include fastcgi_params;
}

3º Passo: Hello World

Criar o arquivo /srv/http/nginx/index.lua com o seguinte conteúdo:

require('wsapi.response')
require('wsapi.request')

return function(env)
    local resp = wsapi.response.new()
    resp:write('Hello world!')
    return resp:finish()
end

A cada requisição, a função retornada pelo script é executada (o script só é carregado uma vez por instância).

4º Passo: ativar instâncias do FastCGI

$ sudo spawn-fcgi -F 4 -p 9000 -f /usr/bin/wsapi.fcgi

F (fork) é o número de filhos, p é a porta a ser utilizada e f o lançador.

5º Passo: teste:

$ sudo /etc/rc.d/nginx start
URL de acesso: localhost

Pronto.

gthread – exemplo

A biblioteca glib possui uma abstração de threads, com uma API simples  e que se mantém a mesma em todos os S.Os suportados.

Exemplo de utilização: Link

O exemplo mostra uma utilização bem básica, sem necessidade de compartilhar memória e etc. Aplicações reais nem sempre são tão simples! Documentação oficial: Link

Problema de Monty Hall

Programinha simples para simular o famoso problema de Monty Hall (Bertrand’s box paradox).

Link.

lgob 9.04!

No post anterior eu descrevi o projeto lgob. Agora anuncio a primeira versão ‘estável’, a 9.04 (optei por este tipo de versionamento, pois não faz sentido continuar com o 0.1, 0.2 e etc).

Mais informações em: http://oproj.tuxfamily.org .

lgob – Bindings para Lua

A um ano atŕas, eu publiquei bindings para Lua das bibliotecas GTK+, cairo, entre outras, no http://oproj.tuxfamily.org . Decidi automatizar a tarefa, escrevendo um gerador de código que lê informações dos arquivos “.gir” do projeto gobject-instrospection e gera código para exportar classes, funções e enumerações.

O projeto foi nomeado como lgob (lua gobject), e está disponível (via svn) em: http://svn.tuxfamily.org/viewvc.cgi/oproj_oprojsvn/lgob/ .

As vantagens da nova abordagem incluem: uma maior cobertura da API, maior facilidade para mudanças, e geração de código para versões específicas.

Intel GM965 vs performance 2D

Com o novo Xorg 1.6, meus antigos problemas com a performance 3D da minha Intel GM965 (aka X3100) acabaram, mas a performance 2D continuava horrível.

Testando outras configurações pro Xorg, cheguei nesta:

Section “Device”
Identifier  “Card0″
Driver      “intel”
VendorName  “All”
BoardName   “All”
Option “AccelMethod” “exa”
Option “MigrationHeuristic” “greedy”
Option “ExaNoComposite” “true”
EndSection

OK. Os métodos de aceleração suportados são: XAA (antigo, substituido pelo EXA), o EXA (perofrmance 3D melhorada, mas por padrão gera artefatos em algumas aplicações  que usam Qt 4) e o UXA (suporte ao dri2, mas ainda está um pouco instável).

Se não me engano o EXA é usado por padrção, então até ai nenhuma mudança. O que realmente melhorou a performance 2D (e corrigiu alguns bugs) foi o “Option “MigrationHeuristic” “greedy”.

Para testes, usei o programa gtkperf. Antes, uma rodada com 100 repetições demorava 16 segundos. Com a nova configuração, passou para 5 segundos. A performance 3D aparentemente não foi alterada, mas também não testei muito.

Novo site

O novo wiki, agora utilizando o http://www.dokuwiki.org/ (que de ruim só tem o nome) já esta estruturado e contendo um primeiro esforço para documentar os projetos.

A wiki pode ser acessada pelo endereço http://oproj.tuxfamily.org.

Poder do *scanf

A biblioteca padrão do C possui ótimas funções para leitura de dados, porém nem todo mundo sabe que a família *scanf (scanf, fscanf, etc) suporta até (uma versão simplificada) de expressões regulares.

Um exemplo:

Suponha que você tenha que ler uma entrada com a seguinte formatação:

Time1 vs Time2 : 3×2
Time2 vs Time3 : 10×5
Time1 vs Time2 : 1×8
Time3 vs Time1 : 0×0

A tarefa é retirar somente os nomes e os gols de cada time.

Com o bom e velho scanf, isso pode ser feito em uma só linha. Exemplo completo (escreva a entrada em um arquivo, e execute o programa redirecionando o arquivo para a entrada padrão (./programa < arquivo).

Código: Pastebin