Arquivos da categoria: Geek

Posts para iniciados em ciência que ainda não completaram seu treinamento Jedi. Estudantes em faculdades de exatas são o que tenho em mente nessas publicações.

O problema da diretora do colégio

Geek

Venho por meio deste compartilhar um problema deveras interessante que requereu algumas horas do meu dia para a programação. Escrevi-o há algum tempo a um amigo cursando ciência da computação que, sendo garoto de programa, certamente saberia apreciar o que fiz, e sou carente desse tipo de apreciação. O problema que me foi proposto em meu curso de física estatística foi o da diretora do colégio.

Aconteceu uma vez comigo, recebi, acho que na sexta série, um papel para escrever os nomes dos coleguinhas com que gostaria de estar ano seguinte. Escrevi os dois nomes que queria (era uma criança sozinha e com poucos amigos), entreguei e no ano seguinte estava na sala deles. Ainda, as salas não mudaram muito, o que é razoável, já que as pessoas tendiam a querer ficar com quem já estavam, achei que a diretora havia atendido aos pedidos individualmente, mas hoje penso que não. Vamos tentar entender a razão de, se a diretora fosse realmente levar aqueles papéis a sério, ela teria que aprender um pouco mais de física e informática.

Imagine-se uma diretora de colégio, responsável por preparar as classes para o próximo ano letivo. Como você é boazinha, decide deixar os alunos escolherem com quem eles querem ficar no próximo ano, então dá a possibilidade de eles escreverem em um papel nomes dos coleguinhas que mais querem encontrar no ano seguinte. Mas sendo uma diretora justa, você pergunta aos professores quais alunos seria melhor que não ficassem na mesma turma, uma “lista negra” de duplas que seria melhor que ficassem separados. Com essas duas informações: a preferência dos alunos e a lista negra dos professores, como determinar qual distribuição ideal de alunos?

Esse não é um problema fácil. Podemos pensar em tratar o problema brutalmente: listar todas as possibilidades e verificar qual satisfaz melhor às condições das listas, tanto a de preferência quanto a de exclusão, mas isso, com um número pequeno de alunos, logo atinge limites astronômicos. O número de configurações possíveis de sala será $2^{\text{numero de alunos}}$, com 100 alunos você teria algo perto de $10^{30}$ configurações. Meu processador i5 só aguenta algo perto de 10MIPS, o que me dá o direito de realizar $10^7$ instruções por segundo e eu precisaria de pelo menos $10^{23}$ segundos para fazer qualquer coisa com essas configurações, isso é mais que a idade do universo. Essa conta provavelmente está bem errada, mas acredito no argumento de que, para listar todos os casos possíveis, terei que investir mais que uma tarde em cálculos. Precisamos pensar em um jeito mais malandro.

Primeiro, vamos pensar no quadro teórico do problema e como implementar de maneira adequada. Eu quero um jeito prático de saber quantas condições uma configuração de alunos satisfaz e quantas ele viola. Vou atribuir pesos iguais à preferência dos alunos e à lista dos professores, poderiam ser diferentes, mas sou preguiçoso. Seja n o número de alunos. Tomo um vetor $S_n$ com $n$ coordenadas que podem valer 1 ou -1. Se $S_i=1$, então o aluno $i$ está na sala A. Se $S_i=-1$, o aluno $i$ está na sala B.

Em seguida, defino a matriz $J_{ij}$, que é $n\times n$. Ela contém a seguinte informação: $J_{ij} = 1$ se o aluno $i$ quer ficar com o aluno $j$. $J_{ij} = -1$ se não é legal que o aluno $i$ fique com o aluno $j$ e $J_{ij}=0$ se eles são indiferentes entre si. Eu poderia ter privilegiado a opinião dos professores atribuindo um peso muito negativo ao invés de -1, mas vamos dar uma chance as alunos e atribuir pesos iguais às preferências dos alunos e dos professores. Isso vai servir para calcular o quanto de “felicidade” a configuração gera. Se dois alunos estão na mesma sala e queriam estar na mesma sala, a felicidade aumenta. Se eles não podem estar na mesma sala e estão em salas separadas, a felicidade aumenta. Se estão em salas diferentes e queriam estar juntos, ela diminui. Mas como computar isso? Basta calcular: $J_{ij}\cdot S_i\cdot S_j$.

Se eles estão na mesma sala, o produto $ S_i\cdot S_j$ será 1 e, se querem estar na mesma sala, $J_{ij}$ será 1, então o resultado será 1. Se não podem e estão na mesma sala, o resultado será -1. Se não estão na mesma sala, o produto $S_i\cdot S_j$ é -1. Deu para entender que esse produto representa bem a “felicidade” gerada pelo estudo de um par de alunos. Precisamos, então somar $J_{ij}\cdot S_i\cdot S_j$ para todos os $i$’s e $ j$’s e isso dará a felicidade da configuração.

Mais uma vez, isso exige produtos e somas com $2^n$ configurações possíveis, é absolutamente impossível resolver esse problema na força bruta para mais de 50 alunos. Para tal, precisamos de um método mais eficiente, e eu escolho Monte Carlo.

O método de Monte Carlo é um dos mais poderosos e usados na física estatística para resolver esse tipo de problema impossível. Tomamos uma configuração inicial de classes aleatória (um vetor $S$ aleatório) e procedemos da seguinte forma:

  • Trocamos um aluno de sala (tiramos $i$ aleatório e fazemos $S_i\to -S_i$)
  • Checamos a felicidade da nova configuração.
  • Se aumentou, ele fica nessa sala nova.
  • Se diminuiu, ele volta para a primeira sala.

Você ficaria impressionado em saber que, com 50 alunos, eu consigo a configuração certa de $S$ em menos de 1000 iterações. Claro, tomei um $J$ agradável o suficiente para que eu soubesse qual a configuração certa e esse $J$ em particular provavelmente facilitou minha vida. Tomei a sala em panelinha: metade dela quer ficar entre si e não pode ficar com a outra metade. Eu esperava um S da forma $(1,1,\ldots ,1,-1,-1,\ldots ,-1)$, e o tenho rapidamente com esse algoritmo.

Sabendo um pouco mais de física, eu poderia te contar que os átomos possuem uma propriedade chamada spin, que pode apontar para cima (1) ou para baixo (-1). Em uma rede cristalina, os spins interagem e são capazes de definir muita coisa, como, por exemplo, se a rede será um imã ou não. O que acontece é que os spins sempre atingem uma configuração que minimiza a energia da rede, e essa energia é calculada se o material é antiferromagnético (os spins gostam de ficam em direções opostas) ou ferromagnético (eles preferem se alinhar). Em algumas redes, você até mistura esses dois tipos e calcular a magnetização total (o conjunto de todos os spins) pode parecer um inferno.

Mas a energia total é calculada da seguinte forma: você multiplica os spins para saber se estão alinhados ou não, se estão, o produto será positivo, se estão invertidos, o produto será negativo. E então você multiplica pelo fator $J_{ij}$, que vale 1 se o material é ferromagnético ou -1 se é antiferromagnético (ou 0 se os spins estão longe e não interagem). A energia total será a soma para todos os i’s e j’s de $J_{ij}\cdot S_i\cdot S_j$ onde $S_i$ é o spin da partícula $i$. A magnetização do sistema será a configuração de spins que minimiza essa energia. Ora, é difícil não ver que a magnetização de um material misto entre dia e ferromagnetismo é o exato mesmo problema que uma diretora de escola enfrenta ao escolher quais alunos ficarão em qual sala.

Esse método, Monte Carlo, parece quase milagroso, mas possui um problema grave. Não é o caso da matriz $J$ que escolhi, que é extremamente agradável, mas com algum outro $ J$ eu poderia ter um sério problema. Eu poderia atingir uma configuração em que trocar qualquer aluno de sala causaria uma queda na felicidade, mas que, se eu trocasse dois ou três, poderia ter um ganho. Esse tipo de situação é um “mínimo local” da felicidade, um defeito sério em Monte Carlo, que não pode escapar de um mínimo local e atingir a verdadeira configuração ideal de salas, pois ele só aceita ganhos reais e imediatos. Como podemos nos livrar disso? Ah, precisamos de uma adaptação de Monte Carlo, chamada “Algoritmo de Metrópolis”, mas isso fica para outro dia, a diretora da minha sétima série, pelo que escrevi, já terá bastante trabalho pela frente.

1 resposta

O famigerado laplaciano

Geek

O terceiro semestre de cálculo na faculdade é inesquecível. Se o seu curso foi parecido com o meu, você atravessou integrais duplas, triplas, de linha e de superfície, teoremas de Gauss, de Green e de Stokes, todas aquelas parametrizações e todas aquelas integrais. Não são poucas as áreas na física que usam esses conceitos, em especial a mecânica dos fluidos e o eletromagnetismo. As aplicações são tantas que, muitas vezes, as demonstrações dos teoremas e representações dos elementos dessa teoria deveriam ser tão naturais para nós quanto ver água descendo o ralo, mas nosso professor de matemática dificilmente está interessado em água descendo o ralo e acaba sacando da manga exemplos não tão intuitivos; meu professor de sistemas dinâmicos, por exemplo, achava a teoria mais clara quando a aplicava a teoria dos números, o que era para ser uma explicação do pêndulo duplo acabava virando o estudo da função “menor inteiro” para provar algum teorema de Fermat.

Todas essas operações têm uma interpretação física bem clara e bonita, mas o laplaciano, esse incompreendido, sempre escapa aos professores de cálculo. Tentar explicá-lo como “o divergente do gradiente” é dar um nó nos conceitos. Você precisa imaginar a taxa de dispersão de um campo que aponta para a direção de maior crescimento, isso me dá dor de cabeça apenas em tentar e não me traz nenhuma ideia clara e física do que é $ \nabla^2 T$.

Nessa hora, vale mais voltar às raízes do cálculo e tentar atacá-lo com métodos finitos, ou seja, fingir que a derivada é apenas um quociente da forma $ \frac{\Delta T}{\Delta x}$. Isso é bem feio e eu jamais faria isso em uma demonstração séria, mas é a técnica padrão para uma resolução numérica da equação de Poisson ou de Laplace, então pode nos ajudar. Se eu decompuser o espaço em intervalos de $ \Delta x_i$ e tomá-los iguais e no valor da unidade, a derivada discretizada torna-se $ x_{i+1}- x_i$. A segunda derivada será apenas tomar esse valor e subtrair ao da derivada do ponto anterior, ou seja, $ x_{i+1}- x_i – x_i + x_{i-1} = x_{i+1} + x_{i-1} – 2x_i$. Esse é um método finito bem adequado para calcular numericamente a segunda derivada. Em uma dimensão, ela coincide com o laplaciano.

Se o meu campo fosse em duas dimensões, eu poderia representar a discretização do meu campo com dois índices, cada ponto seria da forma $ x_{i,j}$. A segunda derivada em uma direção seria a expressão acima variando o $ i$ e na outra direção seria a variação em $ j$. O laplaciano, soma das segundas derivadas cartesianas, seria: $ x_{i+1,j} + x_{i-1,j} + x_{i,j+1} + x_{i,j-1} – 4x_{i,j}$.

Se essa expressão ainda não lhe diz nada, experimente dividir por 4. Você terá:

\[\frac{1}{4}\nabla^2X\approx \frac{x_{i+1,j}+x_{i-1,j}+x_{i,j+1}+x_{i,j-1}}{4} – x_{i,j}\].

Agora parece mais claro. O laplaciano é proporcional à diferença entre o valor em um ponto e a média de seus vizinhos. Isso nos leva à ideia de concentração, se o laplaciano for muito negativo em um ponto, podemos entender que o valor do campo nesse ponto é muito maior que a média de seus vizinhos, ou seja, sua vizinhança apresenta um descrescimento alto em alguma direção que está puxando a média para baixo.

Encontramos essa ideia na física em diversas circunstâncias. Uma onda, por exemplo, é um sistema que representa “coesão” entre seus elementos, puxe uma ponta de uma corda para cima e para baixo e esse puxão irá se propagar pela corda. O que acontece nesses sistemas coesos é que cada elemento é fortemente puxado por seus vizinhos e supomos que todos os vizinhos puxam igualmente, ou seja, o elemento sobe se a média dos vizinhos estiver acima dele e desce se a média dos vizinhos estiver abaixo dele. Não somente isso, a força com que ele é puxado deve ser proporcional a essa diferença. E com força eu digo aceleração, já que nem todas as ondas são mecânicas e o conceito de força não se aplicaria tanto a elas. Em outras palavras: a aceleração do elemento será proporcional à diferença entre sua altura e a altura média de seus vizinhos. Não por menos, a equação de onda deve ser:

\[\frac{d^2X}{dt^2}+k^2\nabla^2X=0\]

E isso explica a equação de onda ser o que é. Todo sistema coeso deve obedecer a esse sistema, toda perturbação sua propagar-se-á de acordo com essa equação, desde que cada elemento seja puxado ou empurrado por seus vizinhos igualmente.

Folheando um livro de física-matemática, você pode se deparar com teoremas como “As soluções da equação de Laplace não possuem máximo ou mínimo locais no interior de seu domínio, apenas nas bordas.”. Pensando um pouco, isso é bem evidente. Se $ \nabla^2 X = 0$, que é a equação de Laplace, então todo ponto deve ser a média de seus vizinhos, pois a diferença entre eles é sempre nula. Ora, nenhuma média pode ser maior ou menor que nenhuma de suas parcelas, então um ponto de uma solução da equação de Laplace não pode mesmo ser nem mínimo, nem máximo.

E, com isso, fica bem mais fácil entender algumas propriedades e algumas fórmulas que contêm esse triângulo ao quadrado. Em cálculo de várias variáveis, as melhores analogias costumam estar na mecânica dos fluidos ou no eletromagnetismo, não hesite em procurar.

5 respostas

Introdução

Geek Hardcore Rookie

Primeiro post, vamos ver no que isso vai dar.

Todo texto ou artigo começa com uma introdução, aquela parte que quase ninguém lê. Precisava ser justo e começar eu também nessa, explicando a que veio este blog.

Gosto de física e de matemática. Sou físico estatístico, terminando meu mestrado e caminhando para um doutorado, se os ventos permitirem. Muita coisa me fascina no que faço, sou desses apaixonados pela ciência, pelos resultados, pelo desafio e pelas pessoas que a fazem. Gosto de tanta coisa que esse blog ficaria injusto se focasse em um público, se fosse apenas divulgação ou apenas física avançada, então decidi criar três categorias e postar de acordo. A primeira, rookie, é para quem não viu mais ciência do que lhe foi martelado no colegial com musiquinhas e provas de raciocínio a lápis e resposta a caneta. A segunda, geek, é para os que se aventuraram a continuar, ou ainda estão neste treinamento, nas artes das exatas pelo ensino superior; penso em engenheiros, químicos ou estudantes de faculdade nessa categoria. A última, hardcore, é para os que concluíram o treinamento em física ou matemática, estão à vontade com epsilons e deltas, com bras e kets, com difeomorfismos e fibrados tangentes.

Não tenho tema específico, gosto de coisas bonitas na ciência. Sou físico estatístico, o que explica o título do blog; nessa área, estamos cansados de fazer o que chamamos de “soma sobre todas as configurações possíveis”, a base da definição de entropia e de algumas coisinhas mais. Claro, os posts podem acabar tendenciosos, mas não posso evitar, não posso escrever sobre super-cordas se não aprendi super-cordas, não me arrisco nas álgebras de Hopf se jamais me aventurei tanto na teoria das representações. Talvez mude de ideia, talvez Hopf me conquiste, não tenho compromissos com áreas ou gostos no que escrevo.

Vejamos no que estes textos vão dar. Meu único propósito é divertir quem lê, vocês, tentando compartilhar um trecho da beleza na ciência, que tanto é profanada nos impiedosos bloquinhos em plano inclinado de nosso ensino médio. Porque toda ciência começa como filosofia e termina como arte, sua beleza é difícil de deixar de perceber. Ela é, diferentemente de toda poesia, verdade, o que a reveste de um ar selvagem, belo e a ser desvendado. Mais bela que poemas, a ciência é a poesia da realidade, escrita no que somos e vemos, traduzida em matemática, um jogo de xadrez com o divino, em que temos como única missão entender as regras e jogar.

3 respostas