Introdução à Programação em C++
Aula 4 - Autômatos Celulares

Lucas S. Vieira


Universidade Federal dos Vales do Jequitinhonha e Mucuri
Novembro de 2019

O que são autômatos celulares unidimensionais?

Constituído de uma linha de células.

Cada célula é colorida com as cores preto ou branco.

Em cada passo de tempo, uma regra determina a cor de cada uma das células.

A regra opera de acordo com uma vizinhança, composta pela célula que mudará e pelos seus vizinhos esquerdo e direito.

Notação

Figura 1: Regra 90 (WOLFRAM, 2002).

A Regra 90 é capaz de gerar um fractal chamado Triângulo de Sierpiński.

Uma linha é resultado da aplicação das regras do autômato celular na linha anterior.

A primeira linha é o estado inicial do AC. As outras linhas representam gerações.

Modelando AC's

Um AC pode ser compreendido como um vetor numérico onde 0 indica uma célula morta, e 1 indica uma célula viva.

%3 values 0 0 0 1 0 0 0

Podemos aplicar a Regra 90 em cada célula para determinar a próxima geração:

%3 Geração 0: Geração 0: Geração 1: Geração 1: Geração 0:->Geração 1: values1 0 0 0 1 0 0 0 values2 0 0 1 0 1 0 0 values1:f0->values2:g0 values1:f1->values2:g1 values1:f2->values2:g2 values1:f3->values2:g3 values1:f4->values2:g4 values1:f5->values2:g5 values1:f6->values2:g6

O estados da célula atual das células à esquerda e à direita determinam o próximo estado da célula atual.

%3 Geração 0: Geração 0: Geração 1: Geração 1: Geração 0:->Geração 1: values1 ... 0 1 0 ... values2 ... ... 0 ... ... values1:f3->values2:g3

Para a primeira célula, seu vizinho à esquerda será o último elemento do vetor.

Para a última célula, seu vizinho à direita será o primeiro elemento do vetor.

%3 Geração 0: Geração 0: Geração 1: Geração 1: Geração 0:->Geração 1: values1 0 0 0 1 0 0 0 values2 0 0 1 0 1 0 0 values1:f0->values2:g0 values1:f1->values2:g1 values1:f2->values2:g2 values1:f3->values2:g3 values1:f4->values2:g4 values1:f5->values2:g5 values1:f6->values2:g6

Programando um AC unidimensional

Gerando apenas um estado

Seguimos o algoritmo:

  • Criar vetor gen0 (armazena o estado inicial das células).
  • Criar vetor gen1 (armazena a próxima geração do AC).
  • Percorra os elementos de gen0:
    • Tome os estados da célula atual e dos vizinhos.
  • Escreva o estado do novo elemento em gen1 no mesmo índice.
  • Imprima os vetores gen0 e gen1.
Geracao 0: 0 0 0 1 0 0 0 
Geracao 1: 0 0 1 0 1 0 0

Criando próximas gerações

  1. Crie um laço englobando toda a lógica do cálculo de geração;
  2. Imprima gen0 no início do laço;
  3. Copie gen1 para gen0 ao final do laço.
Geracao 0: 0 0 0 1 0 0 0 
Geracao 1: 0 0 1 0 1 0 0 
Geracao 2: 0 1 0 0 0 1 0 
Geracao 3: 1 0 1 0 1 0 1 
Geracao 4: 1 0 0 0 0 0 1

Embelezando a saída do programa

Imprima . no lugar do 0 e @ no lugar do 1.

Remova espaços entre elementos.

Regra 90 para 31 individuos em 16 geracoes:

...............@...............
..............@.@..............
.............@...@.............
............@.@.@.@............
...........@.......@...........
..........@.@.....@.@..........
.........@...@...@...@.........
........@.@.@.@.@.@.@.@........
.......@...............@.......
......@.@.............@.@......
.....@...@...........@...@.....
....@.@.@.@.........@.@.@.@....
...@.......@.......@.......@...
..@.@.....@.@.....@.@.....@.@..
.@...@...@...@...@...@...@...@.
@.@.@.@.@.@.@.@.@.@.@.@.@.@.@.@

Projeto de Programação I

Regra 110 é um AC que apresenta estruturas localizadas sob uma distribuição previsível.

A Regra 110 também é conhecida por ser Turing-completa.

Construa um programa que imprime na tela as primeiras gerações da Regra 110. Utilize o estado inicial e as a quantidades de gerações e células que achar mais conveniente.