Um autômato celular é um modelo discreto estudado em teoria da computabilidade, matemática e biologia teórica. É uma técnica de simulação razoavelmente simples. Consiste em uma grade infinita de células, cada uma podendo estar em um número finito de estados, que variam de acordo com regras determinísticas. Os autômatos celulares foram idealizados nos anos 40 por John von Neumman, um dos mais importantes matemáticos do século XX.
Segundo Oliveira (1999) a grade é composta por N máquinas idênticas, cada uma com um padrão de conexão com outras células. Cada célula i, a um dado tempo t, possui um estado. O estado da célula i, a um dado tempo t, junto com os estados das células às quais a célula i está conectada, é chamado de vizinhança da célula i. A regra de evolução fornece o próximo estado da célula i. A cada passo de tempo todas as células atualizam este estado de acordo com a regra imposta. Ou seja, o autômato celular segue regras determinísticas.
O exemplo mais conhecido de autômato celular é o Jogo da Vida (Life), inventado por John Conway. Este é um autômato celular bidimensional com dois estados (vivo ou morto) e vizinhança de raio 1, sendo que cada célula possui 8 vizinhos. As regras de evolução do Jogo da Vida são (Castro, 2011):
1- Uma célula que está no estado vivo (preto) permanecerá neste estado se 2 ou 3 vizinhas estiverem no estado vivo; caso contrário, ela irá para o estado morto (branco);
2- Uma célula que está no estado morto irá para o estado vivo se exatamente 3 vizinhas estiverem no estado vivo; caso contrário, continuará no estado morto.
Podem ser observadas algumas características interessantes dos autômatos celulares. A primeira é que o tempo é uma variável discreta. Como no exemplo demonstrado, temos os estados da grade de autômato celular no Jogo da Vida em quatro instantes (t=0, t=1, ...,t=4) mas não podemos extrapolar para, por exemplo, t=3,14. A segunda é que, embora regidos por regras simples, estes sistemas são complexos. Por isso inicialmente os autômatos celulares eram populares principalmente entre os entusiastas da computação, pois tais simulações são mais viáveis através do uso de computadores.
Os autômatos celulares possuem diversas aplicações. São citadas por Oliveira e Negrão (FATEC-SP/APS - Inteligência Artificial ): formação de fractais, estudos de processos evolutivos de determinado grupo, implementações na área de criptografia, incêndios florestais, etc. Castro (2011) utiliza os autômatos celulares para uma simulação capaz de descrever a dinâmica de uma floresta.
Referências
CASTRO, R. V. O. Modelagem do crescimento em nível de árvores individuais utilizando redes neurais e autômatos celulares. 2011. 80 p. Dissertação (Mestrado) - Universidade Federal de Viçosa, Viçosa - MG.
OLIVEIRA, K.; NEGRÃO, P. F. K. Autômatos Celulares. Disponível em: <http://www.ime.usp.br/~slago/sia-ac.pdf>. Acesso em: 05 de abril de 2015.
OLIVEIRA, G. M. B. Dinâmica e evolução de autômatos celulares unidimensionais. 1999. 149 p. Tese (Doutorado em Ciência) - Instituto Tecnológico de Aeronáutica, São José dos Campos.
XAVIER, A. Explorando Sistemas Complexos no Ensino Fundamental. 2003. 162 p. Dissertação (Mestrado em Educação) - Faculdade de Educação, UFMG, Belo Horizonte.
Segundo Oliveira (1999) a grade é composta por N máquinas idênticas, cada uma com um padrão de conexão com outras células. Cada célula i, a um dado tempo t, possui um estado. O estado da célula i, a um dado tempo t, junto com os estados das células às quais a célula i está conectada, é chamado de vizinhança da célula i. A regra de evolução fornece o próximo estado da célula i. A cada passo de tempo todas as células atualizam este estado de acordo com a regra imposta. Ou seja, o autômato celular segue regras determinísticas.
O exemplo mais conhecido de autômato celular é o Jogo da Vida (Life), inventado por John Conway. Este é um autômato celular bidimensional com dois estados (vivo ou morto) e vizinhança de raio 1, sendo que cada célula possui 8 vizinhos. As regras de evolução do Jogo da Vida são (Castro, 2011):
1- Uma célula que está no estado vivo (preto) permanecerá neste estado se 2 ou 3 vizinhas estiverem no estado vivo; caso contrário, ela irá para o estado morto (branco);
2- Uma célula que está no estado morto irá para o estado vivo se exatamente 3 vizinhas estiverem no estado vivo; caso contrário, continuará no estado morto.
 |
| Figura 1: Exemplo de grade de autômato celular de 4 evoluções no Life. Fonte: Xavier (2003). |
Podem ser observadas algumas características interessantes dos autômatos celulares. A primeira é que o tempo é uma variável discreta. Como no exemplo demonstrado, temos os estados da grade de autômato celular no Jogo da Vida em quatro instantes (t=0, t=1, ...,t=4) mas não podemos extrapolar para, por exemplo, t=3,14. A segunda é que, embora regidos por regras simples, estes sistemas são complexos. Por isso inicialmente os autômatos celulares eram populares principalmente entre os entusiastas da computação, pois tais simulações são mais viáveis através do uso de computadores.
Os autômatos celulares possuem diversas aplicações. São citadas por Oliveira e Negrão (FATEC-SP/APS - Inteligência Artificial ): formação de fractais, estudos de processos evolutivos de determinado grupo, implementações na área de criptografia, incêndios florestais, etc. Castro (2011) utiliza os autômatos celulares para uma simulação capaz de descrever a dinâmica de uma floresta.
Referências
CASTRO, R. V. O. Modelagem do crescimento em nível de árvores individuais utilizando redes neurais e autômatos celulares. 2011. 80 p. Dissertação (Mestrado) - Universidade Federal de Viçosa, Viçosa - MG.
OLIVEIRA, K.; NEGRÃO, P. F. K. Autômatos Celulares. Disponível em: <http://www.ime.usp.br/~slago/sia-ac.pdf>. Acesso em: 05 de abril de 2015.
OLIVEIRA, G. M. B. Dinâmica e evolução de autômatos celulares unidimensionais. 1999. 149 p. Tese (Doutorado em Ciência) - Instituto Tecnológico de Aeronáutica, São José dos Campos.
XAVIER, A. Explorando Sistemas Complexos no Ensino Fundamental. 2003. 162 p. Dissertação (Mestrado em Educação) - Faculdade de Educação, UFMG, Belo Horizonte.
