A lenda dos dragões surgiu quando os antigos achavam crânios de dinossauros, que eram bichos que eles nunca tinham visto. O que eu não sabia era a origem dos ciclopes, os gigantes de um olho só! Nessa foto que achei na web dá pra ver claramente, um grego achando um crânio desses poderia facilmente deduzir que era de um ciclope.

(fonte da imagem: http://tripwow.tripadvisor.com/slideshow-photo/10-sarah-with-an-elephant-skull-by-travelpod-member-sarahfey-arusha-tanzania.html?sid=10196902&fid=tp-21)

Fiz uma implementação de graph partition usando MIP, porque MIP é vício:

https://github.com/ricbit/Oldies/blob/master/2014-02-partition/partition.cc

A primeira motivação é dividir uma quantidade de trabalho entre p processadores, de modo que cada processador tenha uma carga mais ou menos igual e o tráfego entre eles seja minimizado.

A segunda motivação é fazer figuras bonitas com bolinhas coloridas.

Eu andei pensando no caso do Woody Allen, especialmente em saber se as acusações desqualificam a obra dele, ou se a obra tem valor independente do caráter da pessoa que faz. Eu nunca vi um filme dele, então não tenho como julgar, mas tem um análogo que eu consigo imaginar, que é o Feynman.

Eu adoro o trabalho do Feynman, tanto o científico quanto o não-científico. Mas ele fez a bomba atômica, então é culpado pela morte de pelo menos 150 kpessoas. Isso desqualifica o trabalho dele ou não?

Como eu sou fã do Feynman, minha cabeça ficou racionalizando e concluí que no fim essas mortes não são culpa dele, são culpa do Popper. Quem matou essas pessoas foi o método científico.

O problema do projeto Manhattan é que eles estouraram o deadline, quando a bomba ficou pronta a Alemanha já tinha perdido a guerra. Mas eles gastaram muita grana para fazer a bomba, e não sabiam qual seria o efeito delas em humanos (só sabia-se em casas e porcos, não em humanos). Então, para saber se o investimento valeu a pena, você precisava de um teste empírico. E tome bomba em Hiroshima, já que nessa altura só tinha sobrado o Japão de inimigo.

E a prova de que isso foi um teste é a bomba em Nagasaki. Se o motivo fosse só aterrorizar e forçar a capitulação, não precisava da segunda bomba. Eles só lançaram porque precisavam testar se o mecanismo implosion-type de plutônio da Fat Man era tão bom quanto o gun-type de urânio da Little Boy.

Então não foram mortes causadas pela ciência, foram mortes causadas pelo método científico.

De curiosidade, pacote de fotos assustadoras de quando eu visitei Hiroshima em 2012:

https://picasaweb.google.com/116439213243261718069/Hiroshima?noredirect=1#

Depois da brincadeira dos artistas, agora é a vez da brincadeira dos matemáticos! Você ganha um matemático e precisa escolher um teorema que ele tenha criado. O Reynaldo Fagundes me passou o Donald Knuth, se você também quiser um matemático, é só postar um comentário escrito MANDA.

O Knuth é um dos mais prolíficos autores do século XX, atuando nas áreas mais diversas. Todo mundo o conhece pelo seu trabalho na computação, mas ele também é matemático, organista e humorista (seu primeiro trabalho publicado foi na revista MAD. Sim, aquela revista MAD). Escolher um dos teoremas do Knuth é difícil, porque ele tem muitos trabalhos memoráveis, mas eu acabei escolhendo o mais seminal deles: o paper "Ordered Hash Tables", publicado pela primeira vez The Computer Journal #17 (1974).

O problema é simples: qual é o tempo médio para inserir um valor em uma hash table (com open addressing)? Pergunte isso para qualquer estudante ingênuo e ele vai te responder que é O(1). Mas essa não é a resposta correta! O tempo O(1) só vale no caso em que o número de inserções é muito menor que a tabela, de modo que não tenham colisões.

Mas, na vida real, colisões acontecem. Essa é a essência do teorema do aniversário: em uma hash table de 365 posições, você tem 50% de chance de ter uma colisão após 23 inserções, e essa chance sobe com o número de inserções.

Então, qual o valor real do tempo médio? Apesar do enunciado ser relativamente simples, por anos ninguém sabia resolver o problema, até o Knuth achou a solução em 1974. O povo se perguntava: como analisar, se eu não sei qual a função de hash que você vai considerar? A resposta do Knuth foi: considere todas ao mesmo tempo! Se a sua tabela tem M posições e você vai fazer N inserções, então existem M^N funções de hash diferentes, e o que o Knuth fez foi calcular a média sobre todas elas.

Se você quiser ver a solução, ela está no Art of Computer Programming vol.3. O Knuth, sempre piadista, deixou a demonstração como exercício para o leitor (LOL). Mas não é complicado, em três páginas de contas você resolve, se tiver paciência e conhecimento de análise combinatória.

O resumo da solução é que o número médio de consultas à tabela de tamanho M após N inserções é:

Esse valor do Knuth é exato, mas não te dá muita intuição sobre o algoritmo. Se você assumir que N é razoalmente menor que M, então tem um assintótico mais simples:

Nesse assintótico fica mais claro. Ele realmente é O(1) na primeira inserção, quando N=0; mas depois esse tempo vai subindo. E no limite, quando a tabela está cheia, é infinito? Nope, esse assintótico só vale quando N<<M; intuitivamente, não tem como ter mais que M-1 colisões numa tabela de tamanho M.

Porém, se você colocar N=M e usar a função Q de Ramanujan (um clássico para quem, como eu, sofreu fazendo o curso de Analytic Combinatorics no coursera), então você consegue o valor limite:

Agora, se alguém perguntar, você pode responder com propriedade: a inserção é O(1) quando a tabela está vazia, e vai crescendo até chegar em O(sqrt(N)) quando a tabela está cheia.

Bônus 1: foto de quando encontrei o Knuth.

Bônus 2: eu e a revista MAD que tem o primeiro artigo do Knuth

Bônus 3: Minha biblioteca de livros do Knuth. Os quatro Art of Computer Programming (sendo que o vol.4 está autografado e com dedicatória!), o Concrete Mathematics (que é o melhor livro de Matemática ever), três fascículos do Art of Computer Programming em japonês (que foram presente do Carlos Duarte Do Nascimento), e quatro volumes da série de Selected Papers (obras super legais que pouca gente conhece).

Bônus 4: se você ficou curioso com a função Q de Ramanujan, então talvez queira ver minha apostila de Analytic Combinatorics. No exercício 4.71 eu resolvi o assintótico da função P de Ramanujan, que é parente da função Q: http://www.ricbit.com/temp/analytic.pdf

A Ila Fox é uma garota muito sistemática, e sempre que recebe um orçamento no email ela adiciona o nome e a data numa planilha no google docs. Aí hoje eu resolvi pegar esses dados e brincar.

Primeiro, eu agrupei o número de pedidos por semana. Depois mandei essa série temporal para o Google Correlate. O resultado foi que essas são as queries mais relacionadas com a minha série:

r=0.8280 festa infantil galinha pintadinha
r=0.8208 convite de cha de bebe 

Olha só, eu forneci para ele uma lista de datas e números, mais nada. Nenhum metadata, nenhuma informação de origem, só datas e números. E com isso ele deduziu que era um gráfico sobre venda de lembrancinhas para festas infantis.

SCIENCE. IT WORKS, BITCHES.

Se a informação na tela está certa, então esse download vai demorar 422 milênios para terminar.

Provavelmente eles escrevem o datagrama num papel, colocam nas costas de uma formiga, e mandam ela vir da Califórnia para cá.

Sempre tem os idiotas que defendem o Gentili dizendo que a base do standup americano é a ofensa mesmo. Mas eu vejo dois problemas com essa argumentação.

Primeiro, quem disse que você precisa copiar o humor alheio? A nossa tradição humorística é mais antiga que os standups americanos, os cancioneiros portugueses possuem cantigas de escárnio e maldizer que datam do século 12. 

Segundo, mesmo essas cantigas do século 12, que eram humor ofensivo por definição, sempre ofendiam os abusadores, e não os abusados. As cantigas de escárnio eram indiretas porque se você mencionasse o nome do padre corrupto sendo zoado, você ia para a fogueira.

Agora compara a mediocridade do Gentili com o video mais recente da Porta dos Fundos para ver a diferença:

Dia desses eu estava olhando uma galeria de capas do Buscema e fiquei espantado com uma delas. Minha primeira impressão foi "uai, desde quando o Buscema desenhou Sandman?" mas depois eu mudei para "nó, isso é muito mais legal que Buscema desenhando Sandman, é o Buscema desenhando Labirinto!". Como eu sou Labyrinth-freak, não resisti e acabei comprando as três edições originais.

Trazer isso pro Brasil foi uma aventura, então agredecimentos especiais ao Daniel Balparda de Carvalho, Cleide Regina, Rodrigo Damazio Bovendorp e Patricia Siqueira Bovendorp Damazio pela ajuda!

Como freak pouco é bobagem, eu e o Sir Didymus original:

Os piratas do futuro usam raio laser e régua de cálculo!

(Capa de Pirates of Ersatz by Murray Leinster (1959), com arte de Kelly Freas. Obrigado ao @fzort pelo achado!)

Aproveitando a vibe de retrocomputação mecânica, duas fotos minhas com dispositivos clássicos: a Máquina Diferencial do Babbage e o Mecanismo de Antikythera!

Os engenheiros que possuem uma régua de cálculo são o desejo da mulherada! (cartoon de 1940)

A minha Archimedes tem 10 escalas e 2 dígitos significativos, agora eu estou de olho em uma K&E log log duplex decitrig com 23 escalas e 3 dígitos significativos. Quanto mais escalas, menos movimentos você precisa fazer para resolver sua conta.

Descobri também que tem uns modelos especializados, tipo a K&E log log duplex vector, que calcula o seno hiperbólico com um único movimento. Devia ser o bicho para quem trabalhava com linha de transmissão.

Novamente a brincadeira do artista, dessa vez o Marco Lazzeri me passou o Roy Lichtenstein! Se você quiser um artista para brincar, deixe em comentário escrito MANDA.

Para falar do Roy eu vou ter que rebobinar até a época dos gregos, porque eu não consigo falar de arte moderna sem o contexto em volta. Se você pegar a arte dos gregos, vai ver que eles tem aquelas estátuas super realistas, mas as pinturas são bem simples em comparação. Isso não é preconceito com a pintura, é falta de tecnologia, eles não tinham tintas que permitissem fazer pinturas tão realistas quanto as estátuas.

Essas tintas só foram ser inventadas lá pelos idos de 1300, e nessa época começam a aparecer as pinturas com sombreamento realista. Na época da Renascença Italiana os caras piraram na estética de realismo, que começaram a ter uma fixação mórbida em fazer reproduções perfeitas (literalmente mórbida, para que pegar um livro de anatomia, se você pode dissecar um cadáver e ver in loco como os músculos se encaixam?). A busca por realismo foi aumentando em escala com o tempo, se você pegar aquele quadro das meninas que tem no MASP, o Renoir não contente em apenas fazer a pintura realista, fez até o relevo no vestido das gurias.

Mas a farra do realismo acabou lá por volta de 1850, quando inventaram a fotografia. Para que se esforçar com a técnica perfeita, se você pode tirar uma foto que é muito mais fácil e dá um resultado muito melhor? Quando a fotografia aparece, os artistas surtam e aí que aparecem o impressionismo, cubismo, surrealismo. Não faz mais sentido buscar o realismo, então você abraça o irreal.

É nesse contexto que eu localizo o povo da pop art como o Warhol e o Lichtenstein. Eles possuem a técnica, mas não tem interesse em retratar o mundo real. Ao invés disso, eles vão uma camada acima, fazendo retratos de segunda ordem, reproduções realistas de reproduções que não são realistas. Ao invés de pintar uma fruta, você pinta o rótulo de uma latinha de fruta em conserva. Ao invés de pintar uma mulher, você pinta a caricatura de uma mulher em uma revista.

O Lichtenstein, além de subverter a técnica, subverteu a temática também. Os gregos esculpiam a mitologia do Olimpo. Os italianos pintavam a mitologia Cristã. O Lichtenstein pinta a mitologia moderna: os gibis. Cada um dos quadros dele é uma reprodução de uma história em quadrinho, que tem hoje em dia a mesma função dos mitos para os antigos. E os quadros dele não são impressos saídos de gráficas, são telas enormes pintadas a óleo e acrílico. Os tons que no original eram pontinhos feitos com decalques, nos quadros dele são pontões pintados a mão.

Para ilustrar, eu escolhi o quadro "Image Duplicator", que eu entendo como sendo um auto-retrato. Se fosse o Leonardo, ele usaria um espelho para fazer uma cópia fiel de si mesmo. O Roy não está interessado em leituras literais, então retrata como ele se sente. Os artistas clássicos sempre diziam que pop art era uma piada e não era arte de verdade. Então o Roy se sente como um vilão, e para isso ele copia um quadro do Kirby no X-Men #1, se desenhando como o Magneto. E o texto pergunta aos críticos: "o que vocês sabem sobre meu duplicador de imagens?". Para os críticos, o trabalho dele é só uma cópia. Mas a pergunta é irônica: se você prestar atenção, nenhum dos quadros dele é uma somente uma imagem duplicada. Ele sempre muda algo: nessa imagem, o original não tinha as sobrancelhas loiras, e nem o texto do quadrinho era esse.

A diferença das culturas: dia desses eu traduzi no meu blog em inglês aquele post das calculadoras científicas. No Brasil os comentários eram sempre no sentido de "nó, que legal, um exemplo de criatividade e superação". Mas, para os americanos, a coisa é mais pragmática: "se você não tinha dinheiro para comprar uma calculadora científica, porque não comprou uma régua de cálculo?"

É mesmo né, uma régua de cálculo teria resolvido meu problema. Eu desconfio que nessa época (1991) elas deveriam ser mais ou menos o mesmo preço da calculadora, mas fiquei curioso para ver como seria a experiência e comprei uma no mercado livre para testar. Chegou hoje, um modelo da década de 60 bonitão, agora só preciso deduzir como se usa!

O JOGO MAIS DIVERTIDO DO ANO ATÉ AGORA!

https://microcorruption.com/

Na história, uma empresa de segurança criou um hardware de chave eletrônica. Você é um cracker que ligou um debugger na caixinha deles e vai quebrar a senha do sistema. Toda vez que você quebra uma senha, eles melhoram a segurança, e aí você vai lá quebrar de novo.

O jogo é extremamente realista. Ele te coloca um debugger real e você precisa usar seus skills de blackhat assembly para achar a falha de segurança. Sim, precisa saber assembly para jogar, mas a cpu é o MSP430 que tem o instruction set mais simples e ortogonal que conheço. Dá pra aprender on the fly, ou então você baixa o datasheet da web.

As primeiras fases são boi, o estagiário da empresa é tão naive que até compilou com -g haha. Depois a coisa vai ficando quente. Minhas dicas para o jogo são:

- Todo backdoor será encontrado.
- Todo buffer overflow será exploitado.
- Toda criptografia será quebrada.

Delícia de jogo, gostinho de adolescência. Fiz 110 pontos já, recomendo, Só tome cuidado porque vicia.

Novamente a brincadeira do artista, dessa vez o Girino Vey me indicou o Lacarmélio. Se você quer ganhar um artista, poste um comentário escrito MANDA.

O Lacarmélio faz parte do cenário artístico belo horizontino. Ao andar pela ruas da cidade, você sempre pode encontrá-lo numa esquina, com uma placa gigante anunciando "os gibis que ele mesmo faz". As histórias sempre envolvem o herói Celton explorando o folclore da cidade, usualmente explorando as lendas locais como a Loira do Bonfim e o Capeta do Vilarinho.

Em pelo menos um aspecto, ler o Celton é melhor que ler o Homem-Aranha: a geolocalização é muito mais familiar. Quando um nova iorquino está vendo o Homem-Aranha brigando com o Duende Verde em cima da ponte, ele reconhece naturalmente a ponte como sendo a ponte do Brooklyn, porque o habitante da cidade já passou por lá centenas de vezes. Já um leitor brasileiro não reconhece essa ponte com a mesma facilidade. 

Por outro lado, quando o Celton está atravessando uma ponte atrás de um motoboy em apuros, não é uma ponte qualquer, é o viaduto Santa Tereza, que todo belo horizontino conhece (se você já veio ao FIQ alguma vez, você também conhece).

Da mesma maneira, causou furor a história do Homem-Aranha encontrando o Obama em 2009. Mas o Celton já tinha encontrado o Aécio Neves e o Fernando Pimentel em 2007, no épico em duas partes "O Apocalipse de Belo Horizonte". Na trama, o traidor Joaquim Silvério dos Reis volta do inferno para ordenar que a capital de Minas volte a ser Ouro Preto. Enquanto o governador e o prefeito saem na porrada com diabretes do inferno, Celton volta no tempo para recrutar a ajuda do único herói capaz de vencer o vilão: Tiradentes.

O Lacarmélio também impressiona por ser um quadrinista totalmente independente. Os autores independente atuais costumam viabilizar suas obras usando crowdfunding no Catarse e stands em eventos como FIQ. Mas o Celton rejeita essa abordagem e aposta na venda direta nos faróis. E esse modelo de negócios funciona muito bem para ele, só com vendas de gibis ele conseguiu pagar o apartamento onde mora.

Mas, embora ele rejeite as abordagens de venda modernas, ele muito espertamente adota a análise baseada em Analytics. Em um dos seus primeiros gibis, Celton enfrentava uma sogra malvada. Ele recebeu diversas cartas de fãs dizendo que sogras também são gente e mereciam um tratamento melhor, então ele fez uma continuação onde Celton se alia a uma sogra boazinha.

Resultado: fracasso de vendas! A sogra malvada vendeu muito mais! Explorando os dados, ele construiu seu maior sucesso: O Combate da Sogra com o Capeta, onde a sogra morre, vai pro inferno, e briga com o Capeta porque nem ele a aguenta. As vendas estouraram, sendo o único número da revista com mais de dez reimpressões!

Reescrevi o toy static web server em Go. Está muito menor e mais legível!

https://github.com/ricbit/Oldies/blob/master/2014-01-webserver/server.go

E ainda ficou multi-threaded com esforço mínimo, e o mais legal, se você rodar o strace, dá pra ver que internamente ele usa o epoll ao invés de select.

Escrevi um toy static web server em C++11 idiomático, se alguém quiser dar pitaco:

https://github.com/ricbit/Oldies/blob/master/2014-01-webserver/server.cc

Aproveitando a deixa, terminei de ler o primeiro volume de histórias clássicas da Action Comics. Entre as histórias da segunda metade estão:

- Pivetada cometendo pequenos furtos, aí eles vão presos, mas o Superman arromba o camburão e tira eles de dentro, dizendo que criança precisa de escola e oportunidade, não de cadeia.

- Superman invade um presídio para acabar com as denúncias de maus-tratos e tortura de presos.

- Superman enfrenta um empresário que faz dinheiro vendendo ações de poços de petróleo improdutivos (LOL).

- Superman enfrenta os donos da indústria automobilística, que sabem que o carro que vendem tem defeito mas não fazem o recall.

- Superman enfrenta a máfia da central dos taxistas, que está intimidando e matando todos os taxistas que querem operar de forma independente sem se filiar à central.

O mundo não mudou muito, quem mudou foi o Superman, que ficou bem menos engajado.

Estava lendo uma entrevista do John Byrne, onde perguntam para ele qual lugar você gostaria de visitar, se você pudesse voltar no tempo. Ele respondeu que queria conhecer a Feira Mundial de NY em 1939.

A escolha é meio inusitada, mas depois de ler um pouco concordo que seria muito legal. A foto abaixo é o Kirby visitando a feira, e consta que todo o trabalho dele ao longo da vida era desenhar o que viu por lá. De fato, eu procurei umas fotos / imagens da época, e realmente dá para ver como muito virou inspiração para Asgard e o Fourth World:

http://www.sjsu.edu/faculty/wooda/nywf.html

Além disso, também foi na feira que lançaram o Superman #1. O tema da feira era "O Mundo de Amanhã", e não por acaso o Superman ficou conhecido como Man of Tomorrow nessa época.

Jogando aqui o Assassin's Creed 4 que ganhei de natal da Ila Fox. Está bem melhor que o terceiro, e eu acho que é porque mudaram um pouquinho a fórmula: ao invés de ser um Assassin's Creed que se passa na época dos piratas, está mais para um jogo de piratas que se passa no universo do Assassin's Creed.

Mas o post é só para falar que a parte mais legal do jogo é que você pode colecionar músicas de piratas! A minha preferida é a do video abaixo, tente ouvir e imaginar um pirata em cima de um barril de rum:

http://www.youtube.com/watch?v=Y6B3fLPH1h0