thegoodfellas/blogset-br huggingface dataset:
mao. Na epoca eu era viciado, gostava tanto que ate cheguei a portar esse gerador para Pascal ja na epoca dos PCs.Ja na revista MSX Micro #15, de maio de 88, um desafio mais dificil foi proposto pelo Nabor Rosenthal: escrever um programa de computador que resolva sozinho os criptogramas!Como fazer um programa assim? Existem tres abordagens imediatas. A primeira e usar forca bruta para enumerar todas as combinacoes entre letras e numeros. Cada uma das 8 letras pode assumir 10 valores distintos, entao o tamanho do espaco de estados e 8**10 = 1073741824 combinacoes.A segunda abordagem e notar que duas letras nao podem ter o mesmo numero, entao voce nao precisa visitar todos os estados, so aqueles que contem permutacoes dos oito digitos escolhidos. Assim, o espaco fica apenas com binomial(10, 8)*fatorial(8) = 1814400 combinacoes, quase mil vezes menor que o anterior.A terceira e usar backtracking para eliminar da arvore de busca as combinacoes invalidas. Por exemplo, se voce ja determinou que D=7 e E=5, entao Y precisa necessariamente ser 2 porque e a unica possibilidade que faz a ultima coluna ficar correta. Essa opcao e mais complicada de implementar, mas e ainda mais rapida que a anterior.Nesse ano eu fiz um curso de Discrete Optimization no Coursera, e aprendi um metodo novo para resolver criptogramas. Porem, antes de explicar esse metodo novo, vale a pena fazer uma pausa para estudar um problema mais simples.O problema da dietaEnquanto o dinheiro do pai nao chegava, o estudante estava dormindo de hospede numa fazenda da regiao. Embora ele nao pagasse nada para dormir no celeiro, ele ainda tinha que comprar comida. E so tinham tres comidas disponiveis para comprar: espigas de milho, paes e copos de leite. Dado que ele precisa de pelo menos 2000 calorias por dia, e 5000 unidades de vitamina A, qual e o menor custo diario que ele pode ter para conseguir todos os nutrientes que precisa?PorcaoCalorias (kcal)Vitamina A (IU)PrecoEspiga de milho72107$ 0.08Copo de leite121500$ 0.23Pao650$ 0.05Esse problema pode ser expresso atraves de uma serie de inequacoes:Na literatura, problemas com esse formato sao estudados em Programacao Linear, e existem varios algoritmos eficientes para resolve-los, como os metodos de Ponto Interior, que podem ser implementados de forma a garantir uma solucao em tempo polinomial. Na pratica, usa-se mais o Simplex, que tem um pior caso ruim, mas tambem e polinomial no caso medio.Usando essas tecnicas para resolver o problema, temos que a melhor solucao e comprar 17.13 espigas e 6.33 copos de leite, gastando um total de $2.82.Mas agora tem um problema: eles nao vendem 17.13 espigas, a quantidade precisa ser um inteiro. Ou voce compra 17 espigas, ou compra 18. Facil de resolver, e so arredondar para cima ne? Leva-se 18 espigas e 7 copos de leite, gastando $3.05, e garantindo todos os nutrientes que voce precisa.Porem, se voce fizer isso, voce vai perder dinheiro! Pode conferir: se voce comprar 10 espigas, 8 copos de leite, e 5 paes, vai gastar so $2.89, e continuar garantindo o minimo de nutrientes diarios. Os metodos de programacao linear nao funcionam quando
programa completo voce pode ver no github. Rodando o programa, ele retorna a solucao que esperavamos:Corn: 10Milk: 8Bread: 5Agora ja temos as ferramentas que precisavamos para resolver o problema original!Criptoaritmetica com MIPMIP e uma ferramenta excelente para resolver puzzles. Tudo que voce precisa fazer e arrumar uma maneira de transformar seu puzzle em um sistema de inequacoes; feito isso, o framework faz todo o servico sujo para voce.O problema entao deixa de ser programacao e passa a ser modelagem. Qual o melhor modelo que representa seu puzzle? Um truque que funciona na maioria das vezes e introduzir variaveis binarias que codificam as informacoes do seu puzzle.Por exemplo, a letra S vai ser associada a um dos digitos de 0 a 9, mas ainda nao sabemos qual. Vamos entao introduzir dez variaveis binarias: bS0, bS1, .., bS9. Cada uma deles pode assumir o valor 0 ou 1. Por exemplo, se na solucao final descobrirmos que S=9, entao teremos bS9=1, e as outras nove variaveis sao zero.Mas sabemos que a letra S precisa estar associada a um digito, e nao mais que um. Isso pode ser expresso como a nossa primeira equacao:Confira: para a equacao ficar correta, se uma das variaveis for 1, entao todas as outras precisam ser 0. (Os mais atentos podem reclamar que eu usei uma equacao ao inves de uma inequacao, mas nao tem problema; toda equacao da forma A=k pode ser escrita como duas inequacoes encadeadas: k A k).Repetindo uma equacao dessas para cada letra, nos garantimos que a cada letra corresponde um digito. Mas isso nao e suficiente, voce tambem precisa garantir o oposto: a cada digito precisa corresponder uma letra. Sem essa condicao adicional, voce poderia ter uma solucao do tipo S=9 e E=9 (mas nao podemos ter o mesmo digito em duas letras distintas).A solucao e parecida com a anterior. Para o digito 9, por exemplo, teremos:Note que temos apenas oito letras distintas para dez digitos, entao pelo menos dois digitos vao sobrar. Como nao temos como garantir qual digito sera utilizado, usamos uma inequacao ao inves de uma equacao.Outra regra que precisa ser modelada e que nenhum numero pode comecar com zero. Isso e o mesmo que dizer que as letras S e M nao podem ser zero. Mais duas equacoes resolvem isso:Agora falta so modelar a soma em si. Antes de comecar, vale notar que o problema tem quatro variaveis binarias escondidas que voce precisa levar em conta: os carrys de cada coluna.Agora basta escrever uma equacao por coluna. Para a coluna mais a direita, por exemplo, teriamos algo do tipo D+E=Y+10c0 em decimal. Usando as nossas variaveis binarias, a equacao completa fica:Parece assustador, mas e so uma equacao linear simples. Fazendo mais uma dessas para cada coluna do nosso puzzle, o modelo esta quase completo: falta so uma funcao objetivo. Se vamos usar MIP, precisamos minimizar alguma coisa. Mas o que minimizar? Nosso modelo ja esta completo sem a necessidade de minimizar nada, entao podemos fornecer uma funcao constante para ele minimizar. Na linguagem da area, nos estamos buscando feasibility, e nao optimality.Com
todas as inequacoes prontas, podemos rodar o modelo no EasySCIP. O codigo completo esta no github, e, apos roda-lo em meu computador, tive a resposta em 0.116s, o que e bastante respeitavel! Mas ainda da para melhorar :)Criptoaritmetica com MIP, segundo modeloEu sei que gostar de resolver criptoaritmetica parece coisa da maluco, mas eu nao sou o unico maluco nesse mundo, tem o Knuth tambem! No volume 4A do Art of Computer Programming, ele da uma dica muito boa para resolver criptogramas: a analise das assinaturas. Vamos isolar a letra E no puzzle original, trocando os lugares onde ela aparece por 1, e onde nao aparece por 0: Apos a substituicao, nos obtemos a assinatura da letra E, que vale 100+1-10, ou seja, 91. A sacada do Knuth e que, na solucao final, a soma das assinaturas precisa necessariamente valer zero:Usando variaveis inteiras ao inves de variaveis binarias, poderiamos colocar essa equacao diretamente no modelo, e ai nao precisariamos das equacoes de cada coluna! Mas podemos fazer ainda melhor: o MIP sempre quer uma funcao para minimizar, entao podemos mandar ele minimizar a soma das assinaturas. Assim, os metodos de branch and bound implementados pelo SCIP podem jogar fora mais nos da arvore durante o processamento, o que acelera a busca.O unico problema e ele resolver minimizar tanto a soma das assinaturas, que ela acabe ficando negativa. Para evitar isso, e so adicionar essa restricao manualmente. Por exemplo, ele pode minimizar a variavel X, onde X satisfaz:Ainda precisamos adicionar as regras de que a cada letra corresponde um unico digito e vice-versa. Vamos manter as variaveis binarias do modelo anterior, e ensinar o modelo a converter entre variaveis binarias e variaveis inteiras. Por exemplo, a letra D ficaria:Com isso o modelo esta completo. O codigo esta no github, e rodando no EasySCIP, ele chega no mesmo resultado que o modelo anterior, porem usando apenas 0.052s, quase metade do tempo!ConclusaoQuando eu devo usar MIP ao inves de outros metodos, como backtracking? O backtracking vai criar uma divisao na arvore de busca cada vez que definir o valor de uma variavel, mas o MIP roda uma iteracao de programacao linear em cada no, o que potencialmente pode definir varias variaveis ao mesmo tempo. A minha experiencia e que o MIP ganha sempre que voce conseguir criar um modelo que permita essa otimizacao global.Como comparacao, lembre que a forca bruta examinava 1073741824 nos, e a analise de permutacoes visitava 1814400 nos. Olhando no log do EasySCIP, eu vejo que o primeiro modelo com variaveis binarias visitou apenas 9 nos, e o segundo modelo com assinaturas resolveu tudo em um unico no! A programacao linear achou a solucao inteira sem nenhum branch! Pelos numeros, e bem claro que vale a pena aprender a escrever modelos MIP :)
MathJax.Hub.Config({ tex2jax: { inlineMath: [ [String.fromCharCode(35)+String.fromCharCode(35),String.fromCharCode(35)+String.fromCharCode(35)]], processEscapes: true } });Se voce trabalhar por tempo o suficiente com Computacao, eventualmente uma das suas atribuicoes vai ser entrevistar candidatos para a sua equipe. Entrevistar e uma arte: existem inumeros truques e macetes paradescobrir se e esse sujeito na sua frente e mesmo o cara que voce quer como seu parceiro. O Joel tem uma boa introducao sobre o tema que vale a pena ler.Uma das habilidades que voce precisa desenvolver rapido e aprender que o candidato nao pensa como voce. Em especial, quando ele responde uma pergunta de um jeito diferente daquele que voce esperava, nao quer dizer necessariamente que ele esteja errado. E esse caso eu ja vi de perto, com o algoritmo que eu apelidei de Busca Por Bozo Binario.Essa historia aconteceu faz algum tempo. Eu estava na cantina conversando sobre entrevistas, quando alguem comentou que rejeitou um candidato porque ele nao conseguiu implementar uma busca binaria. Poxa, isso e grave mesmo! E qual o algoritmo errado que ele fez? A resposta foi essa: "Sorteie um numero de 1 ate o tamanho do vetor, e verifique o elemento que tinha esse indice. Se for igual voce achou, entao retorna. Se for menor, repete para o lado esquerdo; se for maior, repete para o lado direito."Isso e errado, me disseram, porque o pior caso e ##O(n)##. De fato, se o elemento que voce quer achar e o primeiro, e o gerador de aleatorios retornar sempre o ultimo, ele vai passar pelo vetor inteiro.Mas nesse ponto eu tive que interromper: "Perai! Voce explicitou que queria ##O(\log n)## no pior caso? Se voce nao falou nada no enunciado, ele pode ter entendido que era ##O(\log n)## no caso medio, e ai o algoritmo dele esta certo!"Na hora ninguem botou fe que esse algoritmo de Busca por Bozo Binario era de fato ##O(\log n)##, entao eu tive que voltar para casa e escrever a demonstracao. Se voce tem medo de Matematica Discreta, pule a caixa azul:Para a Busca por Bozo Binario, nos queremos calcular qual e o valor medio do numero de comparacoes que ele realiza. E como voce comeca uma analise de caso medio? Primeiro voce define as caracteristicas da entrada: eu vou assumir que todos os casos estao distribuidos uniformemente. Depois, e so usar a formula do valor esperado: voce soma o numero de comparacoes em cada caso, multiplicado pela probabilidade daquele caso ocorrer.$$ F[x] = \sum_i p[i]C[i] $$Antes de comecar, vejamos os casos extremos. Quando o vetor e vazio, nao precisa de nenhuma comparacao, entao ##F[0]=0##. Se o vetor tiver tamanho um, entao so precisa de uma comparacao, ##F[1]=1##. E sempre bom ter uns casos pequenos para conferir no final.Vamos ver agora o caso de um vetor de tamanho ##n##. Eu nao sei qual numero vai ser escolhido para cortar o vetor em dois, e o gerador de numeros aleatorios que escolhe. Entao eu vou tirar a media sobre todas as escolhas possiveis. Como os ##n## valores sao equiprovaveis, entao a probabilidade individual e ##1/n##:$$F[n] = \sum_{0\le k\lt n}\frac{1}{n}F[k,n] = \frac{1}{n}\sum_{0\le k\lt n}F[k,n]
\le n} \frac{6}{k+1} - 2H[n] \right)\\\end{align*}$$O primeiro somatorio precisa de um pouco de massagem:$$\begin{align*} \sum_{1\le k \le n} \frac{6}{k+1} &= \sum_{1\le q-1 \le n} \frac{6}{q} \\ &= \sum_{2\le q \le n+1} \frac{6}{q} \\ &= -6+\frac{6}{n+1}+6\sum_{1\le q \le n} \frac{1}{q} \\ &= -6+\frac{6}{n+1}+6H[n] \\\end{align*}$$Por fim:$$\begin{align*} F[n] &= \frac{n(n+1)}{2n^2} \left( \sum_{1\le k \le n} \frac{6}{k+1} - 2H[n] \right)\\ F[n] &= \frac{n(n+1)}{2n^2} \left( -6+\frac{6}{n+1}+6H[n] - 2H[n] \right)\\ F[n] &= -3 +\frac{2(n+1)}{n}H[n]\\\end{align*}$$Ufa, deu trabalho! E isso e ##O(\log n)## mesmo? Bem, podemos verificar usando um assintotico para o harmonico, por exemplo:$$ H[n] = \ln n + \gamma + O(1/n) $$Agora voce substitui:$$\begin{align*} F[n] &= -3 +\frac{2(n+1)}{n}H[n]\\ &= -3 +2H[n] +\frac{H[n]}{n} \\ &= -3 +2\ln n +2\gamma +O(1/n)+ 2\frac{\ln n}{n}+2\frac{\gamma}{n}+O(1/n^2) \\ &= 2\ln n + O\left(\frac{\ln n}{n}\right) \\ &= O(\log n)\end{align*}$$Como queriamos demonstrar!Ou seja, realmente a Busca por Bozo Binario e ##O(\log n)##. Em demonstracoes grandes assim eu sempre gosto de fazer uma simulacao por Monte Carlo para conferir as contas. A minha simulacao esta no github:Busca por Bozo Binario, simulacao por Monte CarloSimulando 50000 vezes em um vetor de tamanho 3000, o numero medio de comparacoes foi de ##14.1769##. O valor teorico previsto pela formula e de ##14.1732##, nada mau!Eu tambem fiz uma simulacao da busca binaria tradicional como comparacao. Com os mesmos parametros, a busca tradicional usou ##10.6356## comparacoes no caso medio, ou seja, foi mais eficiente que o Bozo Binario. Por que isso acontece? Analisando o assintotico fica claro. Para ##n## grande, o valor medio da Busca por Bozo e de ##2 \ln n## (logaritmo natural), enquanto que na busca binaria e ##\log_2 n## (logaritmo de base 2). Entao, em media, esperamos que Bozo Binario seja mais lento por um fator de:$$\begin{align*}\frac{2\ln n}{\log_2 n} &= {2\frac{\log n}{\log e}} \div {\frac{\log n}{\log 2}} \\ &= 2\frac{\log n}{\log e} \times \frac{\log 2}{\log n} \\ &= 2\frac{\log 2}{\log e} \\ &= 2\ln 2 \\ &\simeq 1.386\end{align*}$$Ou seja, mais ou menos uns 38% mais lento, o que bate com a simulacao.Depois da analise do algoritmo, a duvida que resta e: e o candidato? Bem, se fosse eu a entrevistar, precisaria coletar mais dados para saber se ele realmente sabia do tempo medio, ou se estava perdido e implementou a primeira coisa que veio na cabeca. Um possivel follow-up e "Certo, esse metodo e mais complicado que a busca binaria tradicional, mas funciona. Voce pode me falar alguma situacao onde ele e preferivel sobre o tradicional?". Curiosamente, existe sim um caso onde a Busca por Bozo Binario e melhor que a busca binaria tradicional! Mas esse caso fica para a proxima :)
Todo mundo ja ouviu a historia de que foi Colombo que confirmou que a Terra era redonda, e que antes dele as pessoas achavam que a Terra era plana. Porem, isso e um mito! Desde a epoca dos gregos ja se sabia que a Terra e redonda.Mesmo para os povos antigos as evidencias eram faceis de serem encontradas. Por inducao, se o Sol e redondo e a Lua e redonda, por que a Terra nao seria? Mais diretamente, durante um eclipse lunar, e possivel ver claramente que a sombra projetada pela Terra e redonda.Nem mesmo a Igreja disputava essa interpretacao. Santo Agostinho, por exemplo, sabia que a Terra era esferica, embora nao acreditasse que houvesse gente morando do outro lado do globo. Sao Tomas de Aquino comeca a sua Summa Theologica citando duas diferentes demonstracoes de que a Terra e redonda."Mas e aquela historia de que os marinheiros da epoca tinham medo de cair pela borda da Terra?" Bem, para quem nao entende como a gravidade funciona, e possivel ter esse medo mesmo com a Terra sendo redonda! Se a gravidade puxa sempre para baixo, entao voce cai quando chega no Equador:Aparentemente, todo esse mito comecou com a publicacao de "As Vida e as Viagens de Cristovao Colombo", que voce pode ler integralmente no Google Books. O livro realmente cita que o senso comum era de que a Terra era plana. O problema e que todo mundo achou que esse era um livro de historia, quando na verdade era ficcao! (Conclui-se, portanto, que o autor desse livro foi um precursor do The Onion).Hoje em dia ainda ha quem acredite que a Terra e plana, desde os ingenuos que nunca tiveram acesso a educacao, ate os malucos que formam seitas como a Sociedade da Terra Plana. Talvez voce conheca alguem assim. Na verdade, e bem possivel que voce acredite na Terra Plana. Sim, voce que esta lendo esse texto!Se voce acha que nao acredita na Terra plana, entao tente responder o meu teste: Suponha que voce esta usando um estilingue para arremessar passarinhos em porquinhos. Na ausencia de atrito com o ar e outras formas de perdas dissipativas, qual a curva que o passarinho descreve em seu trajeto?Se voce respondeu que a curva e uma parabola, surpresa! Voce acabou de assumir que a Terra e plana!"Mas perai! Como assim?! Foi isso que meu professor ensinou!". Pois e, sempre e bom ter uma dose de ceticismo quando te ensinam alguma coisa. Na verdade, a prova de que a trajetoria e uma parabola requer a existencia de uma forca gravitacional do tipo F=mg, onde g e uma constante de aproxidamente 9.81 m/s2.A pegadinha e que esse g nao e uma constante! Ele varia com a altura, e, levando isso em conta, a curva nao e mais uma parabola. Porem, se voce assumir que a Terra e um plano infinito, ai sim a curva e uma parabola, porque nesse caso g e uma constante independente da altura.E como provar que o g e realmente constante para uma Terra plana? Existem varias maneiras: se voce souber um
pouco de calculo, pode usar o metodo do guerreiro, que envolve varias paginas de lutas contra integrais duplas. Se voce for um mestre do calculo, pode tentar o metodo do mago, que resolve com poucas contas, mas requer o uso de teoremas magicos. Agora, se voce nao souber calculo, o jeito e apelar para metodo do clerigo: acredite em mim e pule o quadro azul abaixo :)O Metodo do GuerreiroAntes de comecar, convem lembrar a lei da gravidade de Newton, que e proporcional as massas e inversamente quadratica com a distancia entre elas:Como a lei tem simetria radial, as contas ficam mais faceis se explorarmos essa simetria. Vamos calcular qual e a atracao gravitacional causada por um disco de raio R e espessura infinitesimal, composto de materia uniforme com densidade , sobre um passarinho de massa mP que esta a uma altura h.Nos vamos picotar o disco em pedacinhos de massa dm e integrar sobre todos os pedacinhos. Como as dimensoes de cada pedacinho sao infinitesimais, entao eles podem ser considerados pequenos retangulos, onde um dos lados vale dr, e o outro vale um pequeno comprimento de arco. Um comprimento de arco e igual ao raio vezes o angulo, logo esse lado vale r.d . A massa do pedacinho, entao, e a densidade vezes a area: .r.dr.d.Alem disso, se eu tenho o raio r e a altura h, por Pitagoras eu sei quanto vale d2. A forca total sobre o pedacinho e:Antes de continuar, vamos decompor a forca total em componentes radial (Fr) e vertical (Fh). Agora a simetria do problema se mostra util, basta notar que para cada dm, tem um outro dm numa posicao simetrica, do outro lado do disco; e nesse dm espelhado, o Fr vai ter o mesmo modulo e direcao, mas sinal oposto. Entao todos os Fr vao cancelar, e a forca total sobre o passarinho vai ser apenas a soma dos Fh de cada dm.E quanto vale o Fh? E a forca total F vezes o cos , que por sua vez e o lado adjacente pela hipotenusa. Logo:Para calcular o Fh total, e so integrar para o variando de 0 a 2, e para o r variando de 0 a R:Todo mundo e constante em relacao a , entao da pra jogar pra fora, e a integral em d fica simples:Para continuar, uma mudanca de variavel:O meio joga pra fora e cancela com o dois, o resto e um monomio simples, para integrar voce soma um no expoente e passa dividindo:A ultima expressao e a formula final da forca gerada por um disco uniforme. Por fim, basta notar que o plano e o limite do disco quando o raio vai para o infinito:Se o R vai para o infinito, entao a primeira fracao vai para zero, logo:Nos estamos interessados no caso em que h e positivo, logo a fracao simplifica e chegamos na forma final da forca devida a um plano:Como esperado, a forca F nao depende da altura h!O Metodo do MagoAo inves de usar a lei da gravidade de Newton, podemos usar a
lei da gravidade de Gauss, que diz que a integral do campo gravitacional sobre uma superficie fechada e proporcional a massa contida dentro dela: Essas duas leis sao equivalentes, pode-se usar uma para provar a outra. Mas em alguns casos a lei de Gauss e mais pratica, especialmente se voce puder bolar uma superficie que explore as simetrias do problema. No nosso caso, a superficie magica e um cilindro centrado no plano, com as bases paralelas a ele:Antes de mais nada precisamos da massa dentro da superficie. Vamos chamar a area da base do cilindro de A. Como o plano tem densidade , entao a massa dentro da superficie fechada e M = A..Nos ja vimos antes que, pela simetria radial, todas as forcas resultantes sao perpendiculares ao plano. Na lateral do cilindro, todos os elementos de area dA sao normais a lateral, logo sao perpendiculares as forcas, e portanto o produto escalar deles da zero.Alem disso, tambem ha uma simetria em relacao a translacoes no plano, por isso todas as forcas atuando a uma mesma altura sao iguais entre si. Dessa maneira, a integral de superficie em cada base do cilindro vale esse valor constante (chamemos de F) vezes a area A.Juntando tudo, temos:Esse e o mesmo resultado do metodo anterior, mas com bem menos contas!Mas se na Terra redonda a curva nao e uma parabola, entao que curva ela e? Bem, se voce assumir que a Terra e uma esfera perfeita, homogenea, sem campos magneticos, e assumir que nao ha atrito com ar e que ninguem esta girando, entao a curva correta e uma elipse.Para quem leu o Principia, este e um resultado intuitivo. Na Proposicao 71 do Livro 1, o Newton demonstra que a forca resultante da atracao por uma esfera homogenea e a mesma forca de quando voce concentra toda a massa da esfera num ponto material em seu centro. Dai o problema se reduz a atracao entre dois pontos materiais, que sabemos ser uma elipse.Esse raciocinio tambem serve para responder a uma duvida comum da criancada: se a gravidade da Terra puxa tudo para o centro, por que os satelites entram em orbita ao inves de cair? A resposta mais imediata e que na verdade tudo que voce joga pra cima entra em orbita, mas algumas orbitas sao tao excentricas que o objeto bate de volta na superficie da Terra.Eu nao gosto muito da maneira que ensinam Fisica no Brasil (o Feynman tambem nao). Felizmente, hoje em dia voce sempre pode remediar a sua formacao usando os recursos online, como a Wikipedia e a Khan Academy!