domingo, 18 de dezembro de 2011

Linux ainda na frente no TOP500

Nesta última edição do projeto TOP500 (http://www.top500.org/) divulgada em Novembro de 2011, o qual classifica e mostra detalhes dos 500 mais poderosos sistemas de computadores no mundo, o sistema operacional Linux continua com sua superioridade, agora está presente em 91,4% dos 500 maiores supercomputadores. Veja na tabela e no gráfico:

Sistema Operacional        Contagem      Percentual
Linux                         457          91,4 %
Unix                           30           6,0 %
Misto                          11           2,2 %
Windows                         1           0,2 %
BSD                             1           0,2 %


Segundo o TOP500, no topo da lista está o supercomputador de nome K, situado no Japão. Um cluster fabricado pela Fujitsu com um total impressionante de 705.024 núcleos, em processadores SPARC64 VIIIfx. Este fabuloso supercomputador utiliza o Linux.

sábado, 17 de dezembro de 2011

Problema de Lógica: Igualdade entre produtos com dígitos invertidos

23 x 96 = 32 x 69

Surpreendentemente, existem vários pares semelhantes de números com dois dígitos onde seus produtos permanecem o mesmo quando as ordens dos dígitos são invertidas. Quantos pares de números você pode descobrir?





RESPOSTA





Evidentemente, se os números com dois dígitos são ambos formados por dígitos repetidos, como 22 e 55, então inverter a ordem dos dígitos mantém os números inalterados, assim os produtos serão os mesmos. Além disso, se o segundo número é formado pela inversão dos dígitos do primeiro número, por exemplo 12 e 21, então os mesmos números serão obtidos na inversão dos dígitos.

Suponha que os dois números são ab e cd, e depois queremos que seu produto seja igual ao produto de ba e dc. Isto pode ser expresso algebricamente como:

(10a + b) x (10c + d) = (1Ob + a) x (1Od + c)

na qual:

1OOac + 1Oad + 1Obc + bd = 100bd + 1Obc + 1Oad + ac

e simplificando:

99ac = 99bd

Então, os números satisfazem a condição requerida quando seus dígitos satisfazem:

ac = bd

Isto é equivalente ao produto dos dígitos da dezena sendo igual ao produto dos dígitos da unidade, dando as seguintes soluções:

12 x 42 = 21 x 24
12 x 63 = 21 x 36
13 x 62 = 31 x 26
12 x 84 = 21 x 48
14 x 82 = 41 x 28
13 x 93 = 31 x 39
23 x 64 = 33 x 46
24 x 63 = 42 x 36
24 x 84 = 42 x 48
23 x 96 = 32 x 69
26 x 93 = 62 x 39
34 x 86 = 43 x 68
36 x 84 = 63 x 48
46 x 96 = 64 x 69

Problema de Lógica: A fabulosa família

A notável avó generosa, a qual teve somente filhas, percebeu que cada uma filha teve a mesma quantidade de filhos quanto tinham de irmãs, e nenhuma filha. Por sua vez, cada um dos seus netos teve a mesma quantidade de filhas quanto tinham de irmãos. Ela alegrou-se ao contar isto aos seus amigos e, além disso, que o número total de filhas, netos e bisnetas era o mesmo que a sua idade! Quantos anos tem a avó?





RESPOSTA





Se a avó tivesse somente 4 filhas, ela teria 12 netos e 24 bisnetas. Desta forma, teria 40 anos de idade. Muito pouco para uma avó com bisnetas.

Se a avó tivesse 6 filhas, ela teria 30 netos e 120 bisnetas. Desta forma, teria 156 anos de idade. Demais para uma pessoa.

Portanto, a notável avó generosa tem 85 anos de idade. Ela possui 5 filhas, 20 netos e 60 bisnetas.

quarta-feira, 14 de dezembro de 2011

O Jogo da Vida de John Conway

Em 1970, o matemático britânico John Horton Conway inventou um jogo de simulação, reproduzindo os processos de um mundo real da sociedade de organismos vivos. A primeira divulgação deste trabalho de Conway foi na revista Scientific American número 223, de Outubro de 1970, na coluna sobre jogos matemáticos de Martin Gardner.

Este jogo é interessante pois é um exemplo simples de sistema auto-organizável, recebendo a atenção de cientistas e matemáticos de diversas áreas, em estudos sobre como padrões elaborados e comportamentos podem emergir de regras muito simples. Por exemplo, este jogo ajuda a entender como as pétalas de uma flor ou as listras de uma zebra podem aparecer de um tecido de células vivas crescendo juntas.

O Jogo da Vida se passa em um tabuleiro quadriculado com duas dimensões, bastante largo, onde os organismos ficam posicionados um em cada célula, e a partir da configuração inicial dos organismos, serão observadas as mudanças seguindo as leis gerais para nascimento, morte e sobrevivência.

As regras foram escolhidas cuidadosamente por Conway, após um longo período de experiência, para adequar-se a três desejos:

1) Não deverá ter um padrão inicial para o qual seja uma simples prova de que a população possa crescer sem limite.
2) Deverá ter um padrão inicial que aparentemente cresça sem limite.
3) Deverá ter um padrão inicial simples que cresça e se modifique por um período de tempo considerável antes de terminar em três possíveis modos: desaparecendo completamente, estabelecendo uma configuração estável que se mantenha imutável desde então, ou entrando em uma fase oscilatória na qual se repetirá eternamente em ciclos de dois ou mais períodos.

Em resumo, as regras deverão ser de tal modo que faça o comportamento da população imprevisível.

As leis gerais de Conway são muito simples. Cada célula do quadriculado, onde assume-se ser um plano infinito, possui oito células vizinhas, quatro ortogonalmente adjacentes e quatro diagonalmente adjacentes. As leis são:

1) Sobrevivência: Todo organismo com dois ou três organismos vizinhos sobreviverá para a próxima geração.
2) Morte: Cada organismo com quatro ou mais vizinhos morrerá (será removido) por superpopulação. Todo organismo com um vizinho ou nenhum morrerá por isolamento.
3) Nascimento: Cada célula vazia adjacente a exatamente três organismos vizinhos, não mais nem menos, é uma célula de nascimento. Um organismo será colocado nela no próximo movimento.

Uma célula ocupada por um organismo e suas oito células vizinhas.

É importante entender que todos os nascimentos e mortes ocorrem simultaneamente. Juntos eles constituem uma única geração ou um único movimento a partir da configuração inicial (ou anterior). O que acontece em cada organismo ou célula vazia na geração n+1 depende somente da sua vizinhança na geração n. Um organismo pode morrer no movimento seguinte e neste mesmo movimento pode ajudar no nascimento de outros organismos. Cada movimento é marcado em um período. A sucessão dos períodos formam a história da configuração inicial.

Na dinâmica do jogo, coloca-se um ou mais organismos, sempre um em cada célula, e a cada instante do tempo, um período, aplicam-se as leis gerais para cada célula do quadriculado. Um organismo em uma célula pode sobreviver ou morrer e uma célula vazia pode receber um organismo no próximo instante. E assim sucessivamente, a cada geração.

A figura abaixo ilustra a vida de alguns padrões, identificados de A a F. O quadriculado 0 representa a configuração inicial e 1 e 2 as gerações seguintes. Alguns padrões, A, B e C, desaparecem completamente, o padrão D se transforma em um bloco e fica imutável eternamente, o padrão E oscila eternamente em ciclos de dois períodos, e o padrão F torna-se imutável na segunda geração:

A evolução de alguns padrões de organismos.

Apesar do comportamento da população ser imprevisível, através das gerações, existem alguns padrões que foram conhecidos por Conway e por demais pesquisadores. Como vimos, algumas formas são capazes de se manter imutável eternamente (denominados "still lifes"), ou modificando-se de forma cíclica (denominados "oscillators"), entretanto, algumas são capazes de se locomover pelo quadriculado (denominados "spaceships"), e outras são capazes de adicionar organismos, por arremesso (denominados "guns") gerando "gliders", por rastro do deslocamento (denominados "puffers") ou se locomovendo e arremessando ao mesmo tempo (denominados "rakes"). A animação abaixo ilustra um padrão que realiza um deslocamento no decorrer dos períodos:

O padrão denominado "glider" se desloca sobre o quadriculado.

A melhor forma de reproduzir o Jogo da Vida é por meio de um software para computador. Existem centenas de softwares onde é possível criar uma configuração inicial. E clicando no botãozinho "play", a vida desenvolve-se nas regras do jogo. Dois softwares muito bons, e gratuitos, são o Golly (http://golly.sourceforge.net/), com uma rica interface repleta de recursos, e o LucidLife (http://icculus.org/~jcspray/LucidLife/), com um visual limpo e claro. Em ambos é possível "desenhar" os organismos no quadriculado ou carregar uma configuração de uma biblioteca, com dezenas de padrões separados por categorias. O Jogo da Vida é provavelmente o mais programado jogo para computador da existência.

O Jogo da Vida é um exemplo de autômato celular, que proporciona um modo conveniente para representar diversos tipos de sistemas, nos quais os valores das células em uma disposição são atualizados em passos discretos de acordo com uma regra. Este jogo tem recebido muito interesse nos últimos tempos. Neste campo de estudo da matemática, o Jogo da Vida de Conway é o mais estudado frente aos outros inventados. Existem algumas variações onde se usa um tabuleiro hexagonal, células com mais de dois estados (vivo ou morto), outras leis, outras dimensões, gerando padrões muito mais complexos.

Este jogo é fascinante pois leva a uma imensa variedade de histórias de vida, sem qualquer relação óbvia entre a configuração inicial e o que irá se transformar. Entretanto, todo o futuro infinito do sistema está implícito e determinado pela sua configuração inicial.

A grande questão sobre este jogo é, se é possível os organismos vivos desenvolverem-se suficientemente grandes e complexos, como nosso universo, se esperarmos tempo suficiente? Como se comportará um padrão quando se tornar infinitamente largo? Claro que o nosso universo é muito mais complexo, em dimensões, em leis, em matéria, mas o Jogo da Vida ilustra simplificadamente a evolução que vemos em nosso universo. Ilustra como comportamentos complexos podem ser gerados por leis muito simples. O Jogo da Vida trouxe novas questões para o ser humano pensar.

Windows Sysinternals

O Sysinternals (http://www.sysinternals.com/) é uma coleção gratuita de utilitários para diagnóstico, reparo e administração avançada, para a plataforma Windows. Possui uma ampla cobertura das funcionalidades de diversos aspectos do sistema operacional Windows.

A maioria dos utilitários possuem uma interface gráfica intuitiva, de fácil utilização, e outros possuem uma rica interface de linha de comando, para automatismo ou uso pelo prompt de comando.

O Sysinternals foi criado em 1996 por Mark Russinovich e Bryce Cogswell e em 2006 foi adquirido pela Microsoft, que vem disponibilizando estes utilitários no site da Microsoft TechNet.

Os utilitários não necessitam de instalação pois são compostos de arquivos únicos executáveis e podem ser executados de qualquer lugar, inclusive pela rede ou dispositivo removível. Também não deixam qualquer dado armazenado no sistema.

Dentre os utilitários, o Sysinternals fornece o Process Explorer, uma versão avançada do gerenciador de tarefas, o Autoruns, um avançado gerenciador de inicialização de aplicações, o RootkitRevealer, um utilitário de detecção de rootkits, PsTools, uma coleção de utilitários de console para acesso à arquivos e processos local ou remoto, e outros.

São dezenas e mais dezenas de utilitários fornecidos, para acesso ao registro, contas de usuários, active directory, organização do desktop, informação do sistema, rede, sistema de arquivos etc. Até o SDelete, já citado em artigo neste blog, também faz parte do Sysinternals.

Como se não bastasse, a Microsoft mantém no site o Sysinternals Live, um serviço que possibilita executar os utilitários diretamente pela Web. Simplesmente fornecendo o caminho para o Sysinternals Live no Windows Explorer ou na linha de comando, como http://live.sysinternals.com/[utilitário] ou \\live.sysinternals.com\tools\[utilitário].

Pelo site do Sysinternals é possível baixar isoladamente cada utilitário, como também está disponível uma suíte com todos eles em um único pacote.

Conheça mais sobre o Sysinternals em seu próprio site ou pelo livro oficial "Windows Sysinternals Administrator's Reference", de Mark Russinovich e Aaron Margosis, publicado pela Microsoft Press em 2011. Até a computação forense faz uso destes utilitários.

segunda-feira, 12 de dezembro de 2011

O Pôquer e suas combinações e probabilidades

O Pôquer é um jogo onde para vencer é preciso ter a combinação de cartas com menor probabilidade de ocorrência, tornando a combinação mais valiosa. A regra do Pôquer determina algumas combinações de cartas que são denominadas "mãos". São elas, em ordem decrescente de valor: sequência de naipe real, sequência de naipe, quadra, trinca e par, mesmo naipe, sequência, trinca, dois pares e um par. As mãos mais valiosas são mais difíceis de aparecer em um jogo de Pôquer.

Um baralho de Pôquer tem 52 cartas, 13 de cada naipe, do 2 ao Ás. Cada mão utiliza 5 cartas e em um arranjo simples, o número de maneiras diferentes que pode-se pegar 5 cartas de 52 é A(n,p) = n!/(n-p)! = 52!/(52-5)! = 311.875.200. Ou pela regra do produto, do princípio fundamental da contagem, este número é dado por n * (n-1) * (n-2) * ... * (n-p+1) = 52 * 51 * 50 * 49 * 48 = 311.875.200.

Mas, no arranjo simples, calcula-se os agrupamentos ordenados de 5 cartas distintas, que se podem formar com as 52 cartas do jogo, ou seja, a ordem das cartas modifica o grupo. E para um jogo de Pôquer não importa a ordem na qual um jogador recebe as cartas. Trata-se da ordem na qual as cartas são retiradas do maço e não da ordem para a mão, na composição de uma sequência por exemplo, pois para obter uma sequência não precisa retirar as 5 cartas já na ordem da sequência.

Assim, utiliza-se o cálculo de combinação simples para determinar o número de maneiras diferentes que se pode pegar 5 cartas de 52. Onde C(n,p) = n!/(p!(n-p)!) = 52!/(5!(52-5)!) = 2.598.960.

Como existem P(5) = 5*4*3*2*1 = 120 modos diferentes de arranjar as 5 cartas, então deve-se reduzir em 120 vezes o número do arranjo simples, dividindo o cálculo prévio por 120 para obter (52*51*50*49*48) / (5*4*3*2*1) = 311.875.200 / 120 = 2.598.960.

C(n,p) = A(n,p)/P(p) = (n!/(n-p)!)/p! = n!/(p!(n-p)!) = 2.598.960, estas são as diferentes maneiras que pode-se pegar 5 cartas de 52, pois a ordem não importa. Muitas delas serão mãos valiosas, algumas mais fáceis de se obter, outras nem tanto.

Além deste número total de combinações, de 5 cartas em 52, pode-se calcular quantas combinações existem para cada mão do Pôquer, isto é, em quantas mãos diferentes são possíveis formar uma sequência, ou uma quadra, ou uma trinca etc.

Começando pela mão mais valiosa, a sequência de naipe real é formada pelas cartas de valor 10 ao Ás, todas do mesmo naipe. Como no baralho há 4 naipes então só existem 4 sequências de naipe reais possíveis.

A sequência de naipe pode ser determinada pelo valor da menor carta e esta menor carta deve ser menor que 10. Assim, existem 9 cartas por naipe adequadas para ser a menor carta da sequência, do Ás ao 9, totalizando 36 cartas. Desta forma, tem-se 36 sequências de naipe possíveis.

Para formar uma quadra, existem 13 valores disponíveis e 48 cartas disponíveis para ser a quinta carta da mão. Existem 13 * 48 = 624 quadras possíveis.

Para formar uma trinca e um par, existem 13 valores para a trinca e 12 valores para o par. Dentre as cartas de mesmo valor há 4 formas de montar uma trinca e 6 formas de montar um par, com os 4 naipes diferentes. Existem 13 * 12 * 4 * 6 = 3744 trincas e pares possíveis.

Para formar 5 cartas do mesmo naipe, temos por naipe C(13,5) = 13!/(5!(13-5)!) = 1287 combinações possíveis. Porém 10 delas também são sequências de naipe então devem ficar de fora, 1287 - 10 = 1277. São 4 naipes, portanto, existem 1277 * 4 = 5108 combinações possíveis de 5 cartas do mesmo naipe.

Para formar uma sequência com naipes distintos, 40 cartas são adequadas para ser a mais baixa da sequência. A partir desta, há 4 possibilidades para cada uma das 4 cartas restantes. Excluindo as sequências de naipe, real ou não, existem 40 * 4 * 4 * 4 * 4 - 40 = 10.200 sequências possíveis.

Para uma trinca, existem 13 valores em cada naipe para a trinca e C(12,2) * 4 naipes = 12!/(2!(12-2)!) * 4 = 66 * 4 = 264 combinações para as 2 cartas restantes. Há 4 formas de montar uma trinca com cartas do mesmo valor, então, existem 13 * 4 * 264 * 4 = 54.912 trincas possíveis.

Para formar dois pares, há C(13,2) = 13!/(2!(13-2)!) = 78 conjuntos de dois valores dos pares e 6 formas de montar cada par, além de 11 * 4 = 44 cartas para compor a quinta carta. Existem 78 * 6 * 6 * 44 = 123.552 possibilidades de formar dois pares.

E para formar um par, existem 13 valores em cada naipe para o par e 6 formas de montar um par com cartas do mesmo valor. Há ainda C(12,3) * 4 naipes = 12!/(3!(12-3)!) * 4 = 880 combinações para as outras três cartas e 4 formas de montar estas três cartas restantes. Existem 13 * 4 * 6 * 880 * 4 = 1.098.240 pares possíveis.

Estas foram as combinações das mãos com algum valor, mas é possível também ter uma mão ausente de valor, que são as combinações restantes até o total.

Em uma mão que não contenha alguma das combinações valiosas, ou seja, uma mão com nada, onde no jogo, considera-se apenas o valor da carta mais alta, temos C(13,5) = 13!/(5!(13-5)!) = 1287 possibilidades de 5 cartas em 13. Contudo 10 possibilidades formam uma sequência e desconsiderando-as, ficam 1277. Cada uma das cinco cartas pode ser de um dos quatro naipes, 4 * 4 * 4 * 4 * 4 = 1024, entretanto elas todas não podem ser do mesmo naipe, isto são 4 possibilidades para desconsiderar, uma pra cada naipe, 1024 - 4. Assim, existem 1277 * (1024 - 4) = 1.302.540 combinações sem valor.

Outra forma de calcular é somando todas as combinações das mãos valiosas e subtrair este valor do número total de combinações, pois 2.598.960 - (4 + 36 + 624 + 3744 + 5108 + 10.200 + 54.912 + 123.552 + 1.098.240) = 1.302.540.

Tendo o valor que representa todo o universo de combinações de 5 cartas em 52 e a quantidade de combinações para cada mão, é possível calcular a probabilidade de uma mão aparecer durante um jogo de Pôquer. Uma combinação de uma mão valiosa dividida pelo total resulta na probabilidade de ocorrer a respectiva mão.

A tabela abaixo ilustra as probabilidades para cada mão do Pôquer:

Mão                  Combinações    Probabilidade

Sequência Real                 4    0,000001539
Sequência de Naipe            36    0,000013852
Quadra                       624    0,000240096
Trinca e Par               3.744    0,001440576
Naipe                      5.108    0,001965402
Sequência                 10.200    0,003924647
Trinca                    54.912    0,021128451
Dois Pares               123.552    0,047539016
Um Par                 1.098.240    0,422569028
Nada                   1.302.540    0,501177394

Pela tabela acima percebe-se que as chances de uma mão vir com nada são de aproximadamente 50%. A menor probabilidade proporciona o maior valor para a mão. Por isso que a sequência de naipe real é a mão mais valiosa, sua probabilidade é extremamente baixa. Para se ter uma ideia, a probabilidade de acertar os seis números da Mega-Sena é 0,000000020, apenas 77 vezes menor que a probabilidade da sequência de naipe real.


Saiba mais sobre análise combinatória (http://dan-scientia.blogspot.com/2009/12/analise-combinatoria.html) e probabilidade (http://dan-scientia.blogspot.com/2010/01/probabilidades.html).