|
Departamento de Ciência da
Computação - IME - USP
|
|
"Q. Sandpile models? What's that?"
A. The concept of self-organized criticality was introduced to
explain the behaviour of the sandpile model.
In this model, particles are randomly dropped onto a square grid of boxes.
For example [***BLAH BLAH
BLAH BLAH long period of droning on has been snipped ***]
In this case there is a transient cascade of trees from small to
large clusters and a power-law distribution is found only at a
critical density of trees.
Oh. And Sex, too.
Q. Yawn. Hey, what? I'm sorry. Were you talking?
A. Yes.
Fonte do texto sobre Sandpile:
Turcotte, D. L., 1999, Self-organized criticality,
Rep. Prog. Phys. 62, 1377-1426.
Fonte discurso: Matt Dickerson's FAQ Page
O objetivo geral deste exercício-programa (EP) é aplicar conceitos e mecanismos de programação que estudamos durante o semestre, em uma implementação em C de um modelo de simulação descrito abaixo. São objetivos específicos exercitar a manipulação de matrizes (leitura, escrita e varredura de seus elementos) e o uso de funções (definições, chamadas, passagem de valores como parâmetros, e passagem de referências a variáveis, vetores e matrizes como parâmetros
Esta introdução está baseada em vários textos,
entre eles Abelian sandpile model,
Cellular automaton [na
Wikipedia e
Wolfram MathWorld],
Self-organization,
What is ... a Sandpile?.
O modelo de um monte de areia (abelian sandpile model) é um exemplo de sistema dinâmico discreto (dynamical system) em que uma regra fixa descreve o estado de cada ponto de um determinado espaço geométrico ao longo do tempo. Este modelo é um exemplo dos chamados autômatos celulares (cellular automaton [Wikipedia, Wolfram MathWorld]) que são estudados em computabilidade, matemática, física, sistemas complexos, sexo, etc. Antes de continuarmos, uma curiosidade: no episódio "Bettor or Worse" (sic) (2006) [IMDb,tv.com] da série de televisão NUMB3RS é mencionado um autômato celular unidimensional [Wolfram MathWorld].
|
|
Considareremos a seguinte noção de vizinhança entre as casas do tabuleiro: duas casas são vizinhas se possuem um lado em comum. Essa noção de vizinhança é conhecida como do tipo torre (pelos movimentos dessa peça no Xadrez), mas é formalmente denominada de vizinhança de von Neumann. Na figura acima à direita estão ilustradas uma casa verde no meio de um tabuleiro, e suas 4 casas vizinhas de acordo com essa definição. Note que casas no meio do tabuleiro possuem 4 vizinhos, mas casas nas bordas e nos cantos possuem respectivamente 3 e 2 vizinhos.
Um monte de areia evolui em tempo discreto, ou seja, como se houvesse um tique de relógio dizendo para o sistema todo se atualizar a cada tique (muitos sistemas digitais funcionam assim). O que acontece é: toda casa que tem pelo menos tantos grãos quanto o número de vizinhos (4, 3 ou 2 conforme a casa) é ativada pelo sistema e espalha um pouco seu monte, dando um grão para cada vizinho. Essas casas são chamadas de instáveis, e espalham seus grãos simultaneamente. Por analogia, dizemos que uma casa que tem menos grãos que o número de vizinhos é estável nesse instante; uma casa estável não espalha nada. Se todas as casas são estáveis, claramente a configuração não se altera mais; diremos então que a configuração como um todo é estável.
De um instante para outro várias coisas podem acontecer. Uma casa instável pode se tornar estável; também pode continuar instável, ou porque tinha muitos grãos ou porque os grãos que recebeu dos vizinhos compensaram sua perda. Uma casa estável pode continuar assim ou se tornar instável devido aos grãos recebidos das casas vizinhas. Uma possibilidade curiosa pode ocorrer quando todas as casas do tabuleiro são instáveis: nesse instante, cada casa manda um grão para cada vizinho, mas recebe também um grão de cada vizinho. Ou seja, ocorre muito movimento, mas no final não muda nada na configuração. O sistema parece estável, mas não é.
A partir de uma dada configuração inicial podem acontecer duas coisas: ou em algum momento é atingida uma configuração estável (e dizemos que o sistema é finito), ou o sistema prossegue sem parar, seguindo por configurações instáveis (e dizemos que o sistema é infinito). Por exemplo, se alguma configuração instável se repete, o sistema entra em loop e fica se repetindo indefinidamente; na verdade, como o número total de grãos é constante, um sistema infinito necessariamente tem que entrar em loop alguma hora.
Dada uma configuração inicial dos grãos no tabuleiro, não é fácil decidir se ela gera um sistema infinito ou atinge uma configuração estável. O único jeito conhecido que funciona em geral é simular o processo. Se chegar numa configuração estável (todas as casas do tabuleiro são estáveis), conseguimos verificar que isso aconteceu, mas se o sistema for infinito, como é que podemos concluir isso?
Se você pensou em memorizar todas as configurações que aparecerem, testando se houve repetição, pense de novo: é possível construir exemplos razoavelmente pequenos que passam por tantas configurações que não existe memória que chegue no Universo para guardar tudo! Felizmente é possível provar o seguinte
Fato: Se um sistema é infinito, então cada casa do tabuleiro é ativada em algum instante. Reciprocamente, se toda casa do tabuleiro for ativada em algum instante, então o sistema é infinito.
Agora, temos um método para decidir se um sistema é finito ou infinito: Basta simular o sistema, lembrando as casas que já foram ativadas. Daí, ou se chega a uma configuração estável (determinando a finitude do sistema) ou eventualmente se chega a um instante em que todas as casas já foram ativadas pelo menos uma vez (neste último caso, podemos parar, informando que o sistema é infinito). Note que o problema de memória mencionado acima (associado a armazenar todas as configurações visitadas) desaparece, ainda que essa simulação possa levar muito tempo para chegar a uma dessas duas conclusões.
Para exemplificar essas ideias, consulte os exemplos de simulações de um sistema finito e de um sistema infinito.
Usando o formato de imagens PGM (Portable Grayscale Map) é muito fácil transformar matrizes em visualizações gráficas. A partir de vários arquivos de imagens, por exemplo img000000.pgm, img000001.pgm, etc, contendo a situação do tabuleiro nos instantes 0, 1, etc, é possível usar um programa externo para gerar uma animação em formato GIF. As animações abaixo, por exemplo, foram obtidas simulando um monte de areia de 100x100 com 40000 grãos colocados inicialmente na casa central, gerando um sistema infinito (a constatação desse fato ocorre após 20309 instantes de simulação):
Neste exercício-programa, a sua tarefa será escrever um programa em C que simula a evolução de um sistema do tipo monte de areia. O texto a seguir está organizado da seguinte maneira:
Sugerimos que, para fazer este exercício-programa, vocês experimentem com o executável fornecido, que pode ser copiado daqui, aproveitando também os arquivos contendo configurações iniciais para testes. No YouTube existem vários vídeos contendo simulações 2D e 3D da evolução de um monte de areia. Veja, por exemplo este e este outro, e mais este e este, entre outros. Note que essas simulações usam cores para representar o número de grãos em cada casa, ao passo que nosso EP produzirá saídas textuais na tela (e opcionalmente na forma de gráficos em níveis de cinza).
Inicialmente o programa deve ler da entrada padrão (usando scanf) os dados que correspondem à representação de uma configuração inicial para um sistema do tipo monte de areia. Estes dados podem ser digitados no teclado ou redirecionados a partir de um arquivo de entrada chamando o EP com a sintaxe meuep < minhaentrada.txt (exatamente como fizemos no EP2).
O formato de um arquivo de entrada contendo a representação de uma configuração de um monte de areia é o seguinte.
nlin ncol
i1 j1 T[i_1][j_1]
i2 j2 T[i_2][j_2]
...
iK jK T[i_K][j_K]
-1
A primeira linha deste arquivo especifica a dimensão do tabuleiro (nlin é o número de linhas e ncol o número de colunas). Em seguida temos uma sequência de linhas no arquivo que especificam as posições do tabuleiro que contém grãos de areia. Cada uma dessas linhas do arquivo contém dois índices i e j representando uma linha e coluna do tabuleiro, e um valor T[i][j] representando o número de grãos na posição [i][j] da configuração inicial. As posições não especificadas nessa sequência contém 0 grãos. A lista de valores iniciais será terminada pelo valor -1.
Como exemplo, abaixo vemos o conteúdo do
arquivo de teste entrada-2x4I.txt
2 4
0 0 16
1 3 1
-1
que representa o tabuleiro
Simulador de monte de areia
Configuracao inicial
Instante 0:
0 1 2 3
+----+----+----+----+
0 | 16 | 0 | 0 | 0 |
+----+----+----+----+
1 | 0 | 0 | 0 | 1 |
+----+----+---------+
Este formato de representação de matrizes usado no arquivo de entrada é muito útil para representar matrizes esparsas (em que a maioria das entradas da matriz vale 0).
Um sistema do tipo "monte de areia" corresponde a um tabuleiro retangular contendo apenas números naturais, que parte de uma certa configuração inicial (associada ao instante 0), e é atualizado em passos discretos (associados aos instantes 1, 2, etc) seguindo uma única regra:
Regra do espalhamento. Uma casa em uma configuração de um monte de areia é dita instável se o seu número de grãos é maior ou igual ao seu número de vizinhos (que pode ser 4, 3 ou 2 conforme a casa). A cada instante t, toda casa instável é ativada e deve espalhar seus grãos entre as suas casas vizinhas, transferindo exatamente 1 grão para cada casa vizinha. Todas as casas instáveis espalham seus grãos simultaneamente, definindo a nova configuração do tabuleiro no instante t+1.Observação: é claro que no código em C não será possível atualizar toda a matriz simultaneamente, já que isso será feito através de uma varredura sequencial da matriz. Mas é importante que a implementação produza exatamente o mesmo efeito que uma transferência simultânea entre todas as casas instáveis e seus respectivos vizinhos. Isso significa que se uma casa estável no instante t se tornar instável no meio da varredura que atualiza a matriz, ela não poderá espalhar seus grãos nessa mesma varredura, já que ela só será instável no instante t+1, ou seja, após o processamento de todos os espalhamentos associados à varredura do instante t.
Um sistema deste tipo está definido para todos os instantes t naturais, porém nossa simulação terminará assim que for possível estabelecer se o sistema é finito ou infinito, como descrito a seguir.
Uma vez fornecido o nome do arquivo com a configuração inicial, o programa deverá proceder com a simulação.
A simulação deve prosseguir até a última tentativa de espalhamento após detectar o tipo de sistema. Mais precisamente:
Após a simulação, o programa deverá imprimir um pequeno relatório sobre a simulação contendo:
Veja aqui um exemplo de saída para o tabuleiro inicial acima, correspondente ao arquivo de entrada entrada-2x4I.txt. Você pode encontrar mais exemplos de simulação neste link.
-Wall -ansi -O2 -pedantic
As mensagens e a impressão da configuração do
tabuleiro devem ser exatamente iguais às do executável fornecido (que
gerou os exemplos deste enunciado). Note que ao imprimir o tabuleiro,
todas as colunas têm a mesma largura, que se ajusta exatamente à maior
largura exigida por algum elemento do tabuleiro. Dica:
printf("%*d", ndig, m);
imprime o int m num campo cujo tamanho é dado por ndig;
assim, se ndig vale 4,
aquele comando imprime o mesmo que printf("%4d", m).
Seu programa deve
representar um tabuleiro através de uma matriz.
Utilize a declaração abaixo no início do seu programa
/* dimensao maxima da matriz*/
#define MAX 128
e declare seu tabuleiro (na função main) usando a sintaxe
int tabuleiro[MAX][MAX];
A dimensão efetiva do tabuleiro será nlin × ncol com 1 ≤ nlin < MAX
e 1 ≤ ncol < MAX, conforme os valores de nlin e ncol no arquivo de entrada. Um detalhe, não se preocupe com a resposta do programa
na simulação de sistemas sobre tabuleiros de dimensão 1 × 1.
Você deverá escrever e usar todas as funções abaixo, além da função main. O protótipo delas, bem como o que cada uma dessas funções deve fazer está descrito abaixo. Você pode implementar quaisquer outras funções que julgar necessário.
Em geral, recomendamos que você escreva e teste (teste!) cada função separadamente. É muito difícil encontrar erros em nossos programas depois de escrevermos longos trechos de código sem testá-los.
Comece sua implementação com uma função main vazia, e vá acrescentando apenas as variáveis necessárias para testar cada uma das funções descritas abaixo.
Inicialmente, escreva e teste a função
void zere_tabuleiro(int tabuleiro[MAX][MAX], int nlin, int ncol);
Esta função coloca zero em todas as posicoes da matriz
tab de tamanho nlin x ncol.
Em seguida, escreva e teste a função
void leia_configuracao_inicial(int tabuleiro[MAX][MAX],
int *nlin, int *ncol);
Esta função deve ler os valores da entrada
(como descrito na especificação da entrada)
e inicializar o tabuleiro e as variáveis (externas)
nlin e ncol com os valores correspondentes.
Em seguida, escreva e teste a função
void imprima_tabuleiro(int tabuleiro[MAX][MAX],
int nlin, int ncol);
Essa função imprime o tabuleiro no formato utilizado nos exemplos acima.
Agora, escreva e teste
a função
int espalhe(int tabuleiro[MAX][MAX], int ativacao[MAX][MAX],
int nlin, int ncol, int instante, int *novosativados);
Essa função corresponde ao mecanismo central do EP, e
será a responsável pela realização dos espalhamentos em cada instante.
A matriz ativação (declarada na função main e inicializada com -1's) deve registrar o instante em que cada casa é ativada (fica instável) pela primeira vez. O parâmetro de saída novosativados deve indicar quantas casas ficaram instáveis pela primeira vez nesse instante, e o valor de retorno da função é a quantidade total de casas instáveis nesse instante.
Recomendamos ainda que você escreva uma função
void copie_matriz(int origem[MAX][MAX], int destino[MAX][MAX],
int nlin, int ncol);
Você encontrará utilidade para essa função enquanto desenvolve o EP.
Durante a fase de testes, use tabuleiros pequenos e confira o estado do tabuleiro a cada instante
a fim de verificar se o seu programa está correto.
Só quando você achar que seu programa está correto, passe para testes com
tabuleiros maiores.
Compare sempre os resultados do seu EP e os do executável.
Exemplos de arquivos para teste podem ser encontrados aqui.
Nas simulações maiores, talvez você ache útil salvar a saída do
programa em um arquivo texto para facilitar a inspeção. Você pode fazer isso redirecionando
a saída padrão do seu programa (ou do executável fornecido) com a chamada
meuep < minhaentrada.txt > minhasaida.txt
int escreve_imagem(int instante, int tabuleiro[MAX][MAX],
int nlin, int ncol, int media);
Essa função deve criar um arquivo com um nome como img000000.pgm contendo uma imagem PGM do tabuleiro no instante correspondente. O nome do arquivo contém um número que deve corresponder ao valor do parâmetro instante e pode ser construído com a chamada sprintf(nome,"img%06d.pgm",instante); (essa função é parecida com a printf, mas escreve em nome, que é um vetor de elementos do tipo char). O formato PGM nada mais é que um arquivo texto com o conteúdo
P2 ncol nlin 255seguido de nlin x ncol números inteiros entre 0 e 255, representando diferentes níveis de cinza (0=preto, 255=branco) associados aos pixels na tela. Note que o tamanho da imagem é indicado no arquivo pela largura e altura da imagem em pixels, daí a aparente assimetria em relação às dimensões da matriz. O tabuleiro deve ser varrido da forma usual, ou seja, por linhas, para a geração dos pixels na imagem.
Para readequar as quantidades de grãos no tabuleiro à escala de níveis de cinza disponíveis e permitir visualizações interessantes, faremos uma simples regra de 3, mapeando casas com "0 grãos" na cor 0, e sendo media o valor médio de grãos no tabuleiro, mapearemos o valor 2*media em 255 (note que media é o último parâmetro da função escreve_imagem). Todos os valores intermediários serão distribuídos linearmente e arredondados, e todos os valores maiores que 255 serão mantidos em 255: para isso basta re-escrever em C a expressão y = min{255,(int)(255*x/(2.0*media)+0.5)}, onde x é a quantidade de grãos que desejamos representar. Se preferir imagens invertidas (com fundo branco), basta calcular o y da fórmula acima mas escrever o valor 255-y no arquivo PGM.
Para lembrar como criar e escrever em arquivos, você deve reler a parte correspondente do enunciado do EP2. Você precisará dos comandos fopen (com o formato "w" para escrita de texto simples), fprintf e fclose.
Para transformar seus arquivos de saída PGM em uma animação GIF, instale a suíte de aplicativos ImageMagick (disponível para Linux, MacOS e Windows), e use o comando convert com a seguinte sintaxe:
/* no linux: */ convert img*.pgm animacao.gif
/* no windows: */ magick convert img*.pgm animacao.gif
Se tiver dificuldades no uso do comando convert, leia atentamente as notas de instalação para o seu sistema operacional.
Todo EP deve seguir as observações contidas na página da disciplina, onde estão descritas as diretrizes para forma de entrega do exercício, aspectos importantes na avaliação, etc.
Bom trabalho e divirtam-se!