Em 2001 eu fui ao Theatro Municipal de SP assistir ao vivo Also sprach Zarathustra, do Strauss. A data era propícia, todo mundo conhece o primeiro movimento dessa sinfonia porque ele foi usado como tema do filme 2001: a space odyssey.

Mas o que me surpreendeu não foi o primeiro movimento, foram os seguintes. Eu nunca tinha ouvido o resto da sinfonia, e tudo que me vinha à mente era "pombas, estou ouvindo a trilha sonora do Superman"!

De fato, o John Williams nunca começa uma trilha sonora do zero, ele sempre pega alguma obra clássica que encaixa tematicamente e usa como starting point. Zarathustra é baseado no livro homônimo do Nietzsche que fala sobre o übermensch, então tematicamente tem tudo a ver com Superman.

O mesmo acontece com Star Wars. Se você fosse escolher uma obra clássica como ponto de partida, qual você escolheria? Os Planetas, do Holst né? Cada movimento da obra é sobre um dos planetas, e o John Williams se baseou na melodia de Marte. Afinal, Marte é o deus da guerra, então tematicamente tem tudo a ver com Star Wars.

Pode conferir:

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

Os primeiros vinte segundos são a Marcha Imperial. Em 1:10 é o tema do Luke. Mas pra mim a parte mais similar o finalzinho. Avança até 6:55 para ouvir o final da música, e depois vai nesse video aqui, que é a destruição da Death Star. Em 3:20, é a praticamente a mesma música!

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

Quando criança eu não notava nada disso, mas eu imagino que essas ligações deveriam ser óbvias para quem entende de música erudita. 

E se alguém souber qual é a inspiração do tema do Jurassic Park, me avisa porque esse eu nunca descobri 

Povo fala que você não pode revisitar as coisas que você assistia quando criança, mas eu gosto, porque eu deixo de ver como consumidor e vejo como criador.

Por exemplo, hoje eu vi um episódio de Jiraiya. Quando eu era criança, tinha uma música da trilha sonora que eu achava bizarra, que era essa aqui (começa em 00:20):

http://www.youtube.com/watch?v=Yg3wT57RJnU&list=PLszyJ9jJYLMu3CNRETmRzZx7HNACLR2rr#t=24

Em princípio era para ser o tema dos corvos-ninja assassinos, mas não fazia sentido para mim. Por que colocaram um música de circo como tema de um ninja assassino?

A resposta é simples, eu era criança e ignorante, não tinha entendido a proposta do compositor! A música que eu achava que parecia de circo, na verdade era inspirada nessa aqui -> http://goo.gl/4Tq4CO

Quando você entende o contexto, tudo faz sentido!

(Isso também se aplica a 90% das trilhas do john williams, prestando atenção dá pra ouvir direitinho de onde ele tirou a inspiração de cada uma).

No shopping Boulevard em BH tem um arcade da Dona Barata! Apesar de ter projetado esse arcade, eu nunca tinha visto um de perto!

Por volta de 2003, o que estava bombando era o DDR. Nessa época, tinha um fábrica nacional era que especializada em importar placa de street fighter e montar o gabinete por aqui, e eles queriam entrar na onda no DDR também. Então eles foram até a USP perguntar se alguém por lá saberia projetar um clone. Acabou que o projeto caiu na mão da minha equipe, e o plano era fazer um DDR-light para crianças, você tinha que pisar em baratinhas que acendiam no chão.

Eu fiquei com dois pedaços do projeto: a lógica do jogo e o subsistema de som. Cada um tem uma anedota :)

Para a lógica do jogo, nós escolhemos uma variante do 8051 que tem tudo num chip só: cpu, ram, rom e i/o. O código eu fiz todo no assemblão mesmo, mas a dificuldade era: como testar? Não tinha emulador, então o único jeito de testar era gravando a eprom do chip e plugando na placa.

Mas que desperdício né? Queimar um chip a cada teste! Foi aí que a gente teve uma idéia muito boa. Internamente, a eprom tem todos os bits setados em 1, o processo de queimar o código nela deixa os bits 1 como estavam, e queima os bits 0 de maneira permanente. Mas o jogo inteiro era pouco menos de 1kb, e a eprom interna era maior que isso (32kb se minha memória não falha).

A solução foi olhar na tabela de opcodes do 8051 e notar que o NOP codifica como 00! Então quando eu queria testar o código, era só preencher 1kb de NOPs na frente do código, assim eu podia reutilizar o mesmo chip. A única diferença é que demorava alguns microsegundos a mais no boot para percorrer todos os NOPs no começo até chegar no código. Com isso conseguíamos usar o mesmo chip 32 vezes :)

O subsistema de som foi divertido também. Para o som rodar em paralelo com o 8051, decidimos fazer um chip dedicado só pra isso (eu implementei o chip em vhdl e na placa ele era uma fpga). O problema era a rom, para ficar barato eu tinha que enfiar a trilha sonora inteira dentro de 1MB, então tinha que rolar uma compressão bonita.

Depois de quebrar a cabeça um pouco, eu consegui bolar um algoritmo para comprimir a música. Eu levei o sample pro gerente ouvir, e o diálogo foi mais ou menos assim:

- Ficou muito boa a qualidade, Ricbit! Que método você usou?
- ADPCM de 5 bits.
- Não, peraí. Eu sou engenheiro de áudio faz anos, eu SEI que não dá para fazer essa qualidade com 5 bits. Pode falar a verdade, qual método você usou?
- ADPCM de 5 bits.

E realmente era ADPCM de 5 bits! Mas eu usei um truque. :)

O DAC na saída era uma rede R2R de 12 bits, mas eu usava só 5 bits por vez. A cada 10ms eu media a potência na saída, e escolhia só os 5 bits mais altos desse trechinho de audio. Isso introduz ruído de quantização, mas na prática o ouvido humano faz mascaramento, então você não ouve esse ruído. É o mesmo método de compressão com perdas que o mp3 usa, só que de um jeito mais fácil de implementar em hardware.

No fim nós entregamos o projeto pronto e eu nunca cheguei a ver como ficou montado, hoje foi a primeira vez. E ainda tive a oportunidade de ver uma menina de 8 anos brincando no arcade, então eu sei o jogo deve ter ficado divertido :)

Começou nessa semana a segunda turma de Discrete Optimization no Coursera. Eu normalmente já recomendaria, mas dessa vez é especial porque eu ajudei a fazer esse curso!

https://www.coursera.org/course/optimization

Background: Ano passado teve a primeira turma do curso, eu me inscrevi e foi excelente. O formato é diferente dos tradicionais videos-com-quiz: o curso é formado de seis exercícios NP-completos, sua tarefa é resolvê-los em 9 semanas. Os seis problemas são: knapsack, graph coloring, traveling salesman, facility location e vehicle routing, ou seja, só pedreira.

Cada problema tem seis instâncias, você precisa escrever um script que roda localmente na sua casa e submeter só a solução. Para o algoritmo, vale tudo, você escolhe a linguagem e a abordagem que quer usar. Os videos do curso são tutoriais das abordagens possíveis, todos eles são liberados no day-one e você assiste na ordem que quiser. Eu me diverti um monte no ano passado, e acabei terminando o curso com distinction.

Pois bem, depois de acabar o curso, o professor mandou um email para todos que terminaram com distinction perguntando quem tinha alguma idéia para melhorar o curso, e eu tinha uma idéia muito prática.

Programar simulated annealing é mole, qualquer um faz. Mas alguns dos algoritmos propostos são mais difíceis. Para o MIP, por exemplo, precisaria de um curso inteiro para aprender a fazer do zero. Por isso, a recomendação é procurar uma lib pronta por aí e focar no modelo ao invés da implementação. Mas as libs prontas são muito difíceis de usar, com apis horrorosas! E mesmo que um aluno aprenda a usar a api, o conhecimento não passa para os outros, porque o code of conduct não permite compartilhar código entre os alunos.

Então a minha sugestão foi: (1) escrever uma lib mais fácil de usar, e (2) fazer um sétimo exercício open source, que não vale pontos e é feito justamente para os alunos trocarem entre si o conhecimento aprendido. O professor gostou da idéia, e essa turma já está usando esse modelo!

A lib eu mesmo fiz: o EasySCIP, que é um binding em cima do SCIP. Até escrevi um post no ano passado sobre ela:

http://blog.ricbit.com/2013/12/mande-mais-dinheiro-usando-mip.html

O professor criou o sétimo exercício, que é weighted set cover. O curso tem um github oficial, e a idéia é os alunos forkarem e colocarem seus códigos no fork. Assim qualquer um pode entrar na lista de forks e aprender com as soluções dos colegas:

https://github.com/discreteoptimization/setcover

Recomendo demais esse curso, aprendi um monte com ele.

Eu ia fazer um comentário, mas nem precisa.

Matemática Discreta com Patos.

http://www.amazon.com/Discrete-Mathematics-Ducks-Sarah-Marie-Belcastro/dp/1466504994

Esse app parece interessante. A idéia deles é que o quando você está lendo, seu cérebro está fazendo duas tarefas distintas: uma é identificar a palavra, e outra é movimentar o olho até a próxima palavra. 

Ao invés disso, a alternativa do app é mostrar uma palavra por vez, no mesmo lugar, eliminando completamente o movimento do olho. Para isso funcionar, tem que ser com uma fonte especial (arial-like), e um alinhamento especial das palavras na horizontal, que varia de palavra por palavra. Além disso, eles variam o tempo de exposição por palavra, e quando a palavra é muito comprida eles quebram em pedaços de uma forma inteligente.

No site tem um gif animado, eu consegui ler 500 wpm de boa. Eles dizem que com treino dá pra chegar a 1000 wpm. Se isso funcionar mesmo finalmente eu vou ler mais rápido que o Lucas Radaelli 

http://www.33rdsquare.com/2014/03/app-set-to-dramatically-increase-your.html

Eu já contei que foi por causa do Robocop que eu virei engenheiro? 

A história é assim: lá no finzinho da década de 80 nós éramos um grupinho de três amigos decidindo o que fazer da vida. A gente já tinha decidido fazer o curso técnico, só faltava escolher a área.

Aí nós assistimos o filme e ficou decidido: nosso objetivo de vida era fazer o Robocop! E o que precisávamos para fazer o Robocop? Dividimos as tarefas: um iria fazer eletrônica, um iria fazer mecânica, e outro iria fazer computação.

Mas em certo ponto nós notamos que faltava uma parte importante: para fazer o Robocop, a gente iria precisar de um cadáver. Eu pensei um pouco e logo resolvi o problema. Chamei de canto meu irmão, quatro anos mais novo, e perguntei:

- Nós estamos com um plano para transformar alguém no Robocop. Você quer virar o Robocop?
- NOSSA QUE LEGAL EU QUERO
- Você vai ter que morrer, mas depois a gente te traz de volta como Robocop, tudo bem?
- EU VOU VIRAR O ROBOCOP QUE LEGAL

No fim o plano falhou miseravelmente. Eu fiz o técnico em eletrônica e depois engenharia elétrica, mas trabalho com computação. Um dos amigos fez o técnico em mecânica, mas não curtiu, e acabou se formando em arquitetura. O outro amigo estudou computação, mas hoje trabalha como sales engineer na microsoft. E o meu irmão, que ia ser o cadáver, tá aí vivo até hoje.

Gostei muito do Robocop novo, fica ainda mais legal quando você percebe que os personagens são o Steve Jobs e o Nicolelis. E eles não estão vendendo soft drinks haha.

Na primeira vez que eu peguei para ler o Quantum Mechanics and Path Integrals do Feynman, eu não entendi porra nenhuma. Mas agora eu peguei de novo para ler e entendi até a página 27! Eu progredi, agora faltam só as outras 350 páginas!

O auto corretor ortográfico quer tirar o acento da minha idéia. Fuck the system, a idéia é minha e eu que decido quantos acentos ela tem.

Que tipo de nerd você é? Achei um jeito fácil de descobrir.

Vai no google e digita "wol" no campo de pesquisa

Se auto completar com "wolfram alpha", você é do tipo 1. Se auto completar com "wolverine", você é do tipo 2.

Ontem eu li o paper original do Weierstrass com a definição original do método do epsilon-delta. É bem acessível, recomendo a leitura! E ainda permite codificar isso:

O duelo do Luke e do Vader no Episódio 5 é legal porque é o único desigual da série. Todas as outras lutas são mestres contra mestres, mas esse é adulto versus pirralho. O Vader desarma o Luke em 30s usando uma mão só, e só não mata o pivete porque queria levá-lo vivo para o Imperador.

(Mas a melhor trilha sonora é o Duel of the Fates no episódio 1.)

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: