As Figurinhas dos Vingadores são Honestas? (parte 2)

No último post do blog, eu comprei vários pacotinhos de figurinhas dos Vingadores, para tentar responder à pergunta: as figurinhas são honestas? Após fazer dois testes de hipótese, eu concluí que as figurinhas possuem distribuição uniforme, então parece que sim. Mas tem uma pegadinha: para serem honestas, garantir que são uniformes não é o suficiente, ainda tem outro teste que precisamos fazer!

A Distribuição dos Pacotinhos

Para fazer a análise das figurinhas, eu comprei 106 pacotinhos na banca. Mas enquanto eu abria os pacotinhos, notei uma propriedade curiosa: todos os pacotinhos tinham sempre 4 figurinhas diferentes. Mas olha só, se os pacotinhos não possuem repetidas entre si, então as figurinhas podem até ser uniformes, mas não são independentes! Cada pacotinho tem quatro figurinhas, e se eu tirei a figurinha 42 em um pacotinho, então eu sei que as outras três não são a figurinha 42.

Mas pode ter sido só o acaso né? Vai ver eu dei sorte de comprar exatamente 106 pacotinhos que não tinham repetidas. Mas felizmente nós sabemos como testar se foi sorte ou não, basta fazer o teste do ##\chi^2##, que vimos no último post!

Acho que o jeito mais fácil de testar é contar quantas figurinhas diferentes tem dentro do pacotinho. Quantos pacotinhos possíveis existem com 4 figurinhas diferentes? Esse é fácil, o álbum tem 180 figurinhas, então são ##180\choose 4## pacotinhos. Com 3 diferentes precisa de mais cuidado, existem ##180\choose 3## combinações de figurinhas, mas você precisa contar qual dessas três diferentes está repetida (os casos são AABC, ABBC, ABCC). Então para 3 diferentes são ##3 {180\choose 4}## pacotinhos.

Com 2 diferentes também tem três casos: AAAB, AABB, ABBB, logo temos ##3{180\choose 2}## pacotinhos. Para uma única figurinha diferente, são apenas ##180\choose 1## pacotinhos. Agora podemos montar a tabela com quantos pacotinhos eu deveria ter visto, e quantos pacotinhos eu vi:

	1 diferente	2 diferentes	3 diferentes	4 diferentes
Total de pacotinhos	##180\choose 1##	##3{180\choose 2}##	##3{180\choose 3}##	##180\choose 4##
Total (numérico)	180	48330	2867580	42296805
Total (normalizado)	3.98e-6	1.07e-3	0.634	0.936
Esperado (total*106)	422e-6	0.113	6.72	99.163
Observado	0	0	0	106

Opa, nas duas primeiras categorias ##np\lt 5##, então eu não tenho amostras suficientes para usar o ##\chi^2##! Um jeito de consertar isso sem comprar mais pacotinhos é juntando as três primeiras categorias em uma só:

	Menos de 4 diferentes	4 diferentes
Esperado	6.837	99.163
Observado	0	106

Com isso conseguimos calcular o ##\chi^2## pela definição, chegando no valor de ##\chi^2=7.308##. Qual é o limite para rejeitar a hipótese? Se estivermos trabalhando com ##\alpha=5\%##, e um grau de liberdade, então o limite é:

InverseCDF[ChiSquareDistribution[1], 1 - 0.05]
>> 3.84146

Como ##7.308\gt 3.84146##, então temos que rejeitar a hipótese, e concluir que as figurinhas dos Vingadores não são independentes, e, como consequência, não são honestas, apesar de serem uniformes!

Felizmente para o colecionador, elas são desonestas mas estão jogando do seu lado. Se os pacotinhos diminuem a chance de ter repetidas, então o total esperado de pacotinhos que você precisa comprar é menor que no caso puramente honesto.

Dá para calcular o quanto você economiza com as figurinhas desonestas? Sure, vou mostrar dois métodos para fazer isso:

Cadeias de Markov

Esse primeiro método é mais complicado, mas vou começar por ele porque é mais genérico, e se aplica a mais casos. Imagine que eu já tenho 50 figurinhas no meu álbum, e eu abro mais um pacotinho. Se eu der azar, vão sair quatro figurinhas que eu já tenho. Se eu der sorte, pode sair até quatro que eu ainda não tinha. 

O método mais natural para modelar esse problema é com uma Cadeia de Markov: você considera o estado como sendo quantas figurinhas você tem no álbum, e as transições possíveis são quantas figurinhas você ainda não tinha no pacotinho.

Para montar a matriz de transição, nós precisamos da probabilidade de ir de um estado ##n## até um estado ##m##. Como cada pacotinho tem 4 figurinhas diferentes, então o ##m## precisa ser necessariamente ##n##, ##n+1##, ..., ##n+4##, e outras transições não são possíveis. 

Qual a chance de ir do estado ##n## para ##n+k##? Nós sabemos que as quatro figurinhas do pacotinho são diferentes entre si, então temos ##k## figurinhas novas e ##4-k## figurinhas que já tínhamos. A quantidade de pacotinhos que fazem essa transição é igual a ##{180-n\choose k}{n\choose 4-k}##, já que precisamos escolher ##k## figurinhas dentre que as não temos, e ##4-k## dentre as que temos. O total de pacotinhos é ##180\choose 4##, então a probabilidade total do estado ##n## para ##n+k## é ##{180-n\choose k}{n\choose 4-k}/{180\choose 4}## . Com isso podemos montar a matriz de transição ##M##:

$$ M= \begin{bmatrix} 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & \dots & 0 &  0 & 0 \\ 0 & 0 & 0 & 0 & 0.02 & 0.97 & 0 & 0 & \dots & 0 &  0 & 0 \\ 0 & 0 & 0 & 0 & \approx0 & 0.04 & 0.95 & 0 & \dots & 0 &  0 & 0 \\ 0 & 0 & 0 & 0 & \approx0 & \approx0 & 0.06 & 0.93 & \dots & 0 &  0 & 0 \\ \vdots &\vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & & \vdots & \vdots & \vdots  \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & \dots & 0.95 &  0.04 & \approx0 \\0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & \dots & 0 &  0.97 & 0.02 \\0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & \dots & 0 &  0 & 1 \\ \end{bmatrix}$$

Pela matriz podemos conferir a intuição: se você não tem nenhuma figurinha, o primeiro pacotinho vai garantidamente te dar 4 figurinhas novas, então o estado 0->4 na matriz vale 1, e todos os outros nessa linha são zero. Por outro lado, se está faltando só uma figurinha para completar, comprar um pacotinho novo dá um chance de 2% de conseguir a faltante. E, claro, se você tem todas as figurinhas, então a chance de você não conseguir mais nenhuma é 100%.

O que queremos calcular é quanto economizamos devido às figurinhas desonestas. Para isso, vamos calcular qual o valor esperado do número de pacotinhos que precisamos comprar para completar o álbum. Tendo a matriz de transição em mãos, isso é equivalente ao número médio de transições para ir do estado 0 (álbum vazio) ao estado 180 (álbum completo). E como calcular isso? Usando um algoritmo secreto!

Really, um algoritmo secreto. Não sei o motivo, mas você não acha esse algoritmo em lugar nenhum; não tem na wikipedia e nem nos livros de processos estocásticos que eu tenho aqui em casa. Então aproveitem para anotar porque é bem útil:

1. Dada a matriz de transição ##M##, calcule a matriz reduzida ##R##, retirando da matriz original todas as linhas e colunas associadas aos estados finais. (No nosso caso só a última linha e coluna são finais).
2. Calcule a matriz fundamental ##N## do processo, através da fórmula ##N=(I-R)^{-1}##.
3. O valor esperado do número de transições é a soma dos elementos da primeira linha da matriz ##N##.

Implementando o algoritmo acima com um scriptinho rápido no Mathematica, concluímos que o valor esperado do número de pacotinhos que você precisa comprar é ##257.98##. Como cada pacotinho custa R$ 1.20, então você precisa de R$309.58 em média para completar o álbum.

E quanto você gastaria com figurinhas 100% honestas? Esse cálculo eu já fiz aqui no blog anteriormente, se as figurinhas são uniformes e independentes então esse é o Coupon Collector Problem: para ##n## figurinhas a solução é ##n H(n)##, onde ##H(n)## é o número harmônico de ##n##. Essa fórmula dá o total de figurinhas, como elas são independentes, para o total de pacotinhos é só dividir por 4, chegando no total de ##259.78## pacotinhos, ou R$ 311.74, uma economia de 2 reais! (Eu falei que economizava, só não falei que era muito).

Embora o algoritmo secreto seja bacana e funcione em vários casos, ele é meio lento. Você precisa inverter uma matriz 181x181, o que não é muito fácil. O fato dela ser triangular e esparsa ajuda, mas tem um método melhor, que calcula o valor em O(n)!

Linearidade da Expectativa

Qual é o teorema mais surpreendente que você conhece? Só em probabilidade tem vários que são difíceis de acreditar à primeira vista, como o Monty Hall Problem e o Paradoxo do Aniversário. Mas um que sempre me espanta é a linearidade da expectativa (o valor esperado da soma é a soma dos valores esperados):

$$E[a+b]=E[a]+E[b]$$

Para mim a parte curiosa é que ele funciona mesmo se as variáveis ##a## e ##b## não forem independentes! Para o nosso problema isso ajuda bastante: o valor esperado para conseguir 180 figurinhas claramente é correlacionado com o valor esperado para conseguir 179 figurinhas, mas eu posso usar relações lineares entre eles sem medo.

Para essa análise eu acho mais fácil pensar invertido. Se estiver faltando 0 figurinhas para completar o album, quantos pacotinhos eu preciso? Nenhum né, ele já está completo. E se estiver faltando só uma figurinha? Aí depende do que sair no pacotinho, se sair a figurinha faltante, um pacotinho basta, se não sair, então você adiciona um pacotinho no seu valor esperado e repete o procedimento:

$$\begin{align*}\\E[1]&=p_0(1+E[0]) + p_1(1+E[1])\\ (1-p_1)E[1] &= p_1 + p_0(1+E[0]) \\ E[1] &=\frac{1}{1-p_1}\left(p_1+p_0(1+E[0])\right)\end{align*}$$

Olha só, eu sei que ##E[0]=0##; para calcular ##E[1]## eu preciso só do ##E[0]##; para o ##E[2]## eu preciso do ##E[1]## e ##E[0]##; e assim por diante. Como cada pacotinho tem no máximo 4 figurinhas que eu não tenho, então eu só preciso olhar quatro valores para trás na recorrência. Portanto, esse algoritmo é linear!

Preenchendo as probabilidades corretas, o algoritmo completo fica assim:

$$\begin{align*} \\ E[0] &= 0 \\ E[n] &= \frac{1}{1-{{180-n}\choose 4}/{180\choose 4}}\left(\frac{{180-n}\choose 4}{180\choose 4}+\sum_{1\le k \le 4}\frac{{n\choose k}{{180-n}\choose{4-k}}}{180\choose 4}E[n-k]\right) \\ \end{align*} $$

Essa implementação realmente é bem mais rápida que o anterior. A versão com matrizes no Mathematica leva 1s para rodar, enquanto que um scriptinho python com o algoritmo linear leva só 55ms!

Agora que temos os pacotinhos corretamente modelados, finalmente vamos conseguir bolar uma estratégia para minimizar o custo de completar o álbum. Mas vai ficar para o próximo post porque esse já ficou comprido demais :)

A Marcha dos Lemmings

Lemmings são pequenos roedores que vivem na tundra ártica. Eles possuem pelos longos e macios, rabo curto, são herbívoros e explodem.

Sim, eles explodem! Os lemmings possuem a capacidade de ligar um contador luminoso sobre suas cabeças. A cada passo que dão, o contador decrementa, até que finalmente explodem quando o contador chega a zero.

O que você faria se soubesse que vai explodir em seis passos? Parece que não tem muitos passeios possíveis com exatamente seis passos, mas a intuição é meio falha aqui. Na verdade, o número de passeios possíveis é exponencial no número de passos! Como fazer um algoritmo que calcula o número de caminhos possíveis que o lemming pode fazer antes de explodir?

As Regras do Jogo

Para modelar o problema, vamos supor que os passos que lemming pode fazer são descritos por um grafo orientado. Por exemplo, no grafo abaixo o lemming começa no nó A. Do A ele pode ir para B ou C, de B ele pode ir para C, e de C ele pode ir para A.

Se o nosso lemming pode dar seis passos, então existem sete caminhos diferentes que ele pode fazer:

ABCABCA

ABCACAB

ABCACAC

ACABCAB

ACABCAC

ACACABC

ACACACA

Logo ##p(6)=7##, e podemos até tabelar ##p(n)## para todos os ##n## de 0 a 6:

$$p(0..6)=1,2,2,3,4,5,7$$
Dado ##n##, como fazer um algoritmo que calcule ##p(n)##?

Eu vou mostrar três algoritmos possíveis usando a linguagem do Wolfram Mathematica. Para isso, o grafo precisa ser descrito de alguma maneira que os algoritmos entendam. Eu vou usar uma matriz de adjacências: para um grafo com ##k## nós, a matriz é ##k\times k## e o elemento na linha ##i## da coluna ##j## é 1 se existe uma ligação saindo do nó ##j## e indo em direção ao nó ##i##, e 0 em caso contrário. Para o nosso exemplo, a matriz é:

$$M=\left[\begin{matrix}0 && 0 && 1 \\ 1 && 0 && 0 \\ 1 && 1 && 0\end{matrix}\right]$$

Força Bruta

Sempre que eu tenho que fazer um algoritmo do zero, prefiro começar com a força bruta. É fácil e rápido de implementar, e embora não seja eficiente, serve para conferir o resultado dos algoritmos mais avançados.

Nesse caso, para implementar a força bruta você passa o grafo, o nó em que o lemming está, quantos passos faltam para terminar, e o resto é uma recursão simples. Como toda recursão, não esqueça de fazer o caso base! Para esse problema, o caso base é ##p(0)=1##, ou seja, tem um único caminho possível sem dar passo nenhum, que é não sair do lugar.

No fim, a solução em força bruta fica assim:

count[graph_, pos_, 0] := 1
count[graph_, pos_, size_] := Sum[
    If[graph[[i, pos]] == 1, count[graph, i, size - 1], 0],
    {i, 1, Length[graph]}]

Vamos conferir o resultado:

graph := {{0, 0, 1}, {1, 0, 0}, {1, 1, 0}}
Print[Table[count[graph, 1, n], {n, 0, 6}]]

{1,2,2,3,4,5,7}

Perfeito! Mas qual é a complexidade desse algoritmo? Bem, ele precisa visitar cada um dos caminhos possíveis, e o número total de caminhos é exponencial, logo a complexidade vai ser do tipo ##O(c^n)##, onde a constante ##c## depende do grafo. Ou seja, você não quer usar esse algoritmo quando o ##n## é grande.

Multiplicação de Matrizes

Como melhorar então? Tem uma maneira calcular ##p(n)## mais rápido usando multiplicação de matrizes. É mais fácil mostrar como funciona por exemplos: no estado inicial, nós temos um lemming no nó A, então vamos montar um vetor correspondente: ##V=[1 \;0\; 0]^T##. Se multiplicarmos ##M## por ##V##, qual o resultado?

$$M V=\left[\begin{matrix}0 && 0 && 1 \\ 1 && 0 && 0 \\ 1 && 1 && 0\end{matrix}\right] \left[\begin{matrix}1\\0\\0\end{matrix}\right]=\left[\begin{matrix}0\\1\\1\end{matrix}\right]$$

Ou seja, um lemming que está em A vai parar em B ou C. Continuando:

$$M V=\left[\begin{matrix}0 && 0 && 1 \\ 1 && 0 && 0 \\ 1 && 1 && 0\end{matrix}\right] \left[\begin{matrix}0\\1\\1\end{matrix}\right]=\left[\begin{matrix}1\\0\\1\end{matrix}\right]$$
Dado um lemming em B ou C, o resultado é um lemming em A ou C. Se o vetor de entrada mostra quantos lemmings tem em cada nó, multiplicar pela matriz M vai mostrar onde eles podem estar depois de dar um passo.

Agora é só estender o raciocínio. Se multiplicar por M correponde a um passo, então multiplicar ##n## vezes por M é o equivalente a ##n## passos. E se você começou o processo com um vetor unitário, então a soma do elementos de V é o número de caminhos possíveis partindo do nó inicial!

Uma implementação possível é a abaixo:

count[graph_, pos_, size_] :=
  Total[MatrixPower[graph, size] . UnitVector[Length[graph], pos]]

Conferindo:

graph := {{0, 0, 1}, {1, 0, 0}, {1, 1, 0}}
Print[Table[count[graph, 1, n], {n, 0, 6}]]

{1,2,2,3,4,5,7}

Bateu certinho novamente! E qual é a complexidade? Se você implementou a multiplicação e a exponenciação de matrizes do jeito mais simples, vai ser da ordem de ##O(k^3 n)##, que certamente é melhor que exponencial mas ainda não é boa o suficiente para usar na prática.

No entanto, você pode melhorar isso com implementações melhores! A multiplicação de matrizes pode usar o algoritmo de Strassen, e a exponenciação pode usar o método binário, aí o total fica ##O(k^{2.8} \log_2 n)##, bem melhor; e se a matriz for esparsa dá para ficar ainda mais rápido.

Função Geradora

Mas tem um método que supera o anterior, que é usar funções geradoras! Nós começamos tudo com um grafo orientado, e todo grafo orientado é equivalente a um autômato finito. Por sua vez, todo autômato finito é equivalente a uma gramática regular, então deve ter um jeito de descrever os caminhos do lemming usando uma gramática. Para o exemplo dado, a gramática fica assim:

$$\begin{align*}\alpha &\to A \;|\; A \beta \;|\; A \gamma \\ \beta &\to B \;|\;  B \gamma \\ \gamma &\to C \;|\; C \alpha\end{align*}$$
Todos os caminhos possíveis produzem strings que são aceitas por essa gramática, e a gramática não aceita nenhuma string que não seja um caminho possível.

O truque agora é usar combinatória analítica, que para o problema de enumerar strings de uma gramática é bem simples: basta trocar cada token por um ##z##, e cada OR por uma adição. A gramática vira um sistema de equações:

$$\begin{align*}\alpha &= z + z\beta +z \gamma \\ \beta &= z+z \gamma \\ \gamma &= z+z \alpha\end{align*}$$
Resolvendo para ##\alpha##, chegamos na função geradora:

$$\alpha=\frac{z + 2 z^2 + z^3}{1 - z^2 - z^3}$$
E para que serve a função geradora? Olhe só o que acontece quando abrimos a função em série de potências:

$$\frac{z + 2 z^2 + z^3}{1 - z^2 - z^3}=z+2z^2+2z^3+3z^4+4z^5+5z^6+7z^7+\dots$$

Ahá! Os coeficientes de ##z## são exatamente o número de caminhos no grafo! Para calcular ##p(6)##, basta olhar o coeficiente de ##z^7## (você precisa somar um porque a função geradora está contando o número de tokens na strings, e nós queremos o número de passos).

Podemos ir além agora. Quando a função geradora é uma função racional, você sempre consegue inverter e conseguir uma fórmula explícita para ##p(n)##:

$$p(n)=0.957\times 1.325^n+0.426\times 0.869^n\cos(1.469+ 2.438 n)$$
Essa fórmula é exata (ou seria, se eu não tivesse truncado os números para caber na tela). Note que o resultado sempre vai ser um inteiro, e que a parte oscilante da fórmula sempre vai ser menor que 0.4, então dá para simplificar mais ainda:

$$p(n)=\left\lfloor 0.5+0.957\times 1.325^n\right\rfloor$$
Basta pegar a parte exponencial e arredondar para o inteiro mais próximo. Podemos observar duas coisas aqui. Primeiro, agora nós temos um algoritmo onde o número de operações independe do valor de ##n##, então efetivamente esse algoritmo é ##O(1)##. Na prática você vai implementar usando bignum, aí não fica ##O(1)## de verdade; mas os outros algoritmos mostrados também vão ficar mais lentos na mesma proporção.

Segundo, nós provamos que aquele primeiro algoritmo era de fato ##O(c^n)##! Conseguimos até calcular quem é o tal do ##c##: é aproximadamente 1.325; ou, se você quiser o valor exato com radicais:

$$c=\frac{\sqrt[3]{9+\sqrt{69}}+\sqrt[3]{9-\sqrt{69}}}{\sqrt[3]{18}}$$
Para implementar esse método computacionalmente, é só reescrever aquele sistema de equações em forma matricial:

$$\left[\begin{matrix}\alpha\\ \beta \\ \gamma\end{matrix}\right] = z \left[\begin{matrix}0 && 1 && 1\\0 && 0 && 1\\ 1 &&0 && 0\end{matrix}\right] \left[\begin{matrix}\alpha\\ \beta \\ \gamma\end{matrix}\right]  + z\left[\begin{matrix}1\\ 1\\1\end{matrix}\right] $$

A matriz ali no meio é a transposta da matriz de adjacências! Agora já podemos implementar:

count[graph_, pos_, size_] := With[{n = Length[graph]},
  SeriesCoefficient[LinearSolve[
      IdentityMatrix[n] - z Transpose[graph],
      ConstantArray[z, n]][[pos]],
    {z, 0, size + 1}]]

Como esperado, a resposta é correta:

graph := {{0, 0, 1}, {1, 0, 0}, {1, 1, 0}}
Print[Table[count[graph, 1, n], {n, 0, 6}]]

{1,2,2,3,4,5,7}

Um Problema em Aberto

Nós chegamos em um algoritmo que é ##O(1)##, dá para otimizar mais? Não! Esse é um limite teórico.

Quer dizer, existem algoritmos que são ##O(0)##. Por exemplo, "crie um algoritmo que, dado uma circunferência e um diâmetro, calcule a razão entre os dois". Esse é algoritmo é ##O(0)## porque a resposta é sempre ##\pi##, independe do input. Mas, se a resposta não é constante, ##O(1)## é o melhor algoritmo possível. (A não ser que você crie um algoritmo que dê a resposta antes do input chegar. Nesse caso me ensine como faz, porque você inventou a viagem no tempo).

Mas existe uma pequena variação no problema dos lemmings que o torna muito, muito mais difícil. Suponha que agora o lemming não pode passar duas vezes pelo mesmo nó. A força bruta para essa variação ainda é ##O(c^n)##. Mas ninguém bolou um algoritmo que seja melhor que a força bruta nesse caso!

Quando o grafo é finito, você pode usar a força bruta para enumerar todas as soluções, já que eventualmente o grafo acaba. Mas se o grafo for infinito, aí danou-se. Para esse caso, tem gente procurando a solução desde a década de 50. Já são setenta anos procurando o algoritmo e ninguém achou nada para um grafo genérico, nem mesmo um assintótico! O melhor resultado até hoje é um de 2011 onde acharam o ##c## para um grafo específico, o lattice hexagonal. Para todos os outros grafos, o melhor que temos são heurísticas e aproximações numéricas.

Se você estiver sem nada o que fazer no próximo fim de semana, essa pode ser uma boa maneira de ocupar o tempo!

A Busca Por Bozo Binário

Se você trabalhar por tempo o suficiente com Computação, eventualmente uma das suas atribuições vai ser entrevistar candidatos para a sua equipe. Entrevistar é uma arte: existem inúmeros truques e macetes para descobrir se é esse sujeito na sua frente é mesmo o cara que você quer como seu parceiro. O Joel tem uma boa introdução sobre o tema que vale a pena ler.

Uma das habilidades que você precisa desenvolver rápido é aprender que o candidato não pensa como você. Em especial, quando ele responde uma pergunta de um jeito diferente daquele que você esperava, não quer dizer necessariamente que ele esteja errado. E esse caso eu já vi de perto, com o algoritmo que eu apelidei de Busca Por Bozo Binário.

Essa história aconteceu faz algum tempo. Eu estava na cantina conversando sobre entrevistas, quando alguém comentou que rejeitou um candidato porque ele não conseguiu implementar uma busca binária. Poxa, isso é grave mesmo! E qual o algoritmo errado que ele fez? A resposta foi essa:

"Sorteie um número de 1 até o tamanho do vetor, e verifique o elemento que tinha esse índice. Se for igual você achou, então retorna. Se for menor, repete para o lado esquerdo; se for maior, repete para o lado direito."

Isso é errado, me disseram, porque o pior caso é ##O(n)##. De fato, se o elemento que você quer achar é o primeiro, e o gerador de aleatórios retornar sempre o último, ele vai passar pelo vetor inteiro.

Mas nesse ponto eu tive que interromper: "Peraí! Você explicitou que queria ##O(\log n)## no pior caso? Se você não falou nada no enunciado, ele pode ter entendido que era ##O(\log n)## no caso médio, e aí o algoritmo dele está certo!"

Na hora ninguém botou fé que esse algoritmo de Busca por Bozo Binário era de fato ##O(\log n)##, então eu tive que voltar para casa e escrever a demonstração. Se você tem medo de Matemática Discreta, pule a caixa azul:

Para a Busca por Bozo Binário, nós queremos calcular qual é o valor médio do número de comparações que ele realiza. E como você começa uma análise de caso médio?

Primeiro você define as características da entrada: eu vou assumir que todos os casos estão distribuídos uniformemente. Depois, é só usar a fórmula do valor esperado: você soma o número de comparações em cada caso, multiplicado pela probabilidade daquele caso ocorrer. $$ F[x] = \sum_i p[i]C[i] $$ Antes de começar, vejamos os casos extremos. Quando o vetor é vazio, não precisa de nenhuma comparação, então ##F[0]=0##. Se o vetor tiver tamanho um, então só precisa de uma comparação, ##F[1]=1##. É sempre bom ter uns casos pequenos para conferir no final.

Vamos ver agora o caso de um vetor de tamanho ##n##. Eu não sei qual número vai ser escolhido para cortar o vetor em dois, é o gerador de números aleatórios que escolhe. Então eu vou tirar a média sobre todas as escolhas possíveis. Como os ##n## valores são equiprováveis, então a probabilidade individual é ##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] $$ Na fórmula acima, ##F[n]## é o número médio de comparações para um vetor de tamanho ##n##, e ##F[k,n]## é o número médio de comparações para o vetor de tamanho ##n##, no caso em que o corte foi feito no elemento ##k##.

Vamos calcular ##F[k,n]## agora. Esse valor depende de onde está o número que estamos procurando. Eu não sei onde está o número; como estamos calculando o caso médio, precisamos tirar a média sobre todos as posições possíveis. $$F[k,n]=\sum_{0\le i\lt n}\frac{1}{n}F[i,k,n]=\frac{1}{n}\sum_{0\le i\lt n}F[i,k,n]$$ Agora ##F[i,k,n]## significa o valor médio para um vetor de tamanho ##n##, cortado na posição ##k##, e com número final na posição ##i##.

Nós temos três casos agora. Se ##i=k##, então você só precisa comparar uma vez, a comparação vai ser verdadeira e o algoritmo termina. Se ##i\lt k##, então você compara uma vez e faz recursão para o lado esquerdo. Se ##i\gt k##, então você compara uma vez e faz recursão para o lado direito. Resumindo: $$F[i,k,n]=\begin{cases} 1+F[k] &(i \lt k) \\ 1 &(i = k) \\ 1+F[n-k-1] &(i \gt k) \\ \end{cases}$$ Podemos sintetizar tudo que vimos em uma única recorrência. $$\begin{align*} F[0] &= 0 \\ F[n] &= \frac{1}{n} \sum_{0\le k \lt n}\left( \frac{1}{n}\sum_{0\le i\lt k}\left(1+ F[k]\right) + \frac{1}{n} + \frac{1}{n}\sum_{k\lt i\lt n}\left(1+ F[n-k-1]\right) \right) \end{align*}$$ Agora é só resolver!

Antes de mais nada, vamos coletar quem é constante em relação ao índice da somatória. Todos os ##1/n## coletam, e as somatórias mais internas viram constantes. $$\begin{align*} F[n] &= \frac{1}{n^2} \sum_{0\le k \lt n}\left( \sum_{0\le i\lt k}\left(1+ F[k]\right) + 1 + \sum_{k\lt i\lt n}\left(1+ F[n-k-1]\right) \right) \\ &= \frac{1}{n^2} \sum_{0\le k \lt n} k \left(1+ F[k]\right) + 1 + \left(n-k-1\right)\left(1+ F[n-k-1]\right) \\ &= \frac{1}{n^2} \sum_{0\le k \lt n} k + k F[k] + 1 + n-k-1 +\left(n-k-1\right)F[n-k-1] \\ &= \frac{1}{n^2} \sum_{0\le k \lt n} n + k F[k] +\left(n-k-1\right)F[n-k-1] \\ &= 1+\frac{1}{n^2} \left(\sum_{0\le k \lt n} k F[k] +\sum_{0\le k \lt n} \left(n-k-1\right)F[n-k-1] \right) \\ \end{align*}$$ Vamos focar naquela segunda somatória. Primeiro fazemos ##q=n-k-1##: $$ \sum_{0\le k \lt n} \left(n-k-1\right)F[n-k-1] =\sum_{0\le n-q-1 \lt n} qF[q] $$ Agora é só manipular os índices: $$\begin{align*} 0\le n-&q-1 \lt n \\ 1-n\le -&q \lt 1 \\ -1\lt &q \le n-1 \\ 0\le &q \lt n \\ \end{align*}$$ Olha só, a segunda somatória é igual à primeira! $$ \sum_{0\le n-q-1 \lt n} qF[q] =\sum_{0\le q \lt n} qF[q] =\sum_{0\le k \lt n} kF[k] $$ Substituindo, chegamos em uma fórmula curta para ##F[n]##: $$\begin{align*} F[n] &= 1+\frac{1}{n^2} \left(\sum_{0\le k \lt n} k F[k] +\sum_{0\le k \lt n} \left(n-k-1\right)F[n-k-1] \right) \\ &= 1+\frac{1}{n^2} \left(\sum_{0\le k \lt n} k F[k] +\sum_{0\le k \lt n} kF[k] \right) \\ &= 1+\frac{2}{n^2} \sum_{0\le k \lt n} k F[k] \\ \end{align*}$$ A somatória ainda está atrapalhando, o ideal seria sumir com ela. Uma maneira de fazer isso é isolando: $$\begin{align*} F[n] &= 1+\frac{2}{n^2} \sum_{0\le k \lt n} k F[k] \\ \sum_{0\le k \lt n} k F[k] &= \frac{n^2}{2}\left(F[n]-1\right) \end{align*}$$ Essa última fórmula vale para todo ##n##, em especial vale também para ##n-1##: $$\begin{align*} \sum_{0\le k \lt n} k F[k] &= \frac{n^2}{2}\left(F[n]-1\right) \\ \sum_{0\le k \lt n-1} k F[k] &= \frac{(n-1)^2}{2}\left(F[n-1]-1\right) \\ \end{align*}$$ Ahá! Agora é só subtrair uma da outra que a somatória desaparece! $$\begin{align*} \sum_{0\le k \lt n} k F[k] - \sum_{0\le k \lt n-1} k F[k] &= \frac{n^2}{2}\left(F[n]-1\right) - \frac{(n-1)^2}{2}\left(F[n-1]-1\right)\\ (n-1) F[n-1] &= \frac{n^2}{2}\left(F[n]-1\right) - \frac{(n-1)^2}{2}\left(F[n-1]-1\right)\\ (n-1) F[n-1] &= \frac{n^2}{2}F[n]-\frac{n^2}{2} - \frac{(n-1)^2}{2}F[n-1]+\frac{(n-1)^2}{2}\\ \frac{n^2}{2}F[n] &= \left(\frac{(n-1)^2}{2}+(n-1)\right)F[n-1]+\left(\frac{n^2}{2} -\frac{(n-1)^2}{2}\right)\\ n^2F[n] &= \left(n^2-1\right)F[n-1]+(2n-1)\\ \end{align*}$$ Chegamos finalmente em uma recorrência sem somatórias. Melhor ainda, essa recorrência está no ponto certo para usar a técnica do summation factor! Como esse é um truque muito útil de se conhecer, eu vou fazer em câmera lenta. Você pode usar um summation factor sempre que sua recorrência for da forma abaixo: $$a_n F[n] = b_n F[n-1]+c_n$$ Esse é o nosso caso, se usarmos a correspondência abaixo: $$\begin{align*} a_n &= n^2 \\ b_n &= n^2-1 \\ c_n &= 2n-1 \end{align*}$$ O segredo do summation faction é tentar achar uma sequência mágica ##s_n## que tenha a seguinte propriedade: $$s_n b_n=s_{n-1}a_{n-1}$$ E por que isso é bom? Olha só o que acontece quando você multiplica a recorrência original por ##s_n##: $$\begin{align*} a_n F[n] &= b_n F[n-1]+c_n \\ s_n a_n F[n] &= s_n b_n F[n-1]+s_n c_n \\ s_n a_n F[n] &= s_{n-1}a_{n-1}F[n-1]+s_n c_n \\ \end{align*}$$ Agora, se você substituir ##T[n]=s_n a_n F[n]##, temos: $$\begin{align*} s_n a_n F[n] &= s_{n-1}a_{n-1}F[n-1]+s_n c_n \\ T[n] &= T[n-1]+s_n c_n \end{align*}$$ Opa, essa é fácil! Dá pra resolver de cabeça, é praticamente a definição de somatória! $$\begin{align*} T[n] &= T[n-1]+s_n c_n\\ T[n] &= T[0] + \sum_{1\le k \le n} s_k c_k \\ s_n a_n F[n] &= s_0 a_0 F[0] + \sum_{1\le k \le n} s_k c_k \\ F[n] &= \frac{1}{s_n a_n} \left(s_0 a_0 F[0] + \sum_{1\le k \le n} s_k c_k \right) \\ \end{align*}$$ Pronto, agora não é mais uma recorrência, é uma fórmula simples. A dificuldade do método é encontrar o tal do ##s_n##. Para achá-lo você pode usar a intuição, chutar, fazer um sacrifício aos deuses; ou então você pode usar o método do porradão. Nesse método você começa com ##s_n=s_{n-1}\left(a_{n-1}/b_n\right)## e abre recursivamente, chegando no monstrinho abaixo: $$s_n = \frac{a_{n-1}a_{n-2}\ldots a_2 a_1}{b_n b_{n-1}\ldots b_3 b_2}$$ Essa fórmula parece grande, e é grande mesmo. Mas na maioria das vezes tem um monte de cancelamentos, o que deixa o resultado final pequeno. Vamos ver no nosso caso como fica: $$\begin{align*} s_n &= \frac{a_{n-1}a_{n-2}\ldots a_2 a_1}{b_n b_{n-1}\ldots b_3 b_2} \\ &= \frac{(n-1)^2 (n-2)^2 \ldots 2^2 1^2} {\left(n^2-1\right) \left(\left(n-1\right)^2-1\right) \ldots (3^2-1) (2^2-1)} \\ &= \frac{(n-1)^2 (n-2)^2 \ldots 2^2 1^2} {\left((n+1)(n-1)\right) \left((n-1+1)(n-1-1)\right) \ldots (3+1)(3-1) (2+1)(2-1)} \\ &= \frac{(n-1) (n-2)(n-3) \ldots3\cdot 2\cdot 1} {(n+1) (n) (n-1)\ldots (4+1) (3+1) (2+1)} \\ &= \frac{2} {(n+1) (n) } \\ \end{align*} $$ Cancelou mesmo! Bastou lembrar que ##(a^2-b^2)=(a+b)(a-b)## que o resto saiu. Agora é só lembrar que ##F[0]=0## e substituir na fórmula: $$\begin{align*} F[n] &= \frac{1}{s_n a_n} \left(s_0 a_0 F[0] + \sum_{1\le k \le n} s_k c_k \right) \\ F[n] &= \frac{n(n+1)}{2n^2} \sum_{1\le k \le n} \frac{2(2k-1)}{k(k+1)}\\ \end{align*}$$ Essa é a solução da recorrência. Dá para achar uma forma fechada? Nesse caso dá, desde que você tope uma forma fechada em função dos números harmônicos ##H[n]##, que são definidos como: $$H[n]=\sum_{1\le k \le n}\frac{1}{k}$$ Você começa abrindo a fração no somatório: $$\begin{align*} \frac{2(2k-1)}{k(k+1)} &= \frac{A}{k} + \frac{B}{k+1}\\ \frac{4k-2}{k(k+1)} &= \frac{A(k+1)+B k}{k(k+1)}\\ 4k-2 &= Ak+A +B k \\ 4k-2 &= (A+B)k+A \\ A &= -2 \\ B &= 6 \end{align*}$$ Agora você divide o somatório em dois: $$\begin{align*} F[n] &= \frac{n(n+1)}{2n^2} \sum_{1\le k \le n} \frac{2(2k-1)}{k(k+1)}\\ F[n] &= \frac{n(n+1)}{2n^2} \sum_{1\le k \le n} \frac{6}{k+1} - \frac{2}{k}\\ F[n] &= \frac{n(n+1)}{2n^2} \left( \sum_{1\le k \le n} \frac{6}{k+1} - \sum_{1\le k \le n} \frac{2}{k} \right) \\ F[n] &= \frac{n(n+1)}{2n^2} \left( \sum_{1\le k \le n} \frac{6}{k+1} - 2\sum_{1\le k \le n} \frac{1}{k} \right) \\ F[n] &= \frac{n(n+1)}{2n^2} \left( \sum_{1\le k \le n} \frac{6}{k+1} - 2H[n] \right)\\ \end{align*}$$ O primeiro somatório 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 é ##O(\log n)## mesmo? Bem, podemos verificar usando um assintótico para o harmônico, por exemplo: $$ H[n] = \ln n + \gamma + O(1/n) $$ Agora você 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 queríamos demonstrar!

Ou seja, realmente a Busca por Bozo Binário é ##O(\log n)##. Em demonstrações grandes assim eu sempre gosto de fazer uma simulação por Monte Carlo para conferir as contas. A minha simulação está no github:

Busca por Bozo Binário, simulação por Monte Carlo

Simulando 50000 vezes em um vetor de tamanho 3000, o número médio de comparações foi de ##14.1769##. O valor teórico previsto pela fórmula é de ##14.1732##, nada mau!

Eu também fiz uma simulação da busca binária tradicional como comparação. Com os mesmos parâmetros, a busca tradicional usou ##10.6356## comparações no caso médio, ou seja, foi mais eficiente que o Bozo Binário.

Por que isso acontece? Analisando o assintótico fica claro. Para ##n## grande, o valor médio da Busca por Bozo é de ##2 \ln n## (logaritmo natural), enquanto que na busca binária é ##\log_2 n## (logaritmo de base 2). Então, em média, esperamos que Bozo Binário 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 simulação.

Depois da análise do algoritmo, a dúvida que resta é: e o candidato? Bem, se fosse eu a entrevistar, precisaria coletar mais dados para saber se ele realmente sabia do tempo médio, ou se estava perdido e implementou a primeira coisa que veio na cabeça.

Um possível follow-up é "Certo, esse método é mais complicado que a busca binária tradicional, mas funciona. Você pode me falar alguma situação onde ele é preferível sobre o tradicional?". Curiosamente, existe sim um caso onde a Busca por Bozo Binário é melhor que a busca binária tradicional! Mas esse caso fica para a próxima :)

A Intuição do Knuth

Às vezes eu me pergunto se as pessoas da minha área têm noção de quão sortudos nós somos. Os físicos adorariam viajar no tempo para conversar com o Newton, os matemáticos adorariam conversar com o Euclides, os biólogos adorariam conversar com o Darwin. Mas nós podemos conversar com o Knuth!

Nós temos a sorte de viver no mesmo período de tempo que o criador da análise de algoritmos, que é uma das bases da Ciência da Computação. Se você gosta do assunto, vale a pena juntar uns trocos e viajar até a Califórnia para assistir a uma das palestras dele (dica: todo fim de ano, inspirado nas árvores de Natal, ele faz uma palestra de estrutura de dados, falando sobre árvores; elas também estão online se você não tiver como ver ao vivo).

Eu fiz a peregrinação em 2011, quando consegui assistir a uma das palestras dele. Aproveitei para ir todo contente pegar minha recompensa por ter achado um erro no Art of Computer Programming, mas ele, marotamente, me disse que aquilo que eu achei não era um erro, era uma pegadinha, e eu caí! (Mas eu não vou falar qual a pegadinha, vá na página 492 do TAOCP volume 4A, primeira edição, e confira você mesmo :)

Eu e Knuth, o trollzinho

Nesse dia perguntaram que opinião ele tinha sobre o problema mais difícil da nossa geração, P=NP. A intuição dele é que provalmente é verdade, mas ele acredita que se acharmos a demonstração, ela vai ser não-construtiva. O que isso significa? O que é uma demonstração não-construtiva?

Demonstrações construtivas e não-construtivas

Em análise de algoritmos, as demonstrações construtivas são as mais comuns. Por exemplo, digamos que eu quero provar que é possível calcular x elevado a y em tempo O(y). Isso é fácil, basta construir um algoritmo assim:
E se eu quiser provar que esse mesmo problema pode ser resolvido em tempo O(log y)? Novamente, tudo que eu preciso fazer é exibir um algoritmo que implemente isso:

(Nesse caso eu também precisaria provar que esse algoritmo é de fato O(log y), já não é óbvio por inspeção). Nos dois casos temos exemplos de demonstrações construtivas: se eu quero provar uma propriedade P, basta exibir um algoritmo que tenha essa propriedade P.

As demonstrações não-construtivas são diferentes. Nelas, eu posso provar a propriedade P sem mostrar o algoritmo, através de alguma propriedade matemática do modelo.

Por exemplo, imagine que eu tenho uma lista ordenada de números. Se eu fizer uma busca binária, posso achar a posição de um número dado com O(log n) comparações. Mas é possível criar um algoritmo mais rápido que isso? Eu digo que não é possível, e para isso vou fazer uma prova não-construtiva de que esse é o mínimo que um algoritmo de busca precisa para funcionar.

A Teoria de Shannon aplicada à busca binária

Para isso eu vou usar a teoria da informação de Shannon. Essa teoria é surpreendentemente intuitiva, e se baseia no conceito de surpresa. Se eu te falar que o céu ficou escuro às 19h, você não vai achar nada de mais, nessa hora o Sol está se pondo, então é natural que o céu fique escuro. Mas e se eu falar que o céu ficou escuro às 10 da manhã? Foi uma tempestade? Um eclipse? A nave do Independence Day?

Intuitivamente, quanto mais surpresos nós ficamos com uma sentença, mais informação ela tem. O Shannon definiu então a quantidade de informação como sendo uma função monotônica da probabilidade do evento acontecer:

Se o evento é raro, tem bastante informação; se o evento é comum, tem pouca informação. A base do logaritmo fornece a unidade de medida, se a base for 2, então a informação é medida em bits.

E quanta informação nós ganhamos com uma comparação? Se a chance de dar verdadeiro ou falso for a mesma, então a chance é p(m)=1/2, logo a informação é I(m)=1. Você ganha exatamente um bit de informação com uma comparação.

Qual o resultado do nosso algoritmo de busca? O resultado é um índice, se nós temos n elementos no vetor, então a resposta é um índice que varia de 0 a n-1. Logo, a probabilidade de você escolher o índice certo ao acaso é p(m)=1/n, já que a escolha é uniforme.

Quanta informação tem essa escolha, então? Fazendo a conta:

Se você precisa de log n bits para descrever a resposta, e você ganha só 1 bit por comparação, então não tem como um algoritmo rodar em menos que O(log n): a informação tem que vir de algum lugar! Com isso, nós mostramos que qualquer algoritmo precisa rodar no mínimo em tempo O(log n), e sem precisar mostrar o algoritmo em si. Essa é uma demonstração não-construtiva.

Pressinto a pergunta: "mas RicBit, e a busca com hash table, ela não é O(1)?". Sim, ela é! Mas ela não usa comparações, e a nossa análise foi exclusivamente para métodos baseados em comparações. Com um acesso a uma hash você pode ganhar mais que 1 bit de informação por operação.

O limite da ordenação

Um outro exemplo é achar o limite dos algoritmos de ordenação. Suponha que eu tenho um vetor com elementos bagunçados e quero ordená-los usando comparações. Eu sei que cada comparação ganha 1 bit de informação, então só preciso saber quanta informação tem na saída.

Qual o resultado do algoritmo? Um vetor ordenado. Mas os valores do vetor em si são irrelevantes, o que importa mesmo é saber a ordem relativa entre eles. Essa ordem relativa pode ser expressa como uma permutação dos itens originais.

Quantas permutações existem? Se o vetor tem tamanho n, então existem n! permutações, logo a probabilidade é 1/n!. Fazendo as contas:

Primeiro você usa a aproximação de Stirling, depois joga fora todos os termos assintoticamentes menores que o dominante. O resultado é que nós provamos que nenhuma ordenação pode ser melhor que O(n log n), sem precisar mostrar nenhum algoritmo!

Novamente, esse resultado só vale para ordenações baseadas em comparações. Sem usar comparações, você tem métodos como radix sort e ábaco sort que são melhores que O(n log n).

A análise por quantidade de informação

Esse método de análise da quantidade de informação pode ser utilizado em qualquer algoritmo, desde que você note um detalhe muito importante: o método acha um limite inferior para a complexidade, mas não prova que esse algoritmo existe! Tudo que conseguimos provar como ele é que, se o algoritmo existir, então ele não pode ser melhor que o limite achado.

Mande Mais Dinheiro usando MIP

Era uma vez, há mais de cem anos atrás, uma família de matemáticos. O avô era matemático, o pai era matemático, e o filho mudou de cidade para estudar matemática na melhor universidade do país. O pai lhe deu algum dinheiro para pagar o aluguel enquanto estivesse estudando, mas ele não contava com os preços altos. Naquela cidade, o dinheiro que ele tinha não era suficiente para alugar um quartinho.

O filho então precisava mandar uma mensagem para o pai, pedindo mais dinheiro. Naquela época, o meio de comunicação mais rápido era o telégrafo, mas você pagava por cada letra enviada. Por isso, a mensagem tinha que ser bastante sucinta. Depois de pensar um pouco, mandou para o pai a mensagem "SEND+MORE=MONEY".

Ao receber a mensagem, primeiro o pai ficou perplexo. Quanto dinheiro ele precisava mandar? Depois de pensar um pouco, ele logo concluiu: "Ah, eu preciso mandar $10652 para ele!".

Como o matemático pai chegou a essa conclusão?

Esse problema é um exemplo de Criptoaritmética. A solução é trocar as letras por números, de tal maneira que a cada letra corresponda um único número, e de modo que a adição resultante seja verdadeira. No caso descrito acima, só existe uma solução válida, que é M=1, Y=2, E=5, N=6, D=7, R=8, S=9 e O=0.

 

Você pode achar essa solução usando apenas deduções lógicas. Por exemplo, M precisa ser 1 porque o carry (vai-um) da primeira coluna nunca pode ser maior que um. Com raciocínios similares você descobre os números restantes.

Resolver problemas assim é bastante divertido! Meu primeiro contato com Criptoaritmética foi na revista Micro Sistemas #46, de julho de 85, onde eles apresentam um gerador de criptogramas, para que você possa resolvê-los na mão. Na época eu era viciado, gostava tanto que até cheguei a portar esse gerador para Pascal já na época dos PCs.

Já na revista MSX Micro #15, de maio de 88, um desafio mais difícil foi proposto pelo Nabor Rosenthal: escrever um programa de computador que resolva sozinho os criptogramas!

Como fazer um programa assim? Existem três abordagens imediatas. A primeira é usar força bruta para enumerar todas as combinações entre letras e números. Cada uma das 8 letras pode assumir 10 valores distintos, então o tamanho do espaço de estados é 8**10 = 1073741824 combinações.

A segunda abordagem é notar que duas letras não podem ter o mesmo número, então você não precisa visitar todos os estados, só aqueles que contém permutações dos oito dígitos escolhidos. Assim, o espaço fica apenas com binomial(10, 8)*fatorial(8) = 1814400 combinações, quase mil vezes menor que o anterior.

A terceira é usar backtracking para eliminar da árvore de busca as combinações inválidas. Por exemplo, se você já determinou que D=7 e E=5, então Y precisa necessariamente ser 2 porque é a única possibilidade que faz a última coluna ficar correta. Essa opção é mais complicada de implementar, mas é ainda mais rápida que a anterior.

Nesse ano eu fiz um curso de Discrete Optimization no Coursera, e aprendi um método novo para resolver criptogramas. Porém, antes de explicar esse método novo, vale a pena fazer uma pausa para estudar um problema mais simples.

O problema da dieta

Enquanto o dinheiro do pai não chegava, o estudante estava dormindo de hóspede numa fazenda da região. Embora ele não pagasse nada para dormir no celeiro, ele ainda tinha que comprar comida. E só tinham três comidas disponíveis para comprar: espigas de milho, pães e copos de leite. Dado que ele precisa de pelo menos 2000 calorias por dia, e 5000 unidades de vitamina A, qual é o menor custo diário que ele pode ter para conseguir todos os nutrientes que precisa?

Porção	Calorias (kcal)	Vitamina A (IU)	Preço
Espiga de milho	72	107	$ 0.08
Copo de leite	121	500	$ 0.23
Pão	65	0	$ 0.05

Esse problema pode ser expresso através de uma série de inequações:

Na literatura, problemas com esse formato são estudados em Programação Linear, e existem vários algoritmos eficientes para resolvê-los, como os métodos de Ponto Interior, que podem ser implementados de forma a garantir uma solução em tempo polinomial. Na prática, usa-se mais o Simplex, que tem um pior caso ruim, mas também é polinomial no caso médio.

Usando essas técnicas para resolver o problema, temos que a melhor solução é comprar 17.13 espigas e 6.33 copos de leite, gastando um total de $2.82.

Mas agora tem um problema: eles não vendem 17.13 espigas, a quantidade precisa ser um inteiro. Ou você compra 17 espigas, ou compra 18. Fácil de resolver, é só arredondar para cima né? Leva-se 18 espigas e 7 copos de leite, gastando $3.05, e garantindo todos os nutrientes que você precisa.

Porém, se você fizer isso, você vai perder dinheiro! Pode conferir: se você comprar 10 espigas, 8 copos de leite, e 5 pães, vai gastar só $2.89, e continuar garantindo o mínimo de nutrientes diários. Os métodos de programação linear não funcionam quando os valores precisam ser inteiros!

Uma maneira de chegar a esse resultado é quebrando o problema em dois. Se a sua solução tem um valor fracionário, como 17.13, então você roda o Simplex mais duas vezes: na primeira adicionando a inequação M≤17, e na segunda, M≥18. Se o resultado tiver só variáveis inteiras, beleza, está resolvido. Senão, você pega a variável fracionária e quebra em dois de novo. Esse método na literatura é a Programaçao Inteira Mista (ou apenas MIP).

Opa! Peraí! Os métodos de programação linear eram polinomiais, e abrindo uma árvore em cada variável nós transformamos o método em exponencial. É uma perda de performance inaceitável!

Pois é, mas não tem jeito. Embora a programação linear seja polinomial, a programação inteira é NP-hard. Se você achar um método polinomial para resolver esse problema, então você também provou que P=NP.

Nem tudo está perdido, entretanto. Existem vários métodos para otimizar a busca, de modo que você não precise visitar todos os nós da árvore. Por exemplo, você pode usar branch and bound, branch and cut, Gomory cuts, e mais inúmeros truques que deixam o número de nós baixos o suficiente para o método ser viável na prática.

Implementar esses métodos pode ser bem difícil. A boa notícia é que você não precisa fazê-lo! Existem inúmeras bibliotecas prontas que implementam tudo isso para você, em quase todas as linguagens do mercado. A minha preferida é a SCIP, que é open source e bastante competitiva com as soluções comerciais. O único problema dela é que o público-alvo são os pesquisadores da área, então a API é bem complexa e intimidadora para quem está começando agora. Se você quer começar agora a brincar com MIP, eu tenho uma alternativa melhor.

Usando EasySCIP

Já que a SCIP é boa, mas é difícil de usar, meu primeiro instinto foi escrever uma abstração sobre ela que torne a programação mais simples. E assim surgiu o EasySCIP, um binding em C++ que é fácil de usar. Para mostrar como é simples, vamos implementar o problema da dieta em EasySCIP.

Primeiro você cria uma instância do EasySCIP:

MIPSolver solver;

Depois, cria as variáveis, uma para cada tipo de alimento. Na criação da variável, você especifica os limites onde ela pode variar (digamos, de 0 a 1000). Além disso, você passa o coeficiente dessa variável na função que vai ser minimizada (no nosso caso, é o preço de cada item):

Variable corn = solver.integer_variable(0, 1000, 0.08);
Variable milk = solver.integer_variable(0, 1000, 0.23);
Variable bread = solver.integer_variable(0, 1000, 0.05);

Agora você adiciona as inequações (constraints). Para cada inequação, você passa o coeficiente da variável, e os limites inferiores e superiores. No nosso caso, só nos importam os limites inferiores, então eu chutei um valor alto para o superior. A primeira inequação fica assim:

Constraint calories = solver.constraint();
calories.add_variable(corn, 72);
calories.add_variable(milk, 121);
calories.add_variable(bread, 65);
calories.commit(2000, 200000);

Na segunda inequação você nem precisa adicionar a variável do pão, porque ele não tem nenhuma vitamina A.

Constraint vitamin_a = solver.constraint();
vitamin_a.add_variable(corn, 107);
vitamin_a.add_variable(milk, 500);
vitamin_a.commit(5000, 500000);

Agora é só resolver e ler os valores finais:

Solution sol = solver.solve();
cout << "Corn: " << sol.value(corn) << "\n";
cout << "Milk: " << sol.value(milk) << "\n";
cout << "Bread: " << sol.value(bread) << "\n";

O programa completo você pode ver no github. Rodando o programa, ele retorna a solução que esperávamos:

Corn: 10
Milk: 8
Bread: 5

Agora já temos as ferramentas que precisávamos para resolver o problema original!

Criptoaritmética com MIP

MIP é uma ferramenta excelente para resolver puzzles. Tudo que você precisa fazer é arrumar uma maneira de transformar seu puzzle em um sistema de inequações; feito isso, o framework faz todo o serviço sujo para você.

O problema então deixa de ser programação e passa a ser modelagem. Qual o melhor modelo que representa seu puzzle? Um truque que funciona na maioria das vezes é introduzir variáveis binárias que codificam as informações do seu puzzle.

Por exemplo, a letra S vai ser associada a um dos dígitos de 0 a 9, mas ainda não sabemos qual. Vamos então introduzir dez variáveis binárias: b_S0, b_S1, .., b_S9. Cada uma deles pode assumir o valor 0 ou 1. Por exemplo, se na solução final descobrirmos que S=9, então teremos b_S9=1, e as outras nove variáveis são zero.

Mas sabemos que a letra S precisa estar associada a um dígito, e não mais que um. Isso pode ser expresso como a nossa primeira equação:

Confira: para a equação ficar correta, se uma das variáveis for 1, então todas as outras precisam ser 0. (Os mais atentos podem reclamar que eu usei uma equação ao invés de uma inequação, mas não tem problema; toda equação da forma A=k pode ser escrita como duas inequações encadeadas: k ≤ A ≤ k).

Repetindo uma equação dessas para cada letra, nós garantimos que a cada letra corresponde um dígito. Mas isso não é suficiente, você também precisa garantir o oposto: a cada dígito precisa corresponder uma letra. Sem essa condição adicional, você poderia ter uma solução do tipo S=9 e E=9 (mas não podemos ter o mesmo dígito em duas letras distintas).

A solução é parecida com a anterior. Para o dígito 9, por exemplo, teremos:

Note que temos apenas oito letras distintas para dez dígitos, então pelo menos dois dígitos vão sobrar. Como não temos como garantir qual dígito será utilizado, usamos uma inequação ao invés de uma equação.

Outra regra que precisa ser modelada é que nenhum número pode começar com zero. Isso é o mesmo que dizer que as letras S e M não podem ser zero. Mais duas equações resolvem isso:

Agora falta só modelar a soma em si. Antes de começar, vale notar que o problema tem quatro variáveis binárias escondidas que você precisa levar em conta: os carrys de cada coluna.

Agora basta escrever uma equação por coluna. Para a coluna mais à direita, por exemplo, teríamos algo do tipo D+E=Y+10c₀ em decimal. Usando as nossas variáveis binárias, a equação completa fica:

Parece assustador, mas é só uma equação linear simples. Fazendo mais uma dessas para cada coluna do nosso puzzle, o modelo está quase completo: falta só uma função objetivo. Se vamos usar MIP, precisamos minimizar alguma coisa. Mas o que minimizar? Nosso modelo já está completo sem a necessidade de minimizar nada, então podemos fornecer uma função constante para ele minimizar. Na linguagem da área, nós estamos buscando feasibility, e não optimality.

Com todas as inequações prontas, podemos rodar o modelo no EasySCIP. O código completo está no github, e, após rodá-lo em meu computador, tive a resposta em 0.116s, o que é bastante respeitável! Mas ainda dá para melhorar :)

Criptoaritmética com MIP, segundo modelo

Eu sei que gostar de resolver criptoaritmética parece coisa da maluco, mas eu não sou o único maluco nesse mundo, tem o Knuth também! No volume 4A do Art of Computer Programming, ele dá uma dica muito boa para resolver criptogramas: a análise das assinaturas. Vamos isolar a letra E no puzzle original, trocando os lugares onde ela aparece por 1, e onde não aparece por 0:

 

Após a substituição, nós obtemos a assinatura da letra E, que vale 100+1-10, ou seja, 91. A sacada do Knuth é que, na solução final, a soma das assinaturas precisa necessariamente valer zero:

Usando variáveis inteiras ao invés de variáveis binárias, poderíamos colocar essa equação diretamente no modelo, e aí não precisaríamos das equações de cada coluna! Mas podemos fazer ainda melhor: o MIP sempre quer uma função para minimizar, então podemos mandar ele minimizar a soma das assinaturas. Assim, os métodos de branch and bound implementados pelo SCIP podem jogar fora mais nós da árvore durante o processamento, o que acelera a busca.

O único problema é ele resolver minimizar tanto a soma das assinaturas, que ela acabe ficando negativa. Para evitar isso, é só adicionar essa restrição manualmente. Por exemplo, ele pode minimizar a variável X, onde X satisfaz:

Ainda precisamos adicionar as regras de que a cada letra corresponde um único dígito e vice-versa. Vamos manter as variáveis binárias do modelo anterior, e ensinar o modelo a converter entre variáveis binárias e variáveis inteiras. Por exemplo, a letra D ficaria:

Com isso o modelo está completo. O código está no github, e rodando no EasySCIP, ele chega no mesmo resultado que o modelo anterior, porém usando apenas 0.052s, quase metade do tempo!

Conclusão

Quando eu devo usar MIP ao invés de outros métodos, como backtracking? O backtracking vai criar uma divisão na árvore de busca cada vez que definir o valor de uma variável, mas o MIP roda uma iteração de programação linear em cada nó, o que potencialmente pode definir várias variáveis ao mesmo tempo. A minha experiência é que o MIP ganha sempre que você conseguir criar um modelo que permita essa otimização global.

Como comparação, lembre que a força bruta examinava 1073741824 nós, e a análise de permutações visitava 1814400 nós. Olhando no log do EasySCIP, eu vejo que o primeiro modelo com variáveis binárias visitou apenas 9 nós, e o segundo modelo com assinaturas resolveu tudo em um único nó! A programação linear achou a solução inteira sem nenhum branch! Pelos números, é bem claro que vale a pena aprender a escrever modelos MIP :)

Metaprogramming com constexpr

Até ano passado, quando eu queria fazer algum projetinho onde eu precisava da maior velocidade possível, acabava escolhendo escrevê-lo em C++. Mas a minha vida mudou quando eu conheci o C++0x. Ele é muito superior ao C++ tradicional, adicionando features que faziam muita falta, como lambdas, variáveis auto e range for.

Uma das features novas que mais gosto é o constexpr, uma maneira de avisar ao compilador que o resultado de função pode ser determinado em tempo de compilação. Combinando isso com funções recursivas, nós temos uma maneira nova de fazer metaprogramming em C++, bem melhor que o tradicional template metaprogramming.

Para mostrar a superioridade do constexpr, resolvi escrever de três maneiras diferentes uma função bem simples: o totiente de Euler, cuja definição é a quantidade de inteiros positivos menores que n, e que não possuem fatores em comum com n. Escrito em C++ tradicional, essa função fica assim:

int gcd(int a, int b) {
  if (b == 0)
    return a;
  else
    return gcd(b, a % b);
}

int totient(int x) {
  int sum = 0;
  for (int i = 1; i < x; i++) {
    if (gcd(x, i) == 1) sum++;
  }
  return sum;
}

int main() {
  cout << totient(1000) << endl;
}

O código em si é bem simples de entender e compila em qualquer lugar. Eu calculei o GCD usando o algoritmo de Euclides, que é O(log n), então essa implementação do totiente é O(n log n).

Compare agora com o mesmo algoritmo escrito em template metaprogramming:

template<int a, int b>
struct GCD {
  const static int result = GCD<b, a % b>::result;
};

template<int a>
struct GCD<a, 0> {
  const static int result = a;
};

template<int x, int i>
struct TotientHelper {
  const static int result =
      (GCD<x, i>::result == 1) +
      TotientHelper<x, i - 1>::result;
};

template<int x>
struct TotientHelper<x, 0> {
  const static int result = 0;
};

template<int x>
struct Totient {
  const static int result =
      TotientHelper<x, x - 1>::result;
};

int main() {
  const int x = Totient<1000>::result;
  cout << x << endl;
}

Essa versão é bem mais difícil de entender e é cheia de boilerplate. A vantagem dela é que o cálculo do totiente é feito em tempo de compilação; então, em runtime, o resultado é calculado em O(1).

Por fim, a versão em c++0x usando constexpr:

constexpr int gcd(int a, int b) {
  return b == 0 ? a : gcd(b, a % b);
}

constexpr int totient(int x, int i) {
  return i == 0 ? 0 : (gcd(x, i) == 1) + totient(x, i - 1);
}

constexpr int totient(int x) {
  return totient(x, x - 1);
}

int main() {
  constexpr auto x = totient(NUMBER);
  cout << x << endl;
}

Essa versão não é tão simples quanto a que calcula em runtime, mas também não é excessivamente complexa como a versão com templates.

Para fazer metaprogramming com constexpr, você só precisa seguir algumas regras simples:

• O corpo da função precisa ter um único return.
• Você não pode usar if. Se você precisar de condicionais, tem que usar o operador ternário.
• Você não pode usar for. Se você precisar de loops, tem que usar recursão.
• Você não pode fazer atribuições a variáveis.
• Uma pegadinha: ele só faz o cálculo em compile time se você atribuir o resultado a uma variável constexpr. Se você tentar fazer diretamente cout << totient(100), ele vai calcular em run-time.

Além disso, obviamente, você precisa de um compilador que suporte constexpr. Até onde eu sei, o único que aceita constexpr é o gcc 4.7 ou superior.

Mas a grande vantagem do constexpr sobre os templates não é só a facilidade de programação: é o tempo de compilação. Um programa com constexpr compila muito mais rápido que uma versão com templates. Para comparar o tempo de compilação, eu fiz um script que mede o tempo para vários valores do totiente:

Script em C++ para calcular o totiente em run-time
Script em C++ para calcular o totiente com templates
Script em C++0x para calcular o totiente com constexpr
Script em Python para medir o tempo dos programas acima

Vamos primeiro comparar o tempo de compilação da versão em runtime com a versão em template:

Como esperado, o tempo de compilação da versão em runtime é constante e bem pequeno. Já a versão em template é bem ruinzinha. Eu fiz uma regressão para determinar que curva é essa, e o resultado é que é uma parábola (com coeficiente de determinação R²=0.999, ou seja, com bastante certeza).

Agora a fraqueza do método com templates é evidente: o algoritmo era O(n log n) em runtime, virou O(n²) em compile-time. Veja como isso não acontece com a versão com constexpr:

Ah, agora sim! A versão com constexpr continua sendo O(n log n), só trocou o tempo de run-time pelo tempo de compilação. Comparado o template nem tem graça: para n=30000, a versão com constexpr compila em 1 segundo, e versão em template compila em 2 minutos.

A essa altura já estamos convencidos de que o constexpr é o melhor jeito de implementar metaprogramming, mas ainda falta a pergunta crucial: na prática, pra que isso serve?

Para mim, a utilidade mais imediata é pra conseguir primeiro lugar nos problemas do spoj! Como o spoj só leva em conta o tempo de run-time para ordenar as soluções, se você jogar um pouco do tempo do run-time para a compilação, consegue subir algumas colocações no ranking :)

O algoritmo mais lento do oeste

Por que as pessoas aprendem complexidade computacional? Para achar os algoritmos mais rápidos, é claro. Dada uma lista de algoritmos equivalentes, você pode ordená-los pela complexidade, e o primeiro da lista é o mais eficiente.

Uma brincadeira divertida é fazer isso ao contrário: dada uma especificação, qual o algoritmo determinístico mais lento que a resolve? Por exemplo, qual o algoritmo mais lento para decompor um número em fatores primos?

O algoritmo mais rápido que resolve esse problema é o algoritmo de Shor, que roda em O((log n)³) e requer um computador quântico. Meu candidato a algoritmo mais lento é o abaixo, que na falta de nome melhor eu chamei de Fatoração Bozo:

import itertools

def factor(n):
 solutions = []
 for f in itertools.product(range(1,1+n),repeat=n):
   if reduce(lambda x,y: x*y, f) == n:
     solutions.append(filter(lambda x:x>1, list(f)))
 solutions.sort(key=len, reverse=True)
 return solutions[0]

Parece complexo, mas o funcionamento é bem simples. Vamos pensar no nosso objetivo: queremos achar uma lista de fatores primos, que multiplicados resultam no número desejado (vamos chamá-lo de N).

Nós sabemos que os primos dessa lista são menores ou iguais a N, e sabemos também que essa lista nunca vai ter mais que N elementos. A primeira coisa que fazemos no algoritmo é gerar todas as possíveis listas candidatas, que são o produto cartesiano do intervalo de 1 a N com N repetições. Por exemplo, para N=3, teríamos 27 combinações:

111 112 113 121 122 123 131 132 133
211 212 213 221 222 223 231 232 233
311 312 313 321 322 323 331 332 333

Em python o jeito mais fácil de gerar essa lista é usando itertools.product(), que faz o serviço sozinho. Mas, dessas listas, só interessam aquelas cujo produto seja igual a N. Por exemplo, se N=4, então as listas interessantes são:

1114 1122 1141 1212 1221
1411 2112 2121 2211 4111

Python não tem um operador para multiplicação de listas como tem o sum() para adições, mas pra isso que serve o reduce() né. As listas selecionadas até agora estão boas, mas elas têm um monte de elementos 1 que não contribuem em nada. Usando o filter() podemos jogar fora os uns. Para N=4:

4 22 4 22 22 4 22 22 22 4

Várias listas repetidas, mas tudo bem. O truque agora é notar que, de todas essas listas, a fatoração em primos é a lista de comprimento máximo. É fácil provar isso: se a lista máxima tivesse um elemento composto, então você poderia fatorá-lo, e trocar o número composto pela sua fatoração. Logo, você estaria gerando uma lista maior que a lista máxima, o que é uma contradição.

Pedindo para que o Python ordene as listas por tamanho, basta pegar a primeira lista da seqüência e temos então a nossa fatoração!

E qual a complexidade dessa solução? Ela é dominada pelo número de listas que geramos no primeiro passo, então a complexidade da Fatoração Bozo é maior que O(nⁿ). Se você não tem noção de como isso é lento, veja o tempo que esse código leva para fatorar alguns números:

N=6 - 0.2 segundos
N=7 - 2.1 segundos
N=8 - 45.8 segundos
N=9 - 20 minutos

A função cresce tão rapidamente que, para fatorar N=18, você levaria mais tempo que a idade do universo até agora! Como exercício para o leitor, tente calcular quanto tempo levaria para fatorar o RSA-704, que em decimal tem 212 dígitos :)