segunda-feira, 19 de março de 2018

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!

sexta-feira, 19 de janeiro de 2018

O dia que o Knuth ganhou meu cheque

No último dia 10, o Donald Knuth completou 80 anos de vida. Para comemorar, ele fez uma festinha na remota e gelada cidadezinha de Piteå, no norte da Suécia, e eu tive a sorte de poder participar. A festa foi em formato de simpósio de matemática: ao invés de presentes, cada amigo apresentou uma palestra sobre um tema relacionado ao trabalho do Knuth. (E os amigos dele são os caras mais famosos da computação, estavam lá o Sedgewick, o Karp, o Tarjan, entre outros).



Eu também fiz minha contribuição, presenteei o Knuth com vários artigos contendo idéias para futuras revisões dos livros dele. Mas em um dos artigos aconteceu uma coisa engraçada: o Knuth notou que uma das minhas contas podia ser simplificada, e como agradecimento pela sugestão eu tive a oportunidade de inverter expectativas, e dar um cheque para o Knuth :D


A Soma dos Quadrados


O artigo em questão era uma sugestão para o Concrete Mathematics, que é o meu livro de matemática predileto. Sou fã desse livro desde os 17 anos, quando o usava como referência para estudar para a Olimpíada de Matemática.

Quem já leu sabe que o livro contém mais de dez demonstrações diferentes da fórmula para a soma dos quadrados. Para ##n\ge 0##, a fórmula é:
$$\sum_{1\le x\le n} x^2=\frac{n(n+1)(2n+1)}{6}$$
As demonstrações vão desde as mais simples (usando indução finita), até as mais complexas (usando a fórmula de Euler-MacLaurin). Porém, uns anos atrás, eu bolei uma demonstração nova que é provavelmente a mais curta demonstração de todas! Ela está na caixa azul abaixo:


Testando valores pequenos, notamos que a fórmula é verdadeira para ##n=0##, ##n=1##, ##n=2##, ##n=3##. Logo, é verdadeira para qualquer ##n##.

Sim, eu sei o que você está pensando: "Ricbit, você tá doido? Só porque funciona para alguns números não quer dizer que funciona para todos os números!".

A preocupação é válida: o que mais tem na matemática são fórmulas que funcionam para números pequenos mas falham para números grandes. Um exemplo famoso é o polinômio sortudo de Euler, ##k^2-k+41##, que produz apenas números primos para ##k=1##, ##k=2##, ##k=3##, etc., mas falha lá na frente quando ##k=41##.

Porém, nesse caso, testar números pequenos é suficiente para demonstrar a fórmula! Para entender o motivo precisamos de dois fatos sobre cálculo e polinômios.


O Cálculo Discreto


Quem já estudou cálculo com certeza sabe algumas integrais de cabeça. Por exemplo, a integral do monômio:
$$\int x^n\;dx=\frac{x^{n+1}}{n+1}$$
O que você talvez não saiba é que o cálculo que a gente aprende nas faculdades de exatas é só um tipo de cálculo: o Cálculo Contínuo. Existem outros tipos, como o Cálculo Discreto, que lida com somatórias ao invés de integrais. Esse cálculo possui várias fórmulas análogas ao cálculo mais comum. Em especial, ele tem uma fórmula análoga à integral do monômio:
$$\sum x^{\underline{n}}\;\delta x=\frac{x^{\underline{n+1}}}{n+1}$$
Nesse fórmula o monômio não usa a potência simples, ele usa a potência fatorial, que é definida da seguinte maneira:
$$x^{\underline n}=x(x-1)(x-2)\dots(x-n+1)$$
É como se fosse um fatorial, mas ao invés de ir até o fim, você pega só os ##n## primeiros termos. (Para pronunciar ##x^{\underline n}##,  você fala "x elevado a n caindo").

Para converter uma potência fatorial em uma potência normal, você pode abrir a definição e multiplicar todos os termos, mas isso dá trabalho. É mais fácil ter à mão uma tabela com os números de Stirling (que vêm em dois tipos, o primeiro tipo ##{n\brack k}##, e o segundo tipo ##{n\brace k}##). Esses números são fáceis de calcular porque eles obedecem uma regra similar ao triângulo de Pascal.  Tendo a tabela, as fórmulas abaixo fazem a conversão:
$$\begin{align*}
x^{\underline{n}}&=\sum_k{n\brack k}(-1)^{n-k}x^k\\
x^{n}&=\sum_k{n\brace k}x^{\underline{k}}\end{align*}$$
Usando as fórmulas acima e alguma paciência, você consegue demonstrar a fórmula da soma dos quadrados (converta ##x^2## em potências fatoriais, use a fórmula de somatória do cálculo discreto, depois converta de volta as potências fatoriais em potências tradicionais).

Mas isso dá muito trabalho. Ao invés disso, note que as fórmulas acima tem uma consequência interessante: com elas é possível ver que a somatória de um polinômio de grau ##n## sempre vai ser um polinômio de grau ##n+1##, e em especial a somatória de ##x^2## vai ser um polinômio de grau 3, a gente só não sabe qual polinômio ainda. Mas aí temos outro truque nas mangas!

Interpolação de polinômios


Certo, eu não sei qual é o polinômio de grau 3 que resolve a somatória. Vamos então escrever esse polinômio na forma ##P(n)=an^3+bn^2+cn+d##. Apesar de não conhecermos o polinômio, é fácil descobrir os pontos por onde ele passa, basta calcular a somatória!

Para valores pequenos de ##n##, podemos tabelar ##P(0)=0##, ##P(1)=1##, ##P(2)=1+4=5##, ##P(3)=1+4+9=14##, agora podemos achar os coeficientes usando álgebra linear:
$$\left[\begin{array}{c}0\\1\\5\\14\end{array}\right]=
\left[\begin{array}{cccc}0^3&0^2&0^1&1\\1^3&1^2&1^1&1\\2^3&2^2&2^1&1\\3^3&3^2&3^1&1\end{array}\right]
\left[\begin{array}{c}a\\b\\c\\d\end{array}\right]$$
Novamente, dá muito trabalho. Ao invés disso, notamos que um polinômio de grau ##n## fica completamente determinado por ##n+1## pontos, e agora podemos finalmente entender a demonstração inicial!

Olhe novamente para o que queremos demonstrar:
$$\sum_{1\le x\le n} x^2=\frac{n(n+1)(2n+1)}{6}$$
De um lado, temos uma somatória de polinômios de grau 2, que sabemos que é um polinômio de grau 3. Do outro lado, temos um polinômio cujo grau também é 3. Para provar que esses dois polinômios são iguais, é suficiente testar os dois polinômios em quatro pontos. Escolhemos os mais fáceis que são ##n=0##, ##n=1##, ##n=2##, ##n=3##, como a fórmula funciona para esses quatro valores, então funciona para todos os valores, QED.

O cheque do Knuth


Quando eu presenteei o artigo com essa demonstração para o Knuth, em segundos após a leitura ele comentou: "Você podia ter usado -1 aqui!".

É verdade! Essa demonstração é tão curta que dá para fazer de cabeça, mas as contas para ##n=3## ficam meio chatinhas. Ao invés disso, você pode usar -1 no lugar de 3, e aí fica bem mais fácil: do lado esquerdo a soma é vazia e dá 0, do lado direito o termo ##(n+1)## zera, logo o resultado dá zero também. Você precisa expandir o domínio da fórmula, de ##n\ge 0## para ##n\ge -1##, o que significa que a fórmula provada com -1 é até melhor que a fórmula provada com 0!

Tradicionalmente, o Knuth oferece $0x1 hexadólar para quem acha um erro em um artigo dele, e $0x0.20 para sugestões. Pela simplificação que ele sugeriu, eu achei pertinente oferecer um cheque também!


Aqui o detalhe do cheque. O Knuth emite cheques pelo banco fictício de San Serriffe (eu tenho $0x5.80 lá atualmente). Os meus cheques eu resolvi emitir pelo Banco de Dados:


O Knuth adorou o cheque! Ele ficou impressionado em como eu consegui fazer tão rápido um cheque que parece mesmo um cheque, mas o segredo é simples: quem fez fez a arte foi a Ila Fox, eu só imprimi no hotel onde estava, usando papel reciclado.

Sem dúvida foi a melhor festa de aniversário que já participei! O Knuth já tinha feito uma festa dessas quando completou 64 anos, e para manter a simetria ele disse que vai fazer outra quando completar 96 anos. Eu certamente estarei lá mais uma vez :)