Concurso/Encontro Nacional de Programação Lógica
CeNPL'2003
Universidade de Évora
9--11 de Maio de 2003
Autómatos Celulares
Introdução
Um Autómato Celular (AC) é um sistema dinâmico
determinístico que consiste num array A
de células idênticas que repetidamente mudam
o seu estado ou cor de acordo com uma determinada
regra de actualização ra. Esta regra é aplicada
simultaneamente a todas as células de A em unidades
de tempo discretas. Quando ra é aplicada a uma célula
particular x Î A, a nova cor para x é determinada
pelo valor corrente das células numa vizinhança Vx
de x. Embora existam muitas escolhas interessantes
para A, vamos restringir a nossa atenção a arrays
uni-dimensionais de inteiros. A vizinhança de raio r
(r é um inteiro positivo) de uma célula x é então o
intervalo Vx = {y Î Z : |x-y| £ r}.
De um modo geral, as células de um AC tomam uma cor
de um conjunto de k cores diferentes (k ³ 2).
No nosso problema tomamos r = 1 e k = 2.
As duas cores possíveis são representadas por 0 e 1.
Para os ACs uni-dimensionais com r = 1 e k = 2,
a regra de actualização ra de uma célula x depende
das cores correntes das três células na vizinhança
de x, pelo que podemos representar a nova cor de x
por ra(p,q,r), onde p, q, r denotam as cores
correntes respectivamente das células x-1, x e x+1.
Por exemplo, a regra ra(p,q,r) = r desloca a sequência
de cores (a sequência de zeros e uns) de uma unidade
para a esquerda em cada actualização.
Tarefa
A sua tarefa consiste em escrever um programa Prolog
que dada a configuração inicial das células;
a regra de actualização; e o número N de actualizações
a realizar; mostra na primeira linha do ecrã a configuração inicial
e nas N linhas seguintes as N configurações que lhe sucedem.
Os Dados
O array uni-dimensional A é representado
por uma lista de zeros e uns. A regra ra(p,q,r)
é representada da maneira óbvia. Por exemplo,
a regra
p + (1-2p) (q+r-qr)
é codificada como
p + (1-2*p)*(q+r-q*r)
À esquerda da primeira célula (à esquerda do primeiro elemento
na lista) e à direita da última célula (à direita do último elemento
na lista) supomos um zero para efeitos
de aplicação da regra (supomos, respectivamente, que
p = 0 e r = 0).
Os Resultados
O programa deve ser invocado através do predicado:
ca(+ConfiguracaoInicial,+RegraActualizacao,+NumActualizacoes)
Seguem-se dois exemplos ilustrativos:
?- ca([0,0,0,0,1],r,6).
0 0 0 0 1
0 0 0 1 0
0 0 1 0 0
0 1 0 0 0
1 0 0 0 0
0 0 0 0 0
0 0 0 0 0
?- ca([0,0,0,1,0,0,0],p+(1-2*p)*(q+r-q*r),13).
0 0 0 1 0 0 0
0 0 1 1 1 0 0
0 1 1 0 0 1 0
1 1 0 1 1 1 1
1 0 0 1 0 0 0
1 1 1 1 1 0 0
1 0 0 0 0 1 0
1 1 0 0 1 1 1
1 0 1 1 1 0 0
1 0 1 0 0 1 0
1 0 1 1 1 1 1
1 0 1 0 0 0 0
1 0 1 1 0 0 0
1 0 1 0 1 0 0