Descobrindo os parametros de um LCG

Uma das razões para não se utilizar geradores de números pseudo-aleatórios baseados em congruencia linear em criptografia é o fato destes serem passíveis de se descobrir os parametros de geração.

Tomarei como base o excelente artigo How to crack a Linear Congruential Generator, publicado na Reteam.org, onde o autor vale-se do efeito Marsaglia para descobrir tais parametros.

Marsaglia, renomado matemático americano, descobriu em 1968 que geradores baseados em congruencia linear geram números inteiros que formam planos hiperdimensionais quando plotados graficamente (vide imagem abaixo).

Basicamente, a solução proposta no artigo da Reteam faz uso da determinante de uma matriz tridimencional, composta por uma sequencia consecutiva de quatro números obtidos do gerador, para encontrar valores que são múltiplos do parâmetro m.

Em seguida, de posse de diversas determinantes, basta fazer um simples MDC para obter o valor correto de m.

Outra forma de calcular o MDC é usando-se o algoritmo de euclides:


function gcd(a, b)
if b = 0 return a
else return gcd(b, a mod b)


Uma vez que se tem m, pode-se obter os fatores a e c resolvendo-se um sistema de equações lineares congruenciais.

Vamos testar esse procedimento na prática.

1) Pega-se uma sequencia de números geradas pelo LCG em estudo:

S = {122, 4803, 7546, 9035, 4824, 727, 506, 2793, 7246, 2237…}

2) Da sequencia original S, pegaremos três sub-sequencias A, B e C:

A = {122, 4803, 7546, 9035}
B = {4803, 7546, 9035, 4824}
C = {7546, 9035, 4824, 727}

3) Calcula-se as determinantes de A, B e C.

Definindo-se os elementos das sub-sequencias como {a, b, c, d}, calcularemos a determinante da seguinte forma:

det = | (a * c + b * d + c * b) – (c * c + a * d + b * b) |

Assim:

det A = | (122*7546 + 4803*9035 + 7546*4803) – (7546*7546 + 122*9035 + 4803*4803) | = 554040

det B = 13767894

det C = 23832954

4) Calcula-se o MDC das determinantes.

Calculamos m = MDC(det A, det B, det C):

m = MDC( 554040, 13767894, 23832954 )

logo, usando-se o algoritmo de euclides:

m = 554040 * 13767894 mod 23832954 = 12567474
m = 23832954 mod 12567474 = 11265480
m = 12567474 mod 11265480 = 1301994
m = 11265480 mod 1301994 = 849528
m = 1301994 mod 849528 = 452466
m = 849528 mod 452466 = 397062
m = 452466 mod 397062 = 55404
m = 397062 mod 55404 = 9234

Como “55404 mod 9234 = 0”, então m é igual a “9234”.

5) Resolve-se as equações lineares para obter os parametros a e c.

Lotofácil: técnica da mínima colisão

A lotofácil é uma loteria da Caixa Economica Federal do Brasil de aposta relativamente barata e que dá boas chances de acertos aos seus apostadores.

Além das bem conhecidas qualidades supracitadas, ela proporciona uma estrutura de funcionamento bastante interessante de ser estudada por amantes do campo de probabilidades e combinatória.

Matemática à parte, trata-se de uma loteria bastante popular e que pode servir também como boa opção (melhor que Megasena) pra apostadores não profissionais.

Nesse sentido, sabendo-se que em geral o apostador eventual dessa loteria faz apenas duas apostas simultaneas em um dado concurso qualquer, comecei a imaginar formas de otimizar tal dupla de aposta.

Foi a partir da premissa do apostador eventual e averso a riscos, que, através de diversos testes computacionais e matemáticos, cheguei ao método da colisão mínima, descrito em maiores detalhes no artigo constante em minha página pessoal (veja aqui o referido artigo).

Tal método é de simples memorização e garante maiores chances de algum ganho quando as combinações são apostadas em conjunto, do que se tivessem sido escolhidas puramente ao acaso. Para fazê-lo basta proceder da seguinte forma:

1. Escolha cinco dezenas e marque-as nas duas apostas;
2. Marque outras dez dezenas na primeira aposta;
3. Marque as dezenas restantes da segunda aposta que não constem na primeira.

Fica aqui então minha dica. Espero que seja de grande ajuda aos que arriscam a sorte em loterias apenas eventualmente.

Sistemas legados e números aleatórios

Recentemente precisei gerar números aleatórios em um sistema escrito em linguagem legada, no caso, o velho e confiável COBOL.

O objetivo era usar esses valores na chave primária de uma tabela, pois tinhamos como requisito que essa chave contivesse números sem significado, sorteados de tal forma que não fossem de fácil adivinhação, descartando-se assim o uso de um simples campo numérico autoincremental.

No caso, como a aplicação não precisava de primor estatístico e nem segurança criptográfica – além da linguagem não dar suporte a operadores binários – optei por implementar um simples gerador baseado em congruencia linear.

Nesse tipo de gerador, temos a seguinte relação recorrente:

O problema foi como escolher os três parâmetros de geração a, c e m de forma que possam ser processados em inteiros de 18 digitos (limitação imposta pela linguagem) e que tenha um ciclo de repetição o mais longo possível, isto é, percorra todos os números do conjunto de inteiros previamente definido antes que ocorra repetição dos elementos gerados.

Para calcular tais parâmetros, fiz uso da dica constante na própria página da wikipedia que diz como escolher valores que resultem em períodos longos de geração sem repetição.

Assim, com base no método citado no artigo, construí o roteiro abaixo (que é uma versão simplificada do roteiro original que utilizei):

1) Escolha um número máximo esperado para o numero aleatorio (MAX);
2) Procure o primeiro número PRIMO antes de: MAX / (3*3*3*3*3*2);
3) Parametro M = (PRIMO*3*3*3*3*3*2):
4) Parametro A = (PRIMO*3*2+1)
5) Definir o parametro C como 7.
6) Teste se:
6.1) A e 1 são congruentes em relação ao primo?
6.2) A e 1 são congruentes em relação a 3?
6.3) A e 1 são congruentes em relação a 2?

Vamos então a um exemplo prático.

Digamos que desejamos gerar números entre 0 e 9999, sendo que os números só devem se repetir quando não houver mais inteiros “sorteados”.

Seguindo os passos do roteiro acima temos:

1) MAX = 9999;
2) 9999 / 486 ~= 20. Nesse caso, PRIMO = 19;
3) Parametro M = (19*486) = 9234:
4) Parametro A = (19*3*2+1) = 115
5) Definir o parametro C como 7.
6) Teste se:
6.1) A e 1 são congruentes em relação ao primo? 115 mod 19 = 1.
6.2) A e 1 são congruentes em relação a 3? 115 mod 3 = 1.
6.3) A e 1 são congruentes em relação a 2? 115 mod 2 = 1.

Em sequencia, supondo-se a existencia da função LCG(a, c, m, semente_inicial), vejamos os primeiros numeros gerados com base na semente “1”:

LCG(115, 7, 9234, 1) = {122, 4803, 7546, 9035, 4824, 727, 506, 2793, 7246, 2237…}

Para atestar se o período alcançado pelos parametros calculados foi o mais longo possível, desenvolvi um pequeno programa que gera números aleatórios com base na LCG até que um número já sorteado apareça novamente (para períodos curtos, como o do exemplo, pode-se verificar isso até mesmo no MS-Excel).

Em todos os testes que fiz da LCG acima, o período foi de 9234 números até que ocorra repetição (isto é, período = m) , servindo assim para a finalidade proposta.

Geradores de números pseudo-aleatórios

O gerador de números pseudo-aleatórios mais usado no universo digital é o famoso método da congruencia linear, descrito no livro Numerical Recipes e adotado em diversas linguagens (dentre elas C, Delphi etc). Isso se deve, é claro, a sua imensa simplicidade de implementação:


X[n+1] = (a * X[n] + c) mod m
Onde:
a = 1664525
c = 1013904223
m = 2^32


Porém, tal gerador é comprovadamente ineficiente para criptografia ou simulações estatísticas, notadamente quando se precisa aplicar o método de Monte Carlo.

Existem diversos geradores disponíveis no mercado, dentre eles destaca-se o Mersenne Twister. Porém, embora globalmente aceito como o de melhor custo computacional versus beneficio estatístico disponível atualmente, é bastante complicado de se implementar para a maioria dos pobres mortais.

Uma alternativa interessante que descobri alguns anos atrás é um automato celular chamado pelo seu descobridor (Stephen Wolfram) como Regra 30.

Wolfram fez um verdadeiro estudo sobre esse automato, mas especificamente sobre a capacidade de ser usado como um gerador de bits pseudo-aleatórios, passando por diversos testes estatísticos.

O matemático propõe o algorítmo, inclusive, como fortemente apto a ser utilizado em criptografia.

Controvérsias a parte, a verdade é que a teoria por trás da Regra 30 é bastante simples. O algoritmo consiste em aplicar algumas operações lógicas entre os bits do número processado (algo muito parecido ao método LFSR), tal como a seguir:


bit[n]´ = bit[n-1] xor (bit[n] or bit[n+1])


Podemos implementar facilmente tal algoritmo em linguagem C usando três inteiros representando os bits envolvidos no método, e um quarto que guardará o resultado da operação aplicado a todos os bits, como a seguir:


int rule30rnd() {
static unsigned int a = 0x00FF00FF; // bit[n-1]
static unsigned int b = 0x9ABCDEF0; // bit[n]
static unsigned int c = 0xFF00FF00; // bit[n+1]
unsigned int d;
d = a ^ (b | c);
a = (d >> 1) | (d << 31); // bit[n-1] = result rotate right
b = d; // bit[n] = result bits
c = (d << 1) | (d >> 31); // bit[n+1] = result rotate left
return d;
}


No código acima tratamos o problema das bordas – comum nos automatos estudados pelo Wolfram, que teoricamente crescem infinitamente para os lados, mas fisicamente são limitados por uma memória finita – com rotações nos dois inteiros (bit[n-1] e bit[n+1]).

Para modificar a semente de geração, basta alterar o valor de qualquer um dos três inteiros principais.

É importante notar, porém, que a qualidade de geração é bastante influenciada pelos valores inteiros escolhidos como iniciais.

Nesse contexto, Wolfram propõe a escolha de valores que sejam o mais aleatórios possíveis como semente, além de sempre fazer alguns ciclos de geração (de tamanho variável, descartando o resultado) no inicio do programa, antes de utilizar de fato os valores gerados.

Loterias: crenças e coincidências

As coincidências são um lugar comum no cotidiano das pessoas, até bem mais do que elas próprias imaginam. Algumas são bem corriqueiras, como chegar ao ponto de ônibus no momento em que está chegando a condução certa ou ligar o rádio e estar tocando a musica que se gosta. Porém, existem outras que nos fazem realmente pensar, como – embora seja uma lenda urbana – o caso da mãe que ganhou na loteria jogando as datas de aniversários dos filhos.

O que realmente faz algumas coincidências extraordinárias e outras não é o nosso desejo intenso de explicar as primeiras, na crença de que algo especial aconteceu numa espécie de conspiração do universo para que as coisas tenham acontecido da forma como se deram.

Sagan dedicou, em seu livro “O mundo assombrado por demônios”, um capítulo inteiro sobre isso. Ele acreditava que o cérebro humano é viciado em significados, isto é, faz uma busca incessante por padrões escondidos debaixo da astronômica massa de dados sensoriais que processa a todo o momento.

Segundo Sagan, “… as fases de sorte, longe de ser extraordinárias, são esperadas até para eventos aleatórios. O que seria surpreendente é a ausência dessas fases”.

Vamos imaginar o seguinte exemplo proposto por Sagan: suponha que você jogue uma moeda dez vezes e no final obtenha quatro séries de caras seguidas, qual seria sua reação? Acreditaria estar exercendo algum controle extra-sensorial sobre a moeda? Ou simplesmente “estávamos numa fase de caras”?

Pode-se até argumentar que “parece regular demais para ser obra do acaso”, mas se levar em consideração que se estava jogando a moeda antes e que, certamente, haverá outras rodadas futuras após ter obtido essa serie específica de caras, percebemos que na verdade ela se inseria numa seqüência maior e bem menos interessante.

Quando é permitido prestar atenção a alguns resultados e ignorar outros, sempre se é capaz de provar que há algo de excepcional seja no que for. Pode-se, inclusive, até dizer tratar-se de “uma fase de sorte”. Essa é uma das inúmeras falácias relacionadas à argumentação de fatos.

Em seu artigo “O poder da coincidência” (versão complementar), Novella argumenta que “o que a maior parte das pessoas não sabe ou não querem acreditar é que coincidências, mesmos as notáveis, não são assim tão surpreendentes. Na verdade a maioria são ocorrências inevitáveis sem nenhum significado especial”.

Para ele, basicamente quatro fatores influenciam para essa interpretação errônea das coincidências pelas pessoas:

1. Temos uma pobre compreensão inata de probabilidade;
2. Acreditamos que todos os efeitos devem ter causas deliberadas;
3. Não compreendemos as leis que regem os números verdadeiramente grandes;
4. Sucumbimos facilmente à validação seletiva — a tendência de lembrar somente correlações positivas e esquecer um número muito maior de insucessos.

No que tange o primeiro fator, não é difícil compreender por que a maioria das pessoas tem dificuldades em probabilidades, já que essa disciplina não é comum nos currículos escolares básicos.

Moran & Lopes , no artigo “A Estatística e a Probabilidade Através das Atividades Propostas em Alguns Livros Didáticos Brasileiros Recomendados para o Ensino Fundamental”, discutem exatamente a importância deste tema no currículo escolar.

Para esses autores a estatística é algo indissociável do ensino das probabilidades, e que mesmo a primeira não aparece como estratégia da solução de problemas de pesquisa, como deveria ser trabalhada em todos os níveis de ensino.

Dessa forma argumenta-se que: “… a concepção de estatística que permeia os livros da 1ª à 8ª série é de um fazer empobrecido, por não inserir a construção dos conceitos estatísticos e probabilísticos na metodologia da resolução de problemas”.

Dentre as várias questões apontadas no artigo, destaca-se o fato de que nas séries iniciais sejam introduzidas algumas atividades que dão a entender que a estatística fornece o problema propriamente dito, confundindo-se aí o problema com sua solução.

Além disso, até a porcentagem, a qual é uma ferramenta matemática necessária à construção do conceito de probabilidade, gravemente não aparece em nenhum momento vinculado ao raciocínio estatístico, sendo que mesmo a palavra “probabilidade” é substituída insistentemente por “chance” quando a idéia é inserida nos livros escolares, dificultando ainda mais ao aluno a aproximar-se do pensamento cientifico da disciplina.

O artigo propõe que “o ensino da estocástica no Brasil seja ampliado rapidamente”, como forma de solucionar a questão, e, assim, “possa-se formar, de fato, cidadãos mais aptos a tomadas de decisão, especialmente em situações envolvendo a presença do acaso”.

Segundo os autores a maior inclusão do tema no currículo escolar básico traria diversas vantagens, dentre elas:

“… um maior interesse do aluno para a resolução de problemas relacionados com o mundo real e com outras matérias do currículo; influência positiva na tomada de decisões destes quando dispõem somente de dados afetados pela incerteza; facilidade na análise crítica da informação recebida através, por exemplo, dos meios de comunicação; um tipo de compreensão que proporciona uma filosofia do azar, de grande repercussão para o entendimento do mundo atual“.

De fato, compreender probabilidade pode dar o poder necessário para entender melhor o significado, ou a falta de significado, de muitos eventos do dia a dia. Para Novella:

“… uma compreensão precária de probabilidade e estatística, comum em nossa sociedade, leva as pessoas a se surpreenderem mais do que deveriam quando confrontadas com coincidências, por conseguinte um salto fácil em direção a uma explicação metafísica”.

Esse argumento passa também pelo segundo fator apontado por ele, onde se atribui explicações miraculosas a todo tipo de fato bizarro, porém plenamente plausível probabilisticamente, na crença de que exista “algum motivo especial” por trás do evento.

Uma forma de driblar essa crença é compreendendo melhor a “lei dos números grandes”, o terceiro fator de Novella. Essa lei estatística declara que numa amostra grande o suficiente, mesmo um evento extremamente improvável torna-se provável e, dessa forma, qualquer coisa, por menor que sejam suas chances de acontecer, em algum momento ocorrerá.

Utilizemo-nos de um exemplo hipotético para ilustrar esse fato: numa pesquisa feita pela Catho – uma empresa de recolocação profissional – afirmava-se que apenas 1% dos pedidos de aumento feitos ao chefe é realmente atendido, sendo assim inútil tal procedimento. Bem, apoiando-se na lei dos números grandes, bastaria então que o colaborador faça o pedido uma vez por dia para, em um ano, ter, em média, pelo menos duas delas atendidas, e se topar-se tentar diariamente durante cinco anos seguidos, pelo menos em 12 delas ter-se-ia sucesso.

Mesmo tratando-se, evidentemente, de uma estratégia irreal e cômica, o exemplo demonstra como mesmo um percentual pequeno se torna significante num montante de tentativas maior.

No mundo real um exemplo a ser citado é o interessante caso do coronel brasileiro Oscar Rocha da Silva Filho que, em 2003, sobreviveu a uma queda de 3,5 mil metros. Oscar pertence ao Esquadrão Aéreo-Terrestre de Salvamento (Pára-Sar), lotado no Rio de Janeiro, grupo de elite da Força Aérea Brasileira, e na época afirmou que o pára-quedas principal e o reserva falharam. No acidente acabou por cair em um campo, em cima de uma árvore, sofrendo apenas uma fratura no nariz, duas vértebras e o esterno quebrado. Quais as chances de alguém sobreviver a uma queda dessas? Pequenas, quase improváveis, poder-se-ia dizer.

Porém, o caso do sortudo coronel não é único no mundo. Michael Holmes, um instrutor britânico de pára-quedismo acrobático, teve o mesmo destino no final de 2006. Ele sobreviveu com apenas uma fratura no tornozelo a um salto de 3,6 mil metros na Nova Zelândia, quando seus dois pára-quedas falharam, caindo sobre uma plantação de amoras.

A lição que se tem desses fatos é que, dentro dos inumeráveis saltos de pára-quedas que já ocorreram no mundo, sempre encontraremos casos surpreendentes como esse, e isso se deve diretamente à lei dos números grandes.

O último fator de Novella é de longe o mais perigoso, pois trata de nossa tendência, muitas vezes inconsciente, de selecionar fatos felizes em detrimento de outros de menor sorte.

Essa característica pode ser explicada pela forma que nossa memória foi moldada pela natureza em seu processo evolutivo. O homem, de certa forma, é programado para procurar padrões e conexões por toda parte, e isso acaba muitas vezes por atrapalhar. Para Novella, “… na tentativa de encontrar padrão em tudo, nosso cérebro nos leva continuamente a sugerir explicações e até mesmo invocar forças estranhas — tais como poderes psíquicos — que não existem”.

É bem conhecido da medicina o fato de muitas pessoas que ficaram surdas atestarem ainda ouvir vozes, cânticos ou música “vindos do além” (vide Ludwig van Beethoven), bem como aqueles que perderam membros afirmarem sentir a presença “espiritual” destes ainda ligados a seus corpos. Isso tudo é produzido por nosso cérebro, que teima em procurar padrões auditivos ou sensoriais advindos de membros defeituosos ou ausentes.

Quando nossa propensão natural à validação seletiva é levada em conta, unindo-se ao nosso desejo em acreditar em algo ligado ao destino, o verdadeiro poder ilusório da coincidência é percebido.

Por fim, Henri Poincaré, matemático conhecido por sua posição extremamente intuísta nas ciências exatas, nos dá a seguinte explicação do motivo desse comportamento humano: “Nós também sabemos o quanto a verdade é muitas vezes cruel, e nos perguntamos se a ilusão não é mais consoladora”.

Hubblecast

Hubblecast é uma iniciativa da ESA para divulgação dos feitos da missão Hubble.

Liderado pelo sempre animado Dr. J (Joe Liske), os episódios são distribuidos nos mais variados formatos de vídeo, do velho .MOV, passando pelo .MPEG até HD – high definition.

Trata-se na verdade de uma coleção de curtas que versam sobre os mais variados temas astronômicos, ligados diretamente a descobertas obtidas graças as potentes lentes do telescópio Hubble.

No primeiro episódio, Dr. J nos conta sobre a descoberta intrigante de uma “Galáxia Cometa”:

Download do vídeo – Download da legenda em portugues

Já no segundo episódio tomamos conhecimento sobre galáxias barradas (além do fato da Via Láctea possivelmente ser uma delas) e buracos negros supermassivos:

Download do Vídeo – Download da legenda em portugues

Aconselho a todos os interessados em astronomia a assistirem tais vídeos, pois cobrem o tema de forma simples e interessante.

 

 

Loterias: pseudo teorias e seus problemas

É interessante como até hoje se vê na internet pessoas utilizando o velho esquema de dezenas atrasadas/adiantadas para montar seus jogos e testar sua sorte nas loterias.

Para quem não sabe, tal esquema consiste basicamente em contar em determinado período de tempo quantas vezes cada dezena da loteria em questão saiu, montando uma tabela ao estilo “dezena versus quantidade de sorteios que apareceu”. No passo seguinte estas são classificadas em dezenas “quentes” (ou sortudas, para aquelas que saíram mais vezes), e “frias” (ou azaradas, aquelas que saíram poucas vezes).

O uso do esquema varia. Enquanto alguns jogam somente nas dezenas quentes alegando estas estarem no momento com “sorte”, outros fazem o inverso: evitam as “mais” quentes sob o pretexto que estas já tiveram sorte por tempo de mais, portanto com grande chance desta “onda” mudar.

A verdade é que esse esquema é uma das falácias probabilisticas mais conhecidas em jogos de azar, sendo baseada, mais especificamente, na famosa lei das médias (e um pouco também na ilusão de agrupamento, que nos faz ver padrões onde não existem).

Para demonstrar que o que diz a lei das médias está errado, basta imaginar um jogo de cara ou coroa: o fato de sair duas caras consecutivas não garante que a próxima sairá coroa (como prega a lei), já que você pode muito bem estar na realidade no início de uma sequencia de várias caras.

Na verdade, não dá para dizer nem quando a sequencia de caras irá terminar, já que estatisticamente todas as sequencias devem sair em algum momento e em igual proporção. Isto é: três sequencias de coroas sairá em uma determinado intervalo de tempo mais ou menos na mesma proporção que três sequencias de caras.

Existe até uma fórmula estatística que calcula a quantidade de dezenas que estarão atrasadas ou adiantadas ao longo do tempo. O problema é que não dá pra dizer “qual” sequencia (ou dezena) atingirá “qual” tamanho em determinado instante do tempo.

Este, inclusive, é um perfeito exemplo de aplicação do modelo matemático de passeio aleatório (que por sua vez é usado no estudo do movimento browniano) e da eterna busca para saber “quando” o movimento neste passeio terá sua direção modificada.

O modelo de passeio aleatório mais simples é o caminhar do bêbado: neste temos uma linha imaginária onde um individuo alcoolizado deve seguir percorrendo indefinidamente. A cada passo de sua caminhada o bêbado decide (com igual probabilidade) se dá um passo para a direita ou para esquerda (ele não anda em linha reta), tudo em relação a tal linha, afastando-se ou reaproximando-se desta a cada momento.

O problema consiste em, uma vez iniciada a caminhada, identificar quanto tempo demorará para o bêbado voltar a cruzar a linha inicial (ou então, pelo menos, quando este passará a um padrão de aproximação ou distanciamento desta).

O problema do passeio aleatório é abordado também em antigas estratégias de estudo do movimento da bolsa de valores, tendo o princípio de onda de Elliott (que não tem bases científicas para apoiá-la, diga-se de passagem) seu maior exemplo.

Uma dica que dou para quem quer tentar a sorte em loterias da Caixa é ler meus artigos sobre MegaSena e LotoFácil, que dão dicas simples e estatisticamente confiáveis que podem, pelo menos, ajudar na escolha de suas apostas.

E para os loucos por bits e bytes, aconselho também a dar uma olhada nesse meu programa, que usa algumas das idéias contidas nos artigos.

 

IPVA, destino: buraco negro

O IPVA é um pesado imposto anual brasileiro que afeta todos os proprietários de automotores do país. A transferência de tal montante para o Estado frequentemente frustra o contribuinte, principalmente quando este último não vê a contrapartida de tal tributo.

Para entender o motivo dessa infame caixa-preta que envolve a alocação dos recursos do IPVA no país, precisamos conhecer as origens de tal imposto. Dessa forma, segundo SILVA (2007) :

“O Decreto-Lei n.º 999, de 21 de outubro de 1969 instituiu a Taxa Rodoviária Única, a qual incidia sobre o registro e licenciamento de veículos, considerando que a Constituição vigente à época do decreto permitia à União, aos Estados e Municípios, cobrarem taxas remuneratícias do seu poder de política ou pela utilização de serviços públicos utilizados ou postos à disposição do contribuinte. Consideravam, ainda, que a remuneração por esses serviços públicos desvirtuava o preceito constitucional de que o serviço fosse perfeitamente específico e divisível. Como forma de subsidiar a manutenção e conservação das estradas, a Taxa Rodoviária Única foi criada visando à abolição das desigualdades de valores e critérios de cobrança observada nas diversas unidades da Federação, o que levava a um tratamento discriminatório, ensejando a evasões de receita….”

Em seqüência, SILVA relata a estreita relação entre o IPVA e o antigo TRU, com a implementação do artifício que desvincula a contra prestação de serviço que o TRU anteriormente exigia:

“O IPVA, de competência dos Estados e do Distrito Federal, sucedeu a antiga Taxa Rodoviária Única, com o advento da Constituição Federal de 1988. Assim, a cobrança acabou mudando de taxa para imposto por questão de mera técnica de linguagem quanto à exigência dela sobre todos os veículos automotores. Como imposto, o IPVA ficou livre da vinculação direta a uma contraprestação, desvirtuando os reais objetivos da cobrança estatal. Com o fim da TRU, as estradas ficaram sem subsídio garantido, pois na condição de taxa, a contraprestação deve ser direta.”

A mudança de nomenclatura desse tributo – tornando-a assim um imposto – possibilitou aos estados e municípios brasileiros alocarem tal recurso da forma que bem entenderem.

Como pode ser observado em todas as cidades brasileiras, o exercício desmedido dessa liberdade trouxe uma conseqüência indesejada: a contínua queda do nível de investimento que é feito anualmente em estradas no Brasil, já que o Estado, por desobrigar-se de destinar os recursos do IPVA para a finalidade original de tal tributo, acaba por aplicá-lo em outras áreas.

ARRECADAÇÃO

Embora a aplicação dos recursos do IPVA em benfeitorias para o contribuinte seja de quase nenhuma transparência, assim não o é o montante arrecadado anualmente, o qual pode ser facilmente obtido nos órgãos governamentais.

Dessa forma, segundo os dados do próprio governo, a arrecadação obtida pelo estado do Ceará (objeto desse estudo) com o IPVA é da ordem de centenas de milhões (R$165M em 2006), tendo um mínimo de 10% de crescimento anual.

Como o custo por m2 de asfalto gira em torno de R$30, linearmente, tal imposto poderia arcar sozinho com cerca de 5 km2 de asfalto anuais nesse estado.

REDE RODOVIÁRIA

A estrutura da rede rodoviária dos estados brasileiros também é uma informação de acesso público, facilmente obtido em diversos sites. Inúmeros estudos sobre esse assunto podem também ser colhidos na internet.

Dessa forma, observa-se que o tamanho da rede rodoviária do estado cearense corresponde a cerca de 52 mil km que, convertido para km2 (admitindo-se uma hipotética largura média de 10 metros da rodovia), chega-e ao número de 523km2. Porém, como apenas 12% da malha viária desse estado é pavimentada, ficamos com um total de 62km2 a re-pavimentar a cada 10 anos (que é a duração média do asfalto).

Sabendo-se que o estado poderia re-pavimentar 5km2 ao ano, teriamos toda a malha viária do estado refeita a cada 12 anos (ou 3 mandatos, que é a unidade oficial de tempo dos políticos brasileiros), observa-se claramente que os recursos provindos do IPVA, sozinho (sem considerar os gordos recursos advindos do imposto sobre combústiveis), mais do que sobra para arcar com os custos de reconstrução das estradas desse estado ao longo dos anos, se este fosse bem aplicado.

CONCLUSÃO

Fica então a seguinte questão: se mesmo uma investigação de cunho bastante básico como esta já demonstra indícios do potencial de investimento em infra-estrutura que o estado analisado possui, onde está de fato a barreira que impede tal decisão – tão necessária ao futuro econômico deste – de ser tomada?

REFERENCIAS:

SILVA, Márcia S. A inconstitucionalidade dos pedágios.

Inconstitucionalidades da Contribuição de Intervenção no Domínio Econômico.

SEFAZ. Arrecadação IPVA BRASIL, 2001-2006.

Jornal O Povo. Previsão arrecadação IPVA 2008 no Ceará.

WIKIPEDIA. Dados geográficos dos estados brasileiros.

Estatística Ceará

Portal 180 graus. Preço do asfalto no Piauí.

FIEC. Rede rodoviária do Ceará.

Pesquisa aponta principais gargalos da malha rodoviária brasileira, com vias em estado crítico

USP. Largura média das rodovias no Brasil.

FREAKONOMICS. Por que as leis bem-intencionadas saem pela culatra?

Universo computacional

Nesse final de semana estava a assistir um documentário da History Channel sobre como surgiu a Teoria do Big Bang, quando comecei a pensar nas inúmeras pessoas envolvidas nesse empreendimento ao longo dos séculos e como estas utilizaram-se quase que exclusivamente da matemática como principal ferramenta de explicação da natureza.

Não me é grande surpresa o uso da matemática para esse fim, já que julga-se desde eras imemoriais ser esta a linguagem universal (ou de um “Deus Geômetra Onipotente para quem o mundo é um imenso problema matemático“, como bem diria Leibniz). Porém, também não é surpresa todas as teorias derivadas desta serem falhas em algum ponto. Ora, ao contrário do que mundanamente se pensa, não é a matemática imperfeita como nos sugeriu Godel?

O teorema da incompletude de Godel nos diz que “a matemática não é fechada, isto é, é incompleta“. Assim, “sempre existirão questões e problemas que NÃO podem ser respondidas pelos axiomas matemáticos EMBORA estes problemas possam estar bem definidos nesta matemática. Além disso, mesmo que se introduzisse novos axiomas para resolver estes problemas, SEMPRE existirão novos problemas que não serão respondidos por ela“.

Isso nos leva à crer que, assim como acontece na física, na matemática precisamos de teorias novas cada vez mais precisas e próximas da realidade as quais possam nos trazer respostas à velhos problemas bem como novas questões a serem respondidas.

Na física inclusive, mais precisamente na mecânica quântica, é bastante comum utilizarem artifícios matemáticos como a chamada renormalização para fugir de alguns resultados indesejados (infinitos, divisões por zero etc). Sem falar de alguns “relaxamentos” das regras matemáticas que aqui acolá se encontra menção em trabalhos importantes, inclusive de Einstein como acusam alguns.

Nesse contexto, o livro A New Kind of Science de Stephen Wolfram nos propõe que nossa matemática mostra-se assim incompleta por ser um simples reflexo e resultado de estruturas mais básicas. Ele sugere que nossos axiomas matemáticos se apóiam em bases lógicas, isto é, podem ser representadas e reconstruídas através de regras simples em autômatos celulares (vide capítulo Systems Based on Numbers na supracitada obra).

Em sua exposição, Wolfram nos instiga com a idéia de que informações aparentemente aleatórias, como o valor de PI e os números primos, podem ser explicadas e calculadas em termos de interações lógicas.

Nesse prisma, não é difícil visualizar que interações lógicas podem simular nossa matemática, já que são através delas que nossos computadores atuais fazem cálculos, bem como entender a dificuldade da matemática em representar operações lógicas como AND, OR e NOT (“e”, “ou” e “não”) em termos de seus axiomas naturais.

Assim, podemos crer ser plausível a idéia de Wolfram de que a matemática esteja contida dentro dos axiomas da lógica, tendo as CAs (tão conhecidas na ciência da computação) como sua representação gráfica tal qual os gráficos cartesianos os são para a matemática.

Nesse contexto, não se conseguiria com a matemática expressar tudo que poderia-se fazer com a lógica binária. E não é por menos, já que na ciência da computação sabe-se que linguagens de um nivel maior não podem modelar corretamente linguagens de nível menor (que são, inevitavelmente, mais expressivas que as primeiras).

Dessa forma, por exemplo, não se consegue transpor um programa escrito nativamente em Assembly (com binário oriundo dessa linguagem de baixo nível) para uma linguagem de alto nível, como C ou Java. Nesse processo sempre se perde algo que a linguagem destino não consegue expressar.

Este é o motivo, na ciência da computação, da grande dificuldade na engenharia reversa de código binário: embora sempre seja possível “descompilar” programas binários que sejam oriundos de código de alto nível, se o binário contiver partes (ou totalmente) escritos nativamente em Assembly estas não são convertidas. Talvez até esta seja também o motivo da dificuldade da engenharia genética em “hackear” o DNA: por ser código nativamente escrito em uma linguagem de baixo nível (como descrito nesse ótimo artigo), perde-se sua representação direta em uma abstração maior.

Mas, voltando-se ao tema do universo computacional, toda essa proposta do livro sobre a possibilidade de simularmos situações complexas através de simples regras de automatos celulares e que nosso mundo talvez seja governado por elas reacende velhas questões, como por exemplo o eterno debate do “determinísmo Laplaciano x indeterminismo quântico“.

Podemos imaginar que, caso vivamos em um mundo determinista, o simples fato de estarmos imersos nesse “sistema fechado” nos impede de modelarmos estados futuros deste, pois para conseguirmos tal possibilidade precisaríamos:

1. não interagir com o sistema, a fim de evitar reações caóticas oriundas dessa interação (o que está de acordo com a visão da mecânica quântica de que o observador, pelo simples fato de observar, modifica o estado do objeto observado);
2. termos um simulador que funcione mais rápido que o próprio universo, a fim de podermos simular o instante inicial, passar pelo atual e chegar ao instante futuro em um tempo que possa ser humanamente mensurável.

Por estarmos imersos no universo, e não podermos fisicamente fazer um programa rodar mais rápido que a própria máquina que o executa, nos faz chegar à conclusão que nos é impossível visualizar estados futuros por meio de uma simulação perfeita.

Mas essa conclusão não exclui simulações imperfeitas e incompletas, como as que encontramos em todas as nossas teorias da física antiga e atual.

Mundo probabilístico

Imagine se cada decisão que você fizesse em sua vida fosse governada pela sorte, mais especificamente por um dado. Essa é a proposta do livro “The Dice Man“, do autor americano George Cockcroft.

Escrito na década de 70, a obra conta a estória de Luke Rhinehart, um fictício psiquiatra que, após deixar um dado ditar uma decisão sua depois de uma noitada de muito poker, passou a ter progressivamente uma vida aleatória, cada vez mais governada pelos dados.

“Utilizar a sorte para modificar o destino de sua vida é a forma mais extrema de jogo de azar” (Luke Rhinehart)

Rhinehart, para cada simples ação em sua vida, deixava sob o encargo de um dado decidir entre seis opções previamente definidas por ele para aquela ação. Para compor essa lista, ele seguia cinco regras básicas:

1. Não incluia nenhuma opção a qual não gostaria de realizar;

2. Lembrava-se sempre que uma aparente opção errada escolhida pelo dado poderia resultar num grande ganho no futuro;

3. Sempre incluia uma ação drástica como opção, por que, na vida, ações assim podem simplesmente mudar tudo;

4. No inicio de cada dia deixava o dado decidir se deve ou não usá-lo no restante do dia;

5. E, periodicamente ignorava, deliberadamente, todas as quatro regras anteriores.

Analisando sob o ponto de vista matemático, o estilo de vida escolhida por  Rhinehart é tão provável quanto qualquer outro modo de vida que escolhermos ou inventarmos, por mais estranha que possa parecer. Ainda mais se considerarmos que as decisões humanas (e da natureza, vide a genética que apoia-se em mutações aleatórias) estão mais próximas de escolhas ao acaso do que qualquer tipo de embasamento racional (vide nossos políticos que refletem, sob o ponto de vista da amostragem, nosso povo).

De fato, o universo parece bastante aleatório em pequena escala (como demonstrado pela Mecânica Quantica), e mais determinístico em grandes escalas (vide as teorias relativisticas), e, nós humanos, encontramo-nos bem no meio termo disso. Ou, pelo menos, é assim que nos parece.

O pesquisador britânico Stephen Wolfram, em seu livro A New Kind of Science, relata que o mundo natural consegue realizar computações somente até um máximo nível de poder computacional, e que, embora muitos sistemas atinjam esse nível na natureza, há uma gama imensa de sistemas aparentemente simples com comportamento computacional complexo e vice-versa. Além disso sistemas computacionalmente equivalentes não conseguem mimetizar eficientemente um ao outro (ou sistemas mais complexos).

Assim, para que dois sistemas computacionalmente equivalentes (por exemplo, PCs de configuração idêntica) consigam mimetizar as atividades intrisecas do funcionamento um do outro implicará: ou na necessária simplificação do modelo desse sistema (para que seja possível uma simulação parcial em tempo real); ou no relaxamento do fator tempo para que seja possível a simulação total mas em lentíssima execução. Em qualquer das situações, perde-se a visão real do sistema original, impossibilitando sua compreensão total pelo outro.

Wolfram argumenta, em certo ponto do livro, que enxergamos como aleatório qualquer coisa que seja de igual ou maior complexidade que nós mesmos. Esses sistemas nos parecem aleatórios por que são, pelo menos, equivalentes a nossa própria complexidade.

Levando isso para a vida aleatória de Rhinehart, embora esta nos pareça assim sem sentido, qualquer vida também nos pareceria se considerarmos a possibilidade de que o conjunto das inúmeraveis situações que vivemos no decorrer dos anos forme um sistema pelo menos de igual complexidade a nós mesmos (já que esta ter uma menor complexidade é, obviamente, uma impossibilidade). Assim, nos resta apenas analisá-los sob o prisma de modelos imprecisos de vidas, na tentativa vã de mimetizar tais sistemas.

Se a vida, como um conjunto de inúmeraveis escolhas, é assim tão computacionalmente intratável por parte de nós, como saber se nossas decisões estão, de fato, nos rendendo pontos para uma melhor situação futura?

Será que, na soma final, fazer escolhas aleatórias nos trará a mesma taxa de perdas/ganhos que decisões racionais?

A teoria da computação nos mostra que o aumento linear do número de escolhas leva a um crescimento exponencial do número de possibilidades finais. Isso, em última instância, leva à indecidibilidade, na qual reside antigas questões como o Problema do caixeiro viajante de onde podemos apenas obter soluções boas, mas não a garantia da ótima solução.

Assim, talvez, decisões racionais (como uma forma de algoritmo de escolha) nos traga soluções que consideramos pelo menos satisfatórias.

Com isso, parece que na vida abrimos mão da possibilidade estatística real da ótima solução (que pode ser simplesmente descartada no rol de opções de nosso algorítmo pessoal de escolha), em prol de alcançarmos pelo menos o satisfatório.

No fim, trocamos o ganho máximo duvidoso por um ganho menor, porém certo.