Onde estás Alan Turing?

Alan Turing

O Jardim do Campo Grande passou o ano de 2013 divido em dois. Um jardim mais perto de Entrecampos aberto ao público, e o jardim que fica em frente à Faculdade de Ciências… fechado para obras. Abriu agora (infelizmente para o presidente da Câmara não ficou pronto a tempo das eleições) e com uma curiosidade interessante:

O percurso que ladeia o jardim do lado da FCUL elogia os grande matemáticos dos tempos modernos desde 1537 com Pedro Nunes até aos tempos recentes. A CML mandou instalar uma placas no chão em jeito de cronologia de eventos e a verdade é que não se fica indiferente, quer-se sempre seguir até à próxima para ver quem está lá, e o que comemora.

A verdade é que percorri hoje este caminho 4 vezes em menos de 45 minutos para me deliciar com os pormenores biográficos (entre outros prazeres que o coração agradece) dos matemáticos que ajudaram a construir a sociedade moderna. Euler, Bayes, Newton, Libeniz, Gauss, Hilbert, Poincaré… estão todos lá… e mais alguns que a memória não me ajuda.

MAS

Mas a verdade é que apesar de tudo isto estar muito bonito… a cronologia é omissa em alguns monstros do século XX. E honestamente são tão importantes que não percebo como podem faltar.

Vamos andando e em 1933 apanhamos com Kolmogorov e saltamos para 1950 e apanhamos com Von Newmann. Volto atrás, vou até mais à frente e pasmo. Faço uma pirueta e pergunto-me:

SERÁ QUE SE ESQUECERAM?

Onde está Alan Turing? O génio da criptanálise que ajudou a derrotar a Alemanha? O Homem que dá o nome ao teste de Turing! O homem que escreveu papers tão fundamentais?

DEVE SER ENGANO, DEIXA LÁ VER DE QUEM MAIS SE ESQUECERAM, pensei eu incrédulo.

A verdade é que logo a seguir falta outro monstro do século XX. Claude Shannon que é só apelidado de pai da teoria da informação.

E pronto por esta altura já tinha uns 6Km nas pernas e um bocado enjoado com o que NÃO VI, voltei para casa e escrevi esta cartita

Senhor presidente da Câmara de Lisboa,

O senhor gosta de comer bem, e aquilo que fez no jardim do campo grande é um belo bacalhau no forno com batatinhas a murro. Só que, tal como está, esqueceu-se de colocar o bacalhau e ficou apenas com as batatas.

Se por acaso não tiver uns trocos para meter lá umas placas a lembrar os feitos destes dois senhores, pelo menos contrate um Banksy qualquer para resolver o problema.

Cumprimentos

Um Lisboeta que até gosta de correr no seu nosso novo jardim.

3.14 formas de determinar o valor de Pi

O valor do Pi é 3.14159… mas o valor do Pi é um número irracional e não é possível determinar um padrão nos dígitos de Pi que se repita infinitamente — embora todas as sequências de números se encontrem algures no número Pi. Um número irracional é aquele em que não é possível representar pela divisão dois números inteiros.

Então como calcular o valor de Pi? Qual o significado de Pi?

Conteúdo:

Uma introdução a Pi

Pi é o rácio entre o perímetro e o diâmetro de uma circunferência. pi=P/D

A primeira definição que provavelmente aprendemos na escola sobre Pi tem a ver com a determinação do perímetro de uma circunferência de diâmetro 1. O valor do perímetro desta circunferência é o valor de Pi e daqui surge logo a primeira forma de determinarmos o seu valor. Desenha-se uma circunferência com um compasso cuja amplitude seja 0.5 e o perímetro será de 3.14… (as unidades são arbitrárias) que teria que ser medido com um cordel pousado sobre o perímetro. Ora este método não é muito preciso e já no passado se sabia que o valor de Pi poderia ser calculado desta forma.

1) Um pouco da História antiga de Pi

Claro que na história já havia uma ideia do valor de Pi. Os Babilónios antigos tinha ideia de que o valor de Pi seria próximo de 3 e há um gravação onde é indicado o valor de 3.125. Por seu lado, os egípcios determinavam a área do círculo como [(8d)/9)^2 (com d igual ao diâmetro) o que dá um valor de Pi de 3.1605.

Arquimedes de Siracusa por seu lado percebendo que não podia determinar o valor exacto de Pi através de um número racional decidiu enquadrá-lo entre dois números racionais. Segundo ele, Pi estaria no intervalo [223/71, 22/7]. O método geométrico consistia na utilização de poligonos que eram inseridos ou que cobriam a circunferência. Desta forma era possível obter um intervalo para o valor de Pi.

Até na Bíblia aparece uma referência indirecta de Pi como sendo igual a 3 (ver passagem sobre o mar de bronze onde para uma circunferência de dez côvados de diâmetro era preciso usar um fio de trinta côvados para medir o perímetro).

No século XVI e XVII a cálculo de Pi beneficiou dos recentes avanços matemáticos na domínio séries infinitas permitindo o cálculo de Pi com muito maior precisão que os métodos geométricos utilizados até então. Na Europa James Gregory em 1671 e Leibniz em 1674 redescobriram uma série infinta de Madhava de Sangamagram em que

arctan (z) = z - z^3 / 3 + z^5 / 5 - z^7 / 7 +...

Esta fórmula é igual a Pi/4 quando z=1, mas converge lentamente pelo que John Machin apresentou em 1706 uma fórmula que converge muito mais rapidamente e que é a fórmula usualmente utilizada no cálculo de Pi nos computadores modernos:

Pi/4 = 4*arctan(1/5)-arctan(1/239)

Se expandirmos a fórmula em série, apenas com 4 parcelas é possível ter um erro na 6 casa decimal. Nada mau.

Foi também no século XVIII que a letra grega π foi introduzida para designar este valor, tendo a sua utilização sido popularizada por Eüler.

Podem experimentar a comparação dos dois valores com o seguinte código em python:

def arctan(z, it):
    out=0.0
    for a in range(1,it+1):
        p=2*a-1
        s=1
        if a%2==0:
            s=-1
        out+=s*(z**p)/p
    return out
 
for a in range(1,5):
    print 4*arctan(1.0,a), 4*(4*arctan(1.0/5,a)-arctan(1.0/239.0,a))

2) Calcular Pi com berlindes

Mas há outras razões que também dão Pi, uma delas é a que permite o cálculo de Pi através do atirar berlindes para dentro de uma caixa. Imagine que tem uma caixa quadrada e uma hula-hoop que encaixa perfeitamente dentro desta caixa. Se atirarmos berlindes para dentro da caixa de forma a que caiam aleatoriamente, calcularmos a fracção dos berlindes que caíram dentro do círculo e multiplicarmos por 4 temos uma aproximação de Pi.

A razão pela qual isto funciona tem a ver com o facto da razão entre as área do círculo e do quadro que o inscreve estarem relacionadas por Pi/4 (π.r^2/4.r^2= π/4). Se tiver paciência experimente lançar 400 berlindes para dentro da caixa e verifique. Claro que uma forma mais simples é fazê-lo através de um programa de computador. Por exemplo o código seguinte escrito em python lança o equivalente a 400 000 berlindes para fazer uma estimativa de Pi.

import random
pi=0
for a in range(400000):
        x=random.random()
        y=random.random()
        if x**2+y**2<1:
                pi+=1
print "Estimativa de Pi", pi / 100000.0

3) Calcular Pi com fósforos

Uma outra forma de calcular Pi é a partir de fósforos (quantos mais melhor) e um cartolina. Desenhe na cartolina linhas horizontais paralelas com uma distância entre si igual ao tamanho dos fósforos. Depois atire da forma mais aleatória possível os fósforos para cima da cartolina. Duas coisas podem acontecer: ou os fósforos tocam uma linha (não podem tocar as duas linhas ao mesmo tempo) ou não tocam em linha nenhuma. Agora é só uma questão de contar. Conte o número de fósforos que atirou (N) e o número de fósforos que cruzaram linhas (C). Depois, o valor de Pi é aproximado por $latex 2\times N/C$. Este método é também conhecido como o método da agulha de Buffon. O Conde de Buffon viveu no século XVIII e foi um naturalista francês que ainda antes Darwin apresentou ideias sobre a evolução das espécies.

4) Calcular Pi com Computadores

Hoje em dia o cálculo de Pi é feito por computadores através de diferentes estratégias de computação do valor de Pi. O número de dígitos calculados atinge valores para lá do racional (perdoem a chalaça) na ordem dos 10 triliões (10^13). Tanta precisão é inútil para aplicações práticas mas o software desenvolvido para fazer estes cálculo é muito utilizado para benchmarks de computadores e como testes de stress de máquinas pela comunidade de Overclocking.

O princípio básico do cálculo de Pi através de computadores é através de aproximações numéricas de séries infinitas. Os recordes mais actuais são batidos utilizando normalmente o algoritmo de Chudnobsky

Algum software para calcular Pi:

Sobre o (NÃO) crescimento exponencial do Twitter!

twitter.com_6_months

É costume ouvir falar de crescimento exponencial, da internet, lei de Moore, etc… enfim de tudo aquilo que a percepção humana percebe estar a crescer a um ritmo mais elevado do que a aparente normalidade.

No entanto há uma grande liberdade de utilização do termo “crescimento exponencial”. Muitas vezes é metido neste saco o crescimento em lei de potência. Em alguns casos acontece que o crescimento é mesmo linear e é metido no saco do crescimento exponencial.

Veja-se o twitter:

(more…)

Combinações únicas de conjuntos com números primos

Imaginemos que num programa temos que gerar uma espécie de chave única para uma combinação de elementos de um set e em que a ordem pela qual esses elementos aparece não é importante. Imaginemos que o set é

e que é preciso gerar chaves únicas para subsets de 3 elementos de ZZ

por exemplo:

Uma forma de fazer isto é aproveitar uma propriedade dos números primos.

Começa-se por se atribuir um número primo a cada um dos elementos de ZZ

e depois calcula-se o produto dos subconjuntos. Assim:

Ainda para mais que é o pretendido uma vez que a multiplicação é comutativa. Por outro lado como se está a multiplicar números primos temos a garantia que o valor encontrado é único e pode entrar numa tabela sem perigo de duplicação.

A beleza deste método é que como a multiplicação é uma das operações mais rápidas de fazer em termos computacionais, este procedimento é realmente útil e rápido para criar mapas dos subconjuntos com outra propriedade qualquer.

Matemática do Linux

Embora seja o melhor sistema operativo do planeta, a percepção que se tem da utilização e da procura do linux nem sempre é compreendida. O site distrowatch.com possui um ranking das várias distribuições de linux que permite ao utilizador perceber o “momentum” que cada distro vive.

Este ranking é baseado no número de Page Hits e embora não sendo rigoroso quanto à penetração no mercado das várias distros, permite ter uma ideia geral sobre o assunto. Tendo andado a brincar recentemente com leis de escala e leis sem escala, decidi olhar para estes rankings sob a perspectiva da matemática.

Antes de começar o estudo do ranking da distrowatch, tinha uma ideia que queria confirmar. Será que o número de page hits de cada distribuição obedece a uma lei de potências?

Latex

O tipo de fenómeno parecia ajustar-se perfeitamente a estas leis pelo que o primeiro passo foi representar o histograma do page hits em função da posição no ranking. O distrowatch possui um Top 100 na página inicial, mas permite também aceder às listagens completas e assim escolhi utilizar os dados dos últimos 12 meses para fazer esta análise.

A representação do dados num gráfico mostrou logo que estava no bom caminho:

histograma

As 359 distribuições apresentam um comportamento típico de leis sem escala, ou leis de potência. Estas distribuições aparecem numa série de fenómenos naturais. Os tremores de terra, por exemplo que são dados pela lei de Gutemberg-Ritcher:

Outros modelos incluem por exemplo a actividade neuronal, ou o tamanho dos seres, ou ainda o caso de avalanches em modelos matemáticos como o de Bak-Sneppen.

O próximo passo foi naturalmente representar os mesmos dados em escala logarítmica a fim de verificar se nesta escala eles se apresentavam como uma linha recta com um determinado declive:

O comportamento observado continuou a ser típico de uma lei de escala, embora ficasse um pouco surpreendido com a observação de que parecia haver duas zonas distintas, com declives diferentes. No fim o cut-off seria natural. As leis sem escala verificam-se sempre numa determinada gama. Para além disso verifica-se o cut-off. Mas normalmente estamos muito afastados desse cut-off. Se este cut-off não existisse isso queria dizer por exemplo que no modelo dos tremores de terra existiria certamente um tremor de terra com energia suficiente parra fazer explodir a terra. Ora a energia acumulada na terra não é ilimitada e naturalmente tem que existir um cut-off.

Representando as duas secções importantes da e ajustando-as a uma lei de potências obtive o seguinte:

Para os primeiros 100 lugares do Top do DistroWatch.com

e para a zona[101-340]:

Como se pode ver os r^2 são ambos muito altos. No entanto parece que o top é regido por duas leis diferentes com expoentes diferentes. Enquanto o expoente da primeira parte é muito próximo de -1, o segundo é muito próximo de -2.

Conclusão

Pensando no porquê desta diferença e porquê da transição em torno do valor 100 do ranking, presumi que o efeito se deve à presença do Top 100 na página inicial do DistroWatch, levando que as distros que estão nesta página tenham muito mais visibilidade e daí recebam mais hits que as restantes que não conseguem assim tanta visibilidade de consequentemente hits.

Modelo Bak-Sneppen

Andámos todos de volta do modelo do Merton, que nem tive tempo para outras coisas, mas agora que a entrega no passado, pus-me a brincar com o modelo Bak-Sneppen, falado na aula de Matemática. Queria ver o boneco a funcionar… e depois de o implementar, não é que funciona?

Bak-Sneppen

Para quem quiser experimentar, criei o projecto no NetBeans e podem fazer download do projecto para o correr no vosso computador.

Entropia, Gibbs e Testes de Hipóteses

Incerteza

três tipos de incerteza: a incerteza determinística, em que não são conhecidos os estados que um sistema pode assumir; a incerteza entrópica, em que são conhecidos os estados possíveis, mas não as chances de ocorrência de cada um deles; e a incerteza probabilística, em que são conhecidos não só os estados possíveis mas também a distribuição de probabilidade para eles… fonte: Rogério Silva de Mattos

Entropia de Shannon

Claude Elwood Shannon Teoria da Informação Information Entropy Measures of Uncertainty: Shannon’s Entropy

Axiomas de Khinchin

Entropia de Rényi

Rényi entropy

Medidas de Gibbs

from wikipedia (não muito prático) Princípio da Máxima Entropia Paper Maximum Entropy: Clearing up Mysteries

Testes de Hipóteses

Thomas Bayes Thomas Bayes 2 Bayes Theorem (stanford): Uma descrição muito exaustiva do teorema de Bayes juntamente com um conjunto de exemplos muito práticos para entender a formulação.