quarta-feira, 28 de julho de 2010

Furstenberg e a infinitude dos números primos


Para entender esse texto, o leitor deve estar familiarizado com o conceito de topologia.

Frustenberd é um matemático israelense muito respeitado pelos resultados que obteve na teoria de probabilidade e teoria ergódica. Ele ficou famoso logo no começo da carreira ao publicar, em 1955, quando ele era apenas um aluno de graduação, uma demonstração da infinitude dos primos usando apenas a definição de topologia e algumas propriedades de sequências infinitas de números inteiros.

Essa demonstração ficou famosa pois ela está bem longe das demonstrações rotineiras da área de topologia: trata-se de uma técnica topológica aplicada à teoria dos números! Por isso mesmo é considerada muito estranha e fascinante. Inclusive ela está listada entre outras 6 demonstrações da infinitude dos números primos que aparece no livro Proofs from THE BOOK.

Vou começar definindo uma topologia sobre o conjunto dos números inteiros e então, usamos as propriedades dos abertos dessa topologia para mostrar que existem infinitos números primos.

Uma topologia em Z


Dados dois inteiros a,b, com a positivo, considere o conjunto:


N_{a,b} = \{an + b;\ n \in \mathbb{Z}\}



Diremos que um subconjunto A de Z é aberto se, qualquer que seja a em A, existe b inteiro positivo, que depende de a, tal que, Na,b é subconjunto de A.

Não é difícil demonstrar que de fato definimos uma topologia sobre Z. Convido o leitor a verificar esse fato.

Observe que os abertos da topologia de Z possuem as seguintes propriedades:
  1. Se A é aberto e não vazio, então A é infinito.
  2. Cada Na,b, por definição, é aberto. Também é fechado, já que é complementar de um aberto. Veja:

\mathbb{Z} \backslash N_{a,b} = \bigcup_{i = 1}^{a-1} N_{a,b+i}


Como todo número inteiro difernet de -1 e 1 pode ser dividido em duas classes, a dos números primos e a classe dos números compostos (isto é, números que podem ser fatorados em números primos), temos a seguinte igualdade:

\mathbb{Z} \backslash \{-1, 1\} = \bigcup_{p \in P} N_{p,0}


Suponha, por absurdo, que exista apenas um número finito de números primos. Então temos que o lado esquerdo da igualdade acima é fechado. Logo {-1,1} é um conjunto aberto, o que contradiz a propriedade 1 da topologia de Z. Portanto, é um absurdo supor que o conjunto P dos números primos é finito.

A demonstração acaba aqui, mas espero que o interesse do leitor pela topologia e suas técnicas não. Para os interessados, vale a pena ler a página da Wikipédia sobre Topologia.

sexta-feira, 6 de novembro de 2009

Uma comparação ingênua entre algumas linguagens

Pretendo fazer uma pequena comparação entre algumas linguagens de programação, só para tentar mostrar um pouquinho de como cada uma tende a fazer com que o programador pense nas soluções de uma determinada maneira.

Para tal, vamos começar com uma pergunta bem simples: quem negaria que o conceito de somatório é importante em qualquer ciência exata? Se você não se lembra do somatório, dê uma olhada no artigo sobre somatório da Wikipédia.

Ou seja, essa é uma notação para a soma de f(1) + f(2) + ... + f(m). Um conceito bem simples que torna um monte de coisas bem mais práticas. Se tiver algum matemático lendo esse texto, certamente vai lembrar como o somatório é importante na hora de formalizar o conceito de série de números reais, de série de funções. Até mesmo a integral pode ser definida como um limite de somatórios. Falo da soma de Riemann.

Calma, esse texto não vai ser sobre matemática, não se desanimem. Vou começar com um objetivo bem simples: como levar naturalmente o conceito de somatório para a programação? Em linguagens como em C normalmente o somatório fica escondido dentro dos for's e dos while's, ou dá para fazer um hack usando ponteiros para funções, já em outras linguagens, como Python, Ruby e Scheme o somatório pode ser implementado de uma maneira bem elegante.

Mas antes de começar a implementar, vamos tentar formalizar um pouco o conceito de somatório. Podemos pensar no somatório como uma função que recebe dois números inteiros e uma função e então devolve o resultado da soma da função calculada em cada um dos números inteiros entre os dois inteiros dados.

Como isso ficaria em pseudocódigo? Para quem programou muito em C, eu acho que o código ficaria assim:

real soma(inteiro ini, inteiro fim, funcao f)
{
  inteiro i = ini;
  real r = 0;

  enquanto(i <= fim)
  {
    r = r + f(i)
    i = i + 1;
  }

  devolve r;
}

Mas, será que é fácil implementar algo assim em C? Não é complicado, mas tem uns probleminhas e limitações que ficarão bem óbvios, vejam:

float soma(int ini, int fim, float (*f)(float x))
{
  int i = ini;
  float r = 0;

  while(i <= fim) /* while é mais compreensível do que o for! */
  {
    r = r + f(i);
    i = i + 1;
  }

  return r;
}

Mas, tio, qualé a desse float (*f)(float x)?! - É um ponteiro para uma função! Sim, existe esse treco e dá tanta dor de cabeça quanto você pode imaginar. :D

O problema aqui é que em C funções são diferentes dos dados comuns. Outro problema chato é que a soma funciona para um tipo específico de função e tentar aumentar a flexibilidade só causaria mais dor de cabeça, mais náuseas - deixa eu explicar com termos "técnicos" - você teria que usar mais ponteiros. Sim, nada é tão complicado e estranho que não possa ser piorado.

Agora vamos dar uma olhada como essas coisas ficam em Python:

def soma(ini, fim, func):
  r = 0
  for i in range(ini, fim + 1):
    r = r + func(i)
  return r

Um amigo sugeriu que a maneira mais pythônica de fazer isso é:

def soma(ini, fim, func):
  return sum(func(i) for i in range(ini, fim+1))

A primeira coisa que notamos é como a sintaxe é simples e elegante e o código, menor! Mas acho que todo mundo já está cansado de saber como Python é uma linguagem linda e elegante. Vamos para a parte que importa.

Além disso a função func é tratada como um dado normal, que pode ser passada como parâmetro e depois pode ser chamada como função. Além disso, outra vantagem óbvia do Python é que não precisamos nos preocupar demais com o tipo de dado que a função fim devolve. Basta que ela devolva tipos de dados somáveis. Em C teríamos que fazer uma função de soma para funções que devolvem inteiros, depois outra que soma (concatena) strings ou algum outro tipo de dado em que seja possível definir uma soma.

Vamos ver como o mesmo código fica em Scheme?

(define (soma ini fim f)
  (if (> ini fim)
      0
      (+ (f ini) (soma (+ ini 1) fim f))))

Não é simples e bonito? O que eu achei mais interessante é que pela maneira com que o scheme foi desenvolvido, não há a necessidade coisas como o while e o for do C. E, ao contrário do que parece, esse código não acaba ficando lento, nem consome muita memória por ser uma recursão, pois, graças a uma técnica chamada de tail recursion, a função recursiva é executada como se fosse iterativa.

Também tem a beleza matemática: a função em Scheme segue exatamente a definição por indução finita! Eu convido o leitor para tentar definir a soma de n números inteiros usando indução para então se convencer que a maneira com que Scheme trabalha é realmente natural, pelo menos natural para os iniciados na linguagem matemática.

O que eu acho mais fantástico em Scheme é a possibilidade de criar funções durante o período de execução e sem a necessidade de ter que dar nomes para as funções. A vantagem de não precisar das nomes é que não precisamos dar nomes para funções que não merecem um nome! :D

Em Scheme a função soma poderia ser chamada assim:

(soma 1 10 (lambda (x) (* x (+ x 1))))

Isso aí chama a função soma passando uma função que recebe x e devolde x*(x + 1). Bem divertido, hein? Scheme coloca em evidência a criação de funções em tempo de execução e acho que essa é justamente a graça do Scheme. Tem muito mais coisas legais que podem ser feitas com essa brincadeira de criar funções em tempo de execução: dá para usar funções para representar pares ordenados e até listas encadeadas. Você consegue fazer isso? Aliás, acho que a maior graça das linguagens funcionais é a separação entre o conceito de "dado" e "função" acaba não fazendo mais muito sentido.

Bem, eu tinha citado Ruby como exemplo de linguagem interessante para escrever o somatório, então vamos lá. Mas antes, deixa eu só eu fazer um comentário: um monte de gente fala que Ruby é uma linguagem que suporta o paradigma funcional e isso ainda me parece meio estranho. Em Ruby, apesar de ser possível criar métodos em tempo de execução, as funções não são normalmente tratadas como dados. O código a seguir, por exemplo, não funciona:

def soma(ini, fim, func)
    r = 0
    for i in (ini...(fim + 1))
        r = r + func(i)
    end
end

Existe uma maneira de passar funções como parâmetros, mas eu acho feio e tão antipático quanto passar funções em C usando ponteiros. Matz, o criador do Ruby, diz ter um bom motivo para escolher como os blocos e closures funcionam em Ruby, mas não gostei muito não. Talvez eu não tenha entendido. :)

Acho que muita gente concorda comigo, tanto que há um incentivo para que funções não sejam passadas como argumentos, mas sim que blocos de procedimentos sejam criados em tempo de execução e que esses blocos sejam passados como argumentos. Na verdade passar blocos é passar uma função como argumento mas... Ahn, ficou confuso? O código fica assim:

def soma(ini, fim)
  r = 0
  for i in (ini...(fim + 1))
    r = r + yield(i)
  end
  r
end

Aqui yield representa o bloco passado como argumento e a maneira de chamar a função soma é:

soma(1, 10) do |i|
  func(i)
end

Mas eu desconfio que um rubysta faria a coisa confusa:

r = 0
(1...11).each do |i|
  r = r + i*i
end

Talvez essa brincadeira de passar blocos e criar funções em tempo de execução que seja a parte dita funcional de Ruby, mas ainda não sei. Se você tiver alguns exemplos de práticas bem funcionais em Ruby ou Python, por favor, participe nos comentários.

Algo muito parecido pode ser feito com Python, fica como exercício para o leitor implementar e se divertir. =)

Espero que essas comparações entre as linguagens tenham sido interessantes e tenha acrescentado algo na vida dos leitores. Quem sabe não consegui ajudar algum iniciante a escolher qual linguagem aprender primeiro ou até mesmo a um programador mais experiente a aprender a olhar outras linguagens para descobrir outras maneiras de resolver os problemas que aparecem no dia a dia.

Sintam-se livres para criticar o código acima, sugerir outras implementações ou até mesmo mostrar como vocês fariam o somatório na sua linguagem preferida. Ah! Fico devendo uma cerveja para o primeiro que mostrar a implementação do somatório em brainfuck!

domingo, 4 de outubro de 2009

Scheme - Uma linguagem folclórica


Scheme é um dialeto da famosíssima linguagem LISP, criada pelo cientista da computação John McCarthy, inspirada pela teoria matemática chamada de cálculo lambda. LISP também foi amplamente utilizada em pesquisas na área de inteligência artificial e foi provavelmente dela que surgiu o conceito de lista encadeada.

Eu não faço a menor idéia de como é hoje a linguagem LISP para quem quer trabalhar como programador, mas eu resolvi aprender essa linguagem devido ao fato dela ser uma linguagem que implementa muito bem o paradigma de programação funcional e como até hoje eu só aprendi um pouco de linguagens estruturadas, como a linguagem C, e um pouco de linguagens orientadas a objetos, como Python e Ruby, resolvi conhecer qualé a desse paradigma. Tá, eu sei que Python e Ruby são multi paradigma, mas elas dão ênfase na programação orientada a objetos!

Mas, voltando ao assunto original, como não quero trabalhar como programador, acho que posso me dar ao luxo de aprender qualquer tipo de linguagem, por menos prática que ela seja, apenas pelo prazer de aprender. E um outro motivo para eu querer aprender Scheme é que o Emacs usa elisp, mais um dos dialetos de LISP, e aparentemente tem uma galera querendo fazer o Emacs funcionar também com Scheme. Só que não faço a menor idéia de como é a compatibilidade do Scheme com Elisp...

Obviamente, Emacs também é uma excelente ferramenta para programar em Scheme! Ouvi falar que muita gente, mesmo os defensores da seita do VI, largam seus editores/IDEs/SOs favoritos apenas para programar Scheme no Emacs!

Aprendo Scheme por causa do Emacs, e aprendo Emacs por causa do Scheme, parece que caí num ciclo vicioso, mas não, eu queria aprender ambas as coisas desde o início.

Bem, deixa de enrolação, esse texto era sobre o que eu tenho feito feito para aprender Scheme, usando o Emacs e por que tudo isso é muito divertido. Então, como usar decentemente o Emacs para programar em Scheme?

A primeira coisa é decidir qual interpretador de Scheme usar, eu escolhi o Guile. O interpretador GNU Guile, não o personagem do street fighter!

Agora basta configurar o Emacs para usar o Guile, para tal, basta colocar no ~/.Emacs a seguinte linha:

(setq Scheme-program-name "guile") ;; Sonic boom!

Então basta recarregar o Emacs ou ir deixar o cursor no final da linha anterior e mandar o Emacs executar o código elisp: C-x C-e.

Agora vem a parte mais legal, que é a integração do Emacs com o interpretador guile, que funciona bem que é uma maravilha! Eu faço assim, sempre que vou estudar Scheme eu abro duas janelas no Emacs, deixo uma para escrever o código e outra com o interpretador Scheme.

Conforme eu programo, eu peço para o Emacs enviar uma linha ou um bloco de texto direto para o guile, assim eu consigo testar pedaços do programa em tempo de programação, sem ter que ficar montando um programa inteiro para só depois analisar o que um trecho de código faz.

Bem, pode ter sido confuso isso que descrevi acima, mas funciona assim, eu primeiro digito C-x C-3 para abrir uma janela nova, então vou na segunda janela, executando C-x o, nessa segunda janela eu executo o comando M-x run-Scheme e o interpretador fica rodando. Voltando para a primeira janela já podemos começar a programar, então vamos tentar digitar o mais clássicos programa de todos os tempos, um hello world em Scheme! Digite o seguinte código na janela para programar:

(display "Hello World!")

Agora, com o cursor no final da string, execute C-x C-e, e tcharam! o Emacs enviou a linha inteira para o interpretador, que, err, interpretou o código e mostrou a saída! Bem legal, hein?

E ainda dá para fazer mais, dá para enviar um bloco de texto inteiro para o interpretador, e é bem fácil, primeiro você escreve um código que tem mais de uma linha, então seleciona o bloco e em seguida você roda C-x C-r. Aqui vai um exemplo de código para você testar:

(define (factorial n)
  (if (= n 1)
    1
    (* n (factorial (- n 1)))))

(factorial 30)

Se você não se lembra como se seleciona um trecho de código usando Emacs isso é realmente muito simples, basta apertar M-x espace com o cursor onde você quer que o bloco comece, então movimente o cursor até o final do bloco e toda a região delimitada pela posição atual do cursor e a parte onde o início do bloco foi marcado. Agora é só executar C-c C-r.

Espero que as informações acima sirvam para quem está começando com Scheme e queira usar Emacs para programar e, caso você comece a estudar Scheme também, fale comigo e podemos aprender um pouco juntos, discutir umas idéias, trocar uns códigos e coisas assim. Se tiver curiosidade, deixe um comentário ou entre em contato.

sábado, 12 de setembro de 2009

RE: Your Brains

Alguém há algumas semanas me enviou um mp3, o nome do arquivo é Re: Your Brains. Não faço a menor ideia de quem foi que enviou e acabei deixando o mp3 aqui largado no meu Desktop com um monte de outros arquivos aleatórios.

Sem querer deixei o ponteiro do mouse em cima do arquivo e a música começou a tocar, primeiro eu me assustei, pois eu não tinha mandado meu computador fazer nada, mas logo em seguida percebi o que tinha acontecido e resolvi ouvir a música. E a música é bem legal, tanto pela sonoridade quanto, e principalmente, pela letra! Confiram:




RE: Your Brains

Heya Tom, it's Bob,
From the office down the hall.
It's good to see you buddy,
How've ya been?
Things have been okay for me,
Except that I'm a zombie now.
I really wish you'd let us in.
I think I speak for all of us when I say I understand
Why you folks might hesitate to submit to our demands,
But here's an FYI - you're all gonna die, screaming.

All we wanna do is eat your brains
Were not unreasonable,
I mean no-one's gonna eat your eyes
All we wanna do is eat your brains
Were at an impasse here,
Maybe we should compromise.
If you open up the door,
We'll all come inside and eat your brains.

I don't wanna nitpick Tom, but is this really your plan -
Spend your whole life locked inside a mall?
Maybe that's okay for now,
But someday you'll be out of food and guns,
And you'll have to make the call.
I'm not surprised to see you haven't thought it through enough -
You never had the head for all that 'bigger picture' stuff.
But Tom, that's what I do,
And I plan on eating you, slowly.

All we wanna do is eat your brains
Were not unreasonable,
I mean no-one's gonna eat your eyes
All we wanna do is eat your brains
Were at an impasse here
Maybe we should compromise
If you open up the door,
We'll all come inside and eat your brains

I'd like to help you Tom,
In any way I can.
I sure appreciate the way you're working with me.
I'm not a monster Tom - well, technically I am...I guess I am...

I've got another meeting Tom;
Maybe we could wrap it up.
I know we'll get to common ground somehow.
Meanwhile I'll report back to my colleagues,
Who are chewing on the doors.
I guess we'll table this for now.
I'm glad to see you take constructive criticism well
Thank you for your time, I know we're all busy as hell.
And we'll put this thing to bed,
When I bash your head open.

All we wanna do is eat your brains
Were not unreasonable,
I mean no-one's gonna eat your eyes
All we wanna do is eat your brains
Were at an impasse here
Maybe we should compromise
If you open up the door,
We'll all come inside and eat your brains

domingo, 30 de agosto de 2009

Pornophonique e Jamendo

Pornophonic é uma banda alemã de um estilo alternativo, que mistura rock e música eletrônica com sons de jogos de Gameboy e Commodore 64! Além de ter um pouco de pr0n como inspiração nas músicas!

Gostei de quase todas as músicas do album 8-bit lagerfeuer, mas posso destacar Sad Robot e Space Invaders como minhas preferidas. Inclusive todas as músicas estão disponíveis para download no site do Pornophonic.

Descobri essa banda há quase um ano, enquanto eu navegava no Jamendo, que é uma espécie rede social onde músicos podem publicar seus trabalhos. O interessante do Jamendo é que as músicas são todas distribuídas pela licença Creative Commons, todas com permissão para ouvir e redistribuir. Além disso, existe a possibilidade de os usuários se inscreverem num programa para receberem uma parte dos lucros obtidos com anúncios do site.

No final desse post tem um aplicativo do Jamendo para tocar o álbum, mas caso ele não funcione, na página do album no Jamendo tem várias alternativas para ouvir a música, desde o download de mp3 ou ogg via bit torrent ou até a possibilidade de integrar o site com o Rhythmbox ou Amarok.