INTELIGÊNCIA ARTIFICIAL: Autômatos Celulares

ReferênciasAutômatos Celulares: Revisão Bibliográfica e Exemplos de ImplementaçõesLucas Gremonini e Eduardo VicentiniRevista Eletrônica Lato Sensu – Universidade Estadual do Centro-Oeste

Autômatos Celulares: Teoria e AplicaçõesFlávio Pádua e Professor Newton VieiraUniversidade Federal de Minas Gerais.

Autômatos Celulares• Surgiu nos anos 40 objetivando criar sistemas evolutivos

• Possui aplicação em diversas áreas:• Modelagem de fenômenos físicos, biológicos e sociológicos• Aplicativos que processam imagens digitais

DefiniçãoAutômatos Celulares são modelos matemáticos delimitados por uma malha contendo células que são identificadas por estados. Os estados evoluem através de regras de interação locais e com evolução temporal.

AC Inativo

Características Básicas• Paralelismo: atualização autônoma

• Localidade: atualização depende da posição

• Homogeneidade: regras iguais para todos

CaracterísticasA Geometria é a forma da grade de células, formada por dimensão e formato.

Dimensões:

1D

2D 3D

CaracterísticasA Geometria é a forma da grade de células, formada por dimensão e formato.

Formatos da células:

Triangular HexagonalQuadrangular

Características• Vizinhança: determinada seleção de células próximas

Células na vertical, horizontal e diagonalmente adjacentes à célula

Características• Vizinhança: determinada seleção de células próximas

Células na vertical, horizontalmente a adjacentes a célula

Características• Vizinhança: determinada seleção de células próximas

Vizinhança aleatória e arbitrária

Características• Regras: regras para alteração dos estados das células• Determinísticas• Não determinísticas

• Estados: estados em que célula poderá ficar

Autômatos CelularesComo funcionam na prática?

• Formiga de Langton (vídeo)

• CA-horus Line (animação)

• Sistemas complexos (3D):• Simulação biológica de micróbios (vídeo)•Autômato célula 3D (vídeo)

Computação UniversalOs Autômatos Celulares apresentam características e propriedades da computação universal. Prova disso é que os Autômatos Celulares são capazes de simular passo a passo a Maquina de Turing.

Máquina de TuringCriada em 1936 a Máquina de Turing consiste em:• Uma fita infinita• Um cabeçote de leitura e gravação• Um registrador de estados• Uma tabela com as regras

Máquina de Turing

ACs e a Máquina de TuringA partir do movimento da fita consegue-se derivar as regra do Autômato Celular:

AC 1D

Máquina de Turing