( PDF ) Automatizando a obtenção da complexidadebaseada em linguagem regular de autômatoscelulares elementares

UNIVERSIDADE PRESBITERIANA MACKENZIE

PROGRAMA DE PÓS-GRADUAÇÃO

ENGENHARIA ELÉTRICA

Automatizando a obtenção da complexidade

baseada em linguagem regular de autômatos

celulares elementares

Fábio Tokio Miki

Dissertação de Mestrado

apresentada ao Programa de Pós-

Graduação em Engenharia

Elétrica, como parte das

Exigências para Obtenção do Grau

de Mestre em Engenharia Elétrica,

na Área de Concentração em

Engenharia da Computação.

Orientador: Prof. Dr. Pedro Paulo Balbi de Oliveira

São Paulo – SP

2006

ads:

Livros Grátis

http://www.livrosgratis.com.br

Milhares de livros grátis para download.

Dedicatória

À minha amiga e companheir a

Fabíola

, pelo carinho, amor, incentivo e

compreensão aos finais de semana ausente.

À minha

mãe

Hih

umi

,

pelo exemplo

de força, perseverança, dedicação e amor

com seus filhos.

À minha irmã Cinthia,

pela amizade,

companheirismo e pela Luz que irradia.

Ao meu

pai Eijiro

,

pelo caráter,

sabedoria, carinho, amizade e apoio em

todos os momentos de minha vida.

Aos

meus avós

, pelo exemplo de

conduta e união, viv

idas e repassadas para

nossa família.

Agradeci mentos

Ao nosso Deus, pela sabedoria e oportunidade oferecida.

A todos meus familiares, sempre presentes em minha vida.

Aos meus colegas empreendedores da empresa Setis Automação e Sistemas

Ltda, que em momentos necessários apoiaram o desenvolvimento deste trabalho.

A Universidade Presbite riana Mackenzie, pelo idealismo e dedicação ao ensino

na nossa sociedade.

Ao

M

ACKPESQUISA

- Fundo Mackenzie de Pesquisa, p elo suporte, reserva técnica

e bolsa parcial concedida, que colaboraram com desenvolvimento do presente trabalho

À Wolfram Research, pela bolsa integral de hospedagem fornecida, durant e

minha participação no NKS-Summer School 2005.

Ao Victor Trafaniuc, pela paciência e suporte técnico oferecido que

contribuíram com o desenvolvimento desta pesquisa.

Em especial ao professor Dr. Pedro Paulo, meu orientador e amigo, pela

dedicação, incentivo e por estar sempre presente direcionando esta pesquisa.

Esta pesquisa foi possível graças aos seguintes financiamentos concedidos a meu

orientador: o projeto, já concluído, Advances in computing with cellular automata,

concedido p elo M

ACKPESQUISA , Edital 2004; o Mathematica Academic Grant Nº 1149,

concedido pela Wolfram Research; e o projeto Computing with cellular automata and

their temporal or spatial compositions, concedido pela FAPESP (Proc. 2005/04696-3).

Sumário

RESUMO....................................................................................................................................... 1

CAPÍTULO 1 ................................................................................................................................. 2

INTRODU ÇÃO .............................................................................................................................. 2

CAPÍTULO 2 ................................................................................................................................. 4

AUTÔMATOS CELULARES ........................................................................................................ 4

2.1 Introdução........ .................. .................. .................. .................. .................. .................. .................. .4

2.2 Conceito básico ........................ .................. .................. .................. .................. ......... ......................6

2.3 Autômatos celulare s unidimensionais. ......... ........................... ......... ........................... ......... .........6

2.3.1 Autômato celular elementar ............... ......... ........................... ......... .................. .................. ......9

2.3.2 Numeração das regras de autômato celular elementar ................ .................. ......... ................9

2.4 O espaço e lementar de regras............ .................. .................. .................. .................. ..................10

2.5 Comportamento dinâmico e classificação dos autômatos celulares .................. .................. .....14

2.6 Sensibilidade às condições iniciais..... ......... ........................... ......... ........................... ......... .........18

CAPÍTULO 3 ............................................................................................................................... 21

CARACTERIZAÇÃO DE AUTÔMATO CELULAR ATRAVÉS DE AUTÔMATOS FINITOS .... 21

3.1 Introdução........ .................. .................. .................. .................. .................. .................. .................21

3.2 Alfabetos, palavras, linguagens formais e gramáticas............................................. ..................22

3.3 Linguagens regulares, autômatos finitos e representação gráfica de máquinas .....................23

3.4 Semi-autômato............................................. ......... .................. .................. .................. ..................26

3.5 Configuraç ão de autômatos celulares e relação com autômatos finitos......... .................. ........26

3.6 Estado inicial do reticulado e sua representação ................................................. .................. ....27

3.7 Evolução de autômato finito a cada passo de te mpo ............................................. .................. ..2 8

3.8 Complexidade em linguagem regular e caracterizaçã o de autômatos celulares ................ .....30

3.9 Tabela de complexidade das linguagens regula res ....................................... ......... ....................31

3.10 Funções NetCAStep, TrimNet e M inNet ....... .................. ......... ........................... ......... ..............33

3.11 Métodos de análise desenvolvidos e m [Trafaniuc, 2004]..................................... .................. ....35

3.12 Detecção de estruturas comuns em passos de tempo consecutivos....................... .................. ..3 8

CAPÍTULO 4 ............................................................................................................................... 42

ANÁLISE DA COMPLEXIDADE EM LINGUAGEM REGULAR RELACIONADA A

AUTÔMATO CELULAR ............................................................................................................. 42

4.1 Análise automática do crescimento de grafos .......... .................. .................. .................. ............42

4.1.1 Módulo de geração e armazenamento de dados............. .................. .................. .................. ..4 2

4.1.2 Operação de diferença entre grafo s .............................. .................. .................. .................. ....43

4.1.3 Módulo de análise de resultados....................................... .................. .................. .................. .46

4.2 Em busca da caracterização do comportamento limite............. .................. .................. ............50

4.2.1 Grafo limite da regra elementar 18 4................. .................. .................. .................. ................51

4.2.2 Grafos e a relação com diagrama espaço temporal .............. ........................... ......... .............53

4.2.3 Componentes do comportament o limite ........ .................. .................. .................. .................. .55

CAPÍTULO 5 ............................................................................................................................... 58

CONCLUSÃO ............................................................................................................................. 58

5.1 Introdução........ .................. .................. .................. .................. .................. .................. .................58

5.2 Detalhamento dos Resultados.................................................. ......... ........................... ......... .......59

5.3 Comentário s finais............... ........................... ......... .................. .................. .................. ...............71

APÊNDICE .................................................................................................................................. 73

A.1. TABELA DE COMPLEXIDADE DAS LINGUAGENS REGULARES [WO LFRAM, 1994].73

A.2. TABELA DE COMPLEXIDADE DAS LINGUAGENS REGULARES [TRAFANIUC, 2004].

..................................................................................................................................................... 76

A.3. RESULTADO DA ANÁLISE AUTOMÁTICA DE CRE SCIMENTO .................................... 79

REFERÊNCIAS BIBLIOGRÁFICAS......................................................................................... 128

Índice de Figuras

FIGURA 2.1. REPRESENTAÇÃO DE UMA CADEI A FINIT A UTILIZANDO LIMITES

PERIÓDICOS. ...................... ......... .................. .................. .................. .................. .................. ............8

FIGURA 2.2. APLICAÇÃO DA REGRA DE TRANSIÇÃO EM UM AC. . .................. .................. ..........8

FIGURA 2.3. PROCESSO DE NUMERAÇÃO D E REGR AS – REGRA 110.................... .....................10

FIGURA 2.3. DIAGRAMA ESPAÇO-TEM PORAL D AS REGRAS 11 0, 124, 137 E 193 [WOLFRAM,

2002].................... .................. .................. .................. .................. .................. .................. .................. .12

FIGURA 2.4. EVOLUÇÃO DA REGRA 254 [WOLFR AM, 2002]. ............................. .................. .........14

FIGURA 2.5. EVOLUÇÃO TEMPORAL DA REGRA 250 [WOLFRAM, 2002]........... ........................15

FIGURA 2.6. REGRA 90 APLICADA EM 50 PASSOS DE TEMPO [WOLFRAM, 20 02]....................15

FIGURA 2.7. CLASSES DINÂMICAS DOS AUTÔMATOS CELULARES [WOLFRAM, 1984]. (A)

AUTÔMATO CELULAR CLASSE 1, (B) AUTÔMATO CELULAR CLASSE 2, (C) AUTÔMATO

CELULAR CLASSE 3 E (D) AUTÔMATO CELULAR CL A SSE 4. ..............................................17

FIGURA 2.8. FIGURA QUE DEMONSTRA OS EFEITOS CAUSADOS COM PEQUENA

ALTERAÇÃO NA CONDIÇ ÃO INICIAL PARA AS QUATRO CLASSES DE AUTÔMAT O S

CELULARES [WOLFRAM, 2002]. ................ .................. .................. .................. ......... ...................19

FIGURA 2.9. EFEITOS CAUSADOS COM PEQUENA MODIFICA ÇÃO NA CONDIÇÃO INICIAL

NA REGRA 110 – CLASSE 4 DE AUTÔMATO CELULAR [WOLFRAM, 2002]........................20

FIGURA 3.1. REPRESENTAÇÃO GRÁFICA DE AUTÔMATOS FINITOS DETE RMINÍSTICOS

COM ALFABETO BINÁRIO Σ ={0,1} QUE (A) ACEITA TODAS AS PALAVRAS FORMADAS

POR Σ; (B) ACEITA A LINGUAGEM (0+11)*. .............................................. ......... .......................25

FIGURA 3.2. RELAÇÃO ENTRE A EVOLUÇÃO TEMPORAL DE UM AUTÔMATO CELULAR

ELEMENTAR E UM AUTÔMATO FINITO. ................................. ......... .................. .................. ....27

FIGURA 3.3. AUTÔMATO FINITO REPRESENTANDO GRAFICAMENTE A CONDIÇÃO INICIAL

DE UM AUTÔMATO CELULAR BINÁRIO : (A) SEGUINDO A MESMA NOTAÇÃO

DESCRITA NA FIGURA 3. 1; (B) FORMA DE VISU A LIZAÇÃO IMPLEMENTADA NO

SOFTWARE MA THEMATICA E UTILIZAD A EM [TRAFANIUC, 2004]. ....................... ..............28

FIGURA 3.4. DIAGRAMA ESPAÇO TEMPORAL E GRAFOS GERADOS PARA 02 PASSOS

TEMPORAIS DAS REGRAS 255 E 4 DO ESPAÇO ELEMENT AR [TRAFANIUC, 2004]. .........29

FIGURA 3.5. GRAFOS GERADOS A CADA PASSO DE TEMPO PARA A REGR A 126

[TRAFANIUC, 2004 ]...................................... ......... .................. .................. .................. .................. ..3 0

FIGURA 3.6. LEITURA DA TABELA A.1. [WOLFRAM, 1994]. ................................. ......... ................32

FIGURA 3.7. EXECUÇÃO DA FUNÇÃO TRIMNET..................................... .................. .................. ....33

FIGURA 3.8. SEQÜÊNCIA DE UTILIZAÇÃO DE NETCASTEP, TRIMNET E MINNET..................34

FIGURA 3.9. VALIDAÇÃO DOS DADOS APRESENTADOS EM TABELA DE [TRAFANIUC,

2004].................... .................. .................. .................. .................. .................. .................. .................. .36

FIGURA 3.10. ILUSTRAÇÃO DO ALGORITMO UTILIZADO EM [TRAFANIUC, 2004].................36

FIGURA 3.11. GRAFOS DE TEMPOS CONSECUTIVOS (T E T+1) DA REGRA 128 . .......................38

FIGURA 3.12. GERAÇÃO DE SUBGRAFOS DE T+1 COM MESMA QUANTIDADE DE NÓS QUE

O GRAFO EM T. ................... ......... .................. .................. .................. .................. .................. .........39

FIGURA 3.13. SELEÇÃO DE SUBGRAFOS CANDIDATOS PARA IDENTIFICAÇÃO DA

ESTRUTURA COMUM EM PASSOS DE TEMPOS CONSECUTIVOS. ........................... ...........39

FIGURA 3.14. SELEÇÃO DE SUBGRAFO COM MENOR DIFERENÇA. ........... ......... .......................40

FIGURA 4.1. MÓDULO DE G ERAÇÃO E ARMAZENAMENTO . .............................................. .........43

FIGURA 4.2. ILUSTRAÇÃO DA IMPLEMEN TAÇÃO DA OPERAÇ ÃO DE DIFERENÇA. ..............44

FIGURA 4.3. OPERAÇÃO DE DIFERENÇ A APLICADA ENTRE GRAFOS DA REGRA 18 4 NOS

INSTANTES T=1 E T=2..................... .................. .................. .................. .................. .................. .....45

FIGURA 4.4. RESULTADOS DA REGRA ELEMENT AR 11 RETIRADA DO APÊNDICE A.3.........48

FIGURA 4.5. REGRA 184 EM EVOLUÇ ÃO TEMPORAL COM CONDIÇÃO INICIAL (#1S = #0S).51

FIGURA 4.6. REGRA 184 EM EVOLUÇ ÃO TEMPORAL COM CONDIÇÃO INICIAL (#1S > #0S).52

FIGURA 4.7. REGRA 184 EM EVOLUÇ ÃO TEMPORAL COM CONDIÇÃO INICIAL (#1S < #0S).

........ .................. .................. .................. .................. .................. ......... ........................... ......... .............52

FIGURA 4.8. GRAFO LIMITE DA REGRA 184. ....... ......... .................. .................. ......... .......................53

FIGURA 4.9. ANÁLISE DE ESTRUTURAS PRESENTE S NOS GRAFOS RELACIONADO S À

REGRA 184. ......................... .................. .................. .................. .................. .................. .................. .54

FIGURA 4.10. ANÁLISE DO DIAGRAMA ESPAÇO TEMPORAL DA REGRA 184.................... ......54

FIGURA 4.11. RESULT ADOS DA OPERAÇÃO DE DIFERENÇA DE GRAFOS................................56

FIGURA 4.12. ILUSTRAÇÃO DA OPERAÇÃO DE OBTENÇÃO DO G RAFO LIMITE PARA A

REGRA 184. ......................... .................. .................. .................. .................. .................. .................. .56

FIGURA 5.1. RESULTADOS DA REGRA ELEMENT AR 43 COM CRESCIMENTO LINEAR DESDE

O PRIMEIRO INSTANT E DE TEMPO........... ......... .................. .................. .................. ..................61

FIGURA 5.2. RESULTADOS DA REGRA ELEMENT AR 56 COM CRESCIMENTO LINEAR DESDE

O SEGUNDO INSTANTE DE TEMPO.............................................. .................. .................. ..........63

FIGURA 5.3. RESULTADOS DA REGRA ELEMENT AR 50 COM CICLO=2 E CRESCIMENTO

LINEAR . ............................. .................. .................. .................. .................. ......... ........................... ..6 5

FIGURA 5.4. ESTRUTURA ADICIONADA E EXCLUÍDA DA REGRA 50 COM CRESCIMENTO

LINEAR. .............................. ......... .................. .................. .................. .................. .................. ...........66

FIGURA 5.5. RESULTADOS DA REGRA ELEMENT AR 81 SEM ESTRUTU RA REPETITIVA MAS

COM CRESCIM ENTO LINEAR. .................. .................. .................. .................. .................. ...........68

FIGURA 5.6. RESULTADOS DA REGRA ELEMENT AR 11 CRESCIMENTO LINEAR PARA

TEMPO PAR E ÍMPAR............................................... .................. .................. .................. ................70

Índice de Tabelas

TABELA 2.1. REPRESENTAÇÃO DA REGRA DE TRANSIÇÃO DE ESTADOS DE UM

AUTÔMATO CELULAR BI NÁRIO. ...................................... ......... ........................... ......... ..............7

TABELA 2.2. TRANSFORMAÇÃO DO AC ELEMENTAR 110 EM SUA REGRA EQUIVALENTE

124................ ........................... ......... .................. .................. .................. .................. .................. ........11

TABELA 2.3. TRANSFORMAÇÃO DO AC ELEMENTAR 110 EM SUA REGRA EQUIVALENTE

137................ ........................... ......... .................. .................. .................. .................. .................. ........11

TABELA 2.4. TRANSFORMAÇÃO DO AC ELEMENTAR 124 EM SUA REGRA EQUIVALENTE

193................ ........................... ......... .................. .................. .................. .................. .................. ........11

TABELA 2.5. TRANSFORMAÇÃO DO AC ELEMENTAR 137 EM SUA REGRA EQUIVALENTE

193................ ........................... ......... .................. .................. .................. .................. .................. ........12

TABELA 2.6. CLASSES DE REGRAS EQUIVALENTES DO ESPAÇO ELEMENTAR [WOLFRAM,

1994].................... .................. .................. .................. .................. .................. .................. .................. .13

TABELA 3.1. EVOLUÇÃO DOS GRAFOS PARA REGRAS COM CRITÉRIOS DE PARADAS

DISTINTOS. ........................ ......... .................. .................. .................. .................. .................. ...........37

TABELA 3.2. RESULTADO DO MÉTODO DE BUSCA DE SUBGRAFOS COMUM DA REGRA 128.

........ .................. .................. .................. .................. .................. ......... ........................... ......... .............41

TABELA 5.1. EXPRESSÕES DE CRESCIMENTO DA TA BELA DE COMPLEXIDADE

[WOLFRAM, 1994] QUE PERMANECIAM VAZIA ............................................... ......... ..............71

TABELA A.1. COMPLEXIDADE DAS LINGUAGENS REGULARES [WOLFRAM, 1994]. ............ .75

TABELA A.2. TABELA QUE DEMONSTRA A COMPL EXIDADE DAS LINGUAGE NS

REGULARES, RETIRADA DO TRABALHO DE PESQUISA [TRAFANIUC, 2004]...................78

1

Resumo

Autômatos celulares são sistem as dinâmicos e computacionais totalmente discretos no

tempo, no espaço e em suas variáveis de estado. Sabe-se que, para um autômato celular

elementar, o conjunto de todas as configurações possíveis de se obter decorrida uma

quantidade finita de passos de tempo de sua evolução temporal c on stitui uma l inguagem

regular. Com isso, esse conjunto de cadeias pode ser r epresentado por um autômato finit o

determinístico mínimo, e a quantidade de estados e transições entre eles pode ser

considerada uma medida da complexidade (em linguagem regular) da regra el ementar em

questão; tal processo, apesar de eventualmente custoso compu tacionalmente, e stá bem

resolvido na literatura. No entanto, quando se deseja obter a representação do autô mato

finito limite, isto é, para uma quantidade infinita de passos de tempo, essa máquina pode

não existir par a algumas regras, e, mesmo em alguns casos em que se sabe que ela existe,

não há ainda um método que a gere automaticamente. O presente trabalho caminha na

direção de ajudar a solucionar este último problema, apesar de que ainda não foi possível

derivar o algoritmo de comportamento limite. No enta nto, avança-se aqui com relação ao

método atualmente existente, no sentido de, através de um novo algori tmo, derivar

automaticamente expressões de crescimento do autômato finito representativo de cada

passo de tempo, inclusive em casos ainda não reportados, o que lança luz sobre a questão

original, abrindo perspectivas para que a obtenção automática do autômato finito limite

possa ser obtida posteriormente.

Abstract

Cellular aut omata are dynamical and computational systems, t o tally discrete in time, space

and t heir state variables. It is known that, for elementary cellular automata, the set of a ll

possible configurations that can appear at any finite number of time steps in their temporal

evolution constitutes a regular la nguage. As a consequence, such a set of strings c an be

represented by a minimal deterministic finite automaton, and the quantity of states and

transitions among them may be considered a measure of the (regular lan guage) complexity

of the rule at issue; performing such a process may be computationally intensive, but it is

well solved in the literature. However, when the target is the limit finite automaton, t hat is,

the one after an infinite number of ti me steps, the machine may not exi st for some rules, and

the currently existing method fails to automatically generate it for some rules for which it is

known otherwise that a solution does exist. This work aims at helping the solution of the

latter problem, although the actual derivation of the algorithm t o automatically generate the

limit finite automaton has not yet been possible. However, it goes further the currently

existing method, by means of a new algorithm for automatically yielding the growth

expressions of the finite automaton representative of each time step, including some cases

not reported so far, therefore shedding light over the issue, a nd opening perspectives for a

subsequent automatic derivation of the limit finite automaton.

2

Capítulo 1

Introdução

Autômatos Celulares (ACs) são si stemas distribuídos espacialmente, consistindo

de um grande número de componentes simples e idênticos, com conectividade local.

Esses sistemas são discretos no t empo, no espaço, e nas variáveis de estado, cuja

interação local de seus componentes, pode resultar em comportamento global

extremamente complexo. Essa capacidade de processamento coordenado de

informações globais, a partir de forte restrição local, é conhecido como computação

emergente [Mitchell and Crutchfield, 1995], e está presente em inúmeros sistemas

naturais, razão pelo qual, os ACs v em sendo utilizados em modela gem de sistemas.

.

Os autômatos celulares durante a evolução temporal, apresentam um

comportamento de auto-organização, no qual pode ser atribuído a um processo

computacional. Essa evolução pode s er caracterizada, através da teoria das linguagens

formais [Wolfram, 1984]. O conjunto de configurações possíveis para um número finito

de passos da evolução temporal de um autômato celular, forma uma linguagem regular,

onde cada palavra ou ca deia de sí mbolos pertencente a esta linguagem, corresponde a

uma configuração d o autômato celular. De acordo com hierarquia de Chomsky, as

linguagens regulares fazem parte da classe mais simples de linguagens, Tipo-3, e são

aceitas ou reconhecidas por máquinas classificadas como autômatos finitos (verificar

definição formal na Seção 3.3). O conceito dessas máquinas podem ser baseados na

idéia de um sistema capaz de efetuar leitura seqüencial e de gerar ou processar cadeias

de símbolos. Ao término de um processamento de uma c adeia de símbolos, quando

essas máquinas atingem um estado final de aceitação, pode-se afirmar que ocorreu a

aceitação da cadeia, ou seja, a cadeia de sí mbolos pertence à linguagem regular

reconhecida pelo autômato finito. O tamanho do autômato finito correspondente a uma

determinada lingua gem regular, determina a comp lexidade da linguagem, e podem

indicar o grau de complexidade de configurações apresentadas por autômatos celulares

em evolução.

O estudo de autômatos celulares em evolução e a relação exi s tente com a

complexidade de autômatos finitos, foi iniciado em pesquisa anterior intitulada como

3

“Caracterização computacional do comportamento l imite de alguns autômatos celulares

elementares” [Trafaniuc, 2004]. Nesse trabalho, a t abela de complexidade de

linguagens regulares de [Wolfram, 1994] foi reconstruída. Essa tabela, exibe a

complexidade de autômatos finit os , relacionada ao número de nós e arestas necessários

para a representação gráfica da máquina. Em [Trafaniuc, 2004], novos resultados foram

apresentados utilizando métodos iterativos [Wolfram, 2002] e representações gráficas

de máquinas, que permitiram análise e observações visuais. O presente trabalho

apresenta-se como continuidade a essa pesquisa, com novas investigações da

complexidade de linguagens re gulares associadas a regras de autômatos celulares,

dentro do espaço elementar, através de processos automatizados desenvolvidos.

O Capítulo 2 apresenta uma descrição geral d e autômatos celulares, definição,

funcionamento, classificação dinâmica e exemplos que fornecem uma introdução

teórica a essa classe de si s tema, estudada nesta pesq uisa.

O Capítulo 3 apresenta a relação existente entre a complexidade de autômatos

finitos e a caracterização de autômatos celulares, e o processo desenvolvido em

[Trafaniuc, 2004] aborda ndo esse relacionamento.

O Capítulo 4 apresenta todos os processos desenvolvido nesta pesquisa,

módulos de geração e análise de dados, e a exibição e interpretação dos resultados

obtidos.

Por fim, o Capítulo 5 conclui esta pesquisa, analisando os processos

desenvolvidos, com base nos resultados com sucesso e falha, e deixa como sugestão, o

que pode ser feito num trabalho de continuidade.

4

Capítulo 2

Autômatos celulares

2.1 Introdução

Atualmente, as leis básicas da física relevantes aos fenômenos mais comuns, já

são conhecidas e modeladas. Porém, muitos sistemas naturais possuem estruturas e

comportamentos complexos, em consideração à análise qualitativa. Por exemplo, as leis

que regem o congelamento da água ou as leis de condução de calor, são conhecidas há

algum tempo, mas m o delar os inúmeros e complexos padrões gerados pela formação e

crescimento de flocos de neve, é uma tarefa que ainda não foi realizada, mesmo com

sofisticadas técnicas matemáticas. Desenvolver modelos matemáticos que descrevem o

comportamento de sistemas naturais complexos, e a utilização de métodos

convencionais de simulação, na maioria das vezes, apresentam falhas no resultado,

devido ao grande número de componentes a serem considerados. Nos últimos anos,

pesquisadores vem ob tendo resultados importantes, utilizando na modelagem de

fenômenos reais, estruturas computacionais bastante simples, mas com capacidade de

exibir uma dinâmica complexa. Essas estruturas computacionais são conhecidas como

autômatos celulares (ACs) e vem sendo utilizadas nos mais variados campos da ciência

como biologia, física, química, geolo gia, música, etc.

Em meados dos anos 50, com o propósito de desenvolver uma Máquina de

Turing que permitisse m anipular mecanismos capazes de auto-reprodução, John von

Neumann construiu o prim eiro modelo de AC, seguindo sugestão de Stannisl aw Ulam

[Burks, 197 0]. Na m esma época, Ulam investigava uma vari edade de jogos matemáticos

dispostos em uma grade bidimension al onde o estado de cada ponto na grade era

atualizado d e acordo com o seu próprio estado e os estados de seus vizinhos. Ulam

estudava diferentes vizi nhanças, com di versos números de estados pos síveis por célula e

regras de transição variadas. Ulam sugeriu a von Neumann o conceito de uma grade

artificial, como um tabuleiro de xadrez, na qual cada quadrado poderia ser visto como

uma ‘célula’, e cada célula agiria individualme nte, de acordo com um conjunto de

regras, que seria aplicado a todas as células da grade individualmente. A evolução das

células seria feita em passos discretos de tempo. Cada célula saberia seu próprio estado

5

e poderia olhar os estados de suas células mais próximas (vizinhança). A cada passo de

tempo, seria consultado o conjunto de regras de transição para decidir o estado de cada

célula da grade. Uma coleção de células nesta grade poderia ser vi sta como um

organismo artificial [Oliveira, 2003]. O mo delo de AC projetado por von Neumann é

caracterizado por uma grade bidimensional infinita, formado por células uniformes com

29 estados cada e conectadas aos seus quatro vizinhos ortogonais. Os resultados dos

experimentos e estudos de von Neumann só foram publicados após sua morte, por seu

colaborador Arthur Burks em 1966 [von Neumann e Burks, 1966 ].

Na década de 70, durante estudos de autômato celular e computabilidade

universal, John Conway criou o Game of Life [Berlekamp, Conway e Guy, 1992]. O

sistema consiste em um AC bidimensional com estados binários, que funciona com uma

simples regra de transição, onde células no estado 0 são interpretadas como ‘mortas’ e

as no estado 1 como ‘vivas’. O Life como é conhecido, popu larizou-se no s meios

acadêmicos, pelo fato de ser o primeiro AC relativamente simples, que mostrou

capacidade em produzir p adrões complexos e estruturas que se assemelhavam a

organismos artificiais [Oliveira 2003].

Stephen Wolfram iniciou diversas pesquisas durante a década de 80, sobre o

comportamento dinâmico dos ACs, que se tornaram as principais referências ([Wolfram

1983a], [Wolfram 1983b], [Wolfram 1984a], [Wolfram 1984b], [Wolfram 1988],

[Wolfram 1994]) para pesquisadores da área. Wolfram modificou o rumo das pesquisas

demonstrando que mesmo os modelos mais simples de ACs (unidimensionais, binários

e com vizinhança de 3 células), poderiam exibir padrões complexos e interessantes

[Oliveira 2003]. Nas inúmeras pesquisas efetuadas por Wolfram, pode-se destacar o

esquema de classificação de ACs, de acordo com seu comportamento dinâmico

[Wolfram, 1984a] e a demons tração que a regra elementar 110 de AC, apresenta

computabilidade universal [C ook , 2004]. Em 2002, com o lançamento do (polêmico e

aguardado) livro A New Kind of Science [Wolfram, 2002], o autor retrata quase 20 anos

de pesquisa, baseado em experimentos realizados com si stemas de natureza simples,

com destaque aos experimentos utilizando autôm atos celulares.

6

2.2 Conceito básico

Autômatos Celulares (ACs) são sistemas dinâmicos di s cretos, capazes de

realizar computações segundo um modelo de processamento local, descentralizado e

totalmente paralelo [Wolfram, 2002].

Esses sistemas são formados por um espaço celular, regras de transição e

conjunto de estados. O espaço celular é um reticulado n-dimensional, composto por

células idênticas, representadas por autômatos finitos, que possuem conectividade

padrão com out ras células, e condição de contorno. Para cada passo de tempo, de acordo

com uma regra de transição ou regra local, todas as células do reticulado são atualizadas

e podem assumir um estado, dentro de um conjunto de estados possíveis. A regra de

transição de estados, atual iza o valor do estado de cada célula, em função dos estados de

sua vizinhança. O conjunto de estados de todas as células em um determinado passo de

tempo é chamado de configuração ou estado global do autômato celular, e descreve o

estágio da evolução temporal do mesmo. No instante de tempo zero, o aut ômato celular

encontra-se em uma configuração inicial e, a cada passo de tempo subseqüente, ele

evolui de maneira determinística, de acordo com o efeito da regra local, a qual é

aplicada a cada uma de suas células, em paralelo.

2.3 Autômatos celulares unidimensionais

Autômatos Celulares unidimensionais são formados por uma lista compos ta por

i células. As células possuem conectividade com células vizinhas, dependendo do

tamanho do raio r. A cada passo de tempo t, de acordo com uma regra de transição de

estados

φ

, cada célula i poderá assumir um determinado estado

i

t

σ

, pertencente a um

alfabeto finito A que é composto por símbolos:

Ak

i

t

≡−∈ }1,,1,0{ 

σ

(onde k

representa o número de e s tados de um AC).

O estado

i

t

σ

da célula

i

, junto com os estados das células às quais a célula

i

está

conectada, s ão chamados vizinhança

i

t

η

da célula

i

e pode ser representado pela sentença

=

i

t

η

ri

t

ri

t

+−

σσ

,...,

.

7

A regra de transição ou regra lo cal de um autômato celular é denotada por

)(

i

t

ηφ

que

fornece o próximo estado

i

t 1+

σ

para cada célula i, como uma função de

η

t

i

. Dessa forma, a

cada passo de tempo, todas as células atualizam seus estados de maneira sincronizada, de

acordo com a expressão:

)(

1

i

t

i

t

ηφσ

=

+

ou

),...,(

1

ri

t

ri

t

i

t

+−

+

=

σσφσ

. A regra de transição de

estados é representada por uma tabela de transição, a qual relaciona para cada vizinhança

possível (entrada), o valor de atualização do estado da célula central da vizinhança (saída).

A Tabela 2.1 apresenta uma regra de transição de um AC unidimensional, com raio r = 1 e

número de estados k = 2 (AC binário), formada pelas oito viz inhanças possíveis e seus bits

de atualização.

ENTRADA

i

t

η

SAÍDA

)(

i

t

ηφ

Numeração

1−i

t

σ

i

t

σ

1+i

t

σ

i

t 1+

σ

0 1

1

1 0

1 1

1 0 1

2 1

0

1 1

3 1

0

0 0

4 0

1

1 1

5 0

1

0 1

6 0

0

1 1

7 0

0

0 0

Tabela 2.1. Representação d a regra de transição de estados de um autômato celular binário.

Quando se aplica regras de transição em cadeias finitas também é necessário

especificar a condição utilizada nas bordas da cadeia, que normalmente é periódica; ou

seja, para aplicar a regra de atualização do autômato celular a primeira e a última célula

da cadeia são ligadas. Pod e-se considerar a cadeia, então como um conjunto de células

que forma um anel, conforme a Figura 2.1:

8

Figura 2.1. Representação de uma cadeia finita utilizando limites periódicos.

Considerando-se uma célula no estado ‘1’ como preto e ‘0’ como branco, a

Figura 2.2 demonstra um autômato celular em evolução, aplicando a regra de transição

definida na tabela 2.1 e condição de contorno periódica. Os números que aparecem na

primeira linha, referem-se a uma condição aplicada, das oito apresentadas na tabela 2.1,

para definição do próximo estado.

Figura 2.2. Aplicação da regra de transição em um AC.

O estado s

t

, ou configuração, de um autômato celular em um determinado passo

de tempo t representa a configuração de todo a lista neste dado momento:

N

t

As ∈

,

onde

N

A

representa o conjunto de todos os valores possíveis de uma célula em um lista

de N células. O espaço de estados estendido

*

A

representa a união de todos os estados

para qualquer N:

N

AA



0

*

≥

=

A re gra de atualização do autômat o celular

φ

é aplicada em paralelo para todas

as células da cadeia:

)(

1−

=

tt

ss

φ

.

5

6

2

3

7

Configuração I nicial

Configuração para t=1

Configuração para t=2

Número da condição de atualização retirada da tabela 2.1 para definição do próximo estado

0 1 1 0 1

0 1 0 1 1

Vizinhança da célula i=5

9

2.3.1 Autômato celul ar elementar

A classe mais simples de autômatos celulares é chamada de elementar, sendo

formada por autômatos celulares unidimensionais binários onde o estado da célula a

cada passo é determin ado pelo estado atual da própria célula e dos estados das células

vizinhas imediatas, ou seja, a primeira célula vizinha à esquerda e a primeira célula

vizinha à direita. O tamanho da vizinhança utilizada para uma det erminada classe de

autômatos celulares p ode ser verificada pelo raio da vizinhança r, que para o s autômatos

celulares elementares é 1 (k=2, r=1). Os autômatos celulares elementares são

representados, então, com a menor vizinhança possível e valores binários para as

células, 0 e 1 (que graficamente serão representados por células brancas e células pretas,

respectivamente), o qu e dá um total de 8 possíveis vizinhanças, uma vez que para c ada

transição a célula pode assumir k valores que depende de 2r+1 células para ser

determinado, portanto:

82

312

==

+r

k

. A partir do número de possíveis vizinhas, pode-

se chegar ao número de regras através da seguint e expressão:

12 +r

k

, que para os

autômatos celulares elementares resulta em:

.25622

82

312

===

+r

k

Para classes de

autômatos celulares binários com raio maior, 2 por exempl o, há 32 possív eis

vizinhanças, que resultam em

2964.294.967.2

32

= possíveis regras.

2.3.2 Numeração das regras de autômato celular elementar

Stephen Wolfram propôs um esquem a de numeração para os 256 ACs elementares,

no qual os

bits

de saídas são ordenados lexicograficamente (ver Figura 2.3) e são lidos da

direita para a esquerda para formar um binário entre 0 e 255 [Wolfram, 1983a]. Este

esquema proposto por Wolfram é adotado na maior parte das li teraturas técnicas que

abordam o assunto. Dessa forma, é comum referenciar determinado autômato celular

elementar, apenas pelo n úmero da regra de transição. Exemplo : AC elementar 184 ou

Regra 184, representa o autômato celular elementar que poss ui a regra de transição de

estados, de número 184 d e acordo com o esquema de numeração [Wolfram, 1983a].

10

Vizinhança

1 1 1 1 1 0 1 0 1 1 0 0 0 1 1 0 1 0 0 0 1 0 0 0

Número na base binária

0 1 1 0 1 1 1 0

Figura 2.3. Processo de numeração de regras – Regra 110.

Para ilustrar o esq uema de numeração, a regra apresentada na Figura 2.3 (em binário:

01101110) é o AC elemen tar 110 , o mesmo apresentado na Tab el a 2.1.

2.4 O espaço elementar de regras

Todas as 256 regras dos autômatos celulares elementares são equivalent es a uma

outra regra. Essa equivalência pode ser detectada com execução de uma transformação

tipo reflexão, transformação 0 por 1, ou pela operação conjunta das duas transformações

anteriores [W olfram, 1994]. Regras classificadas como equivalentes, aplicadas

N

vezes,

a partir de uma mesma configuração inicial, resultam em um comportamento dinâmico

similar. Essa sim ilaridade d e comp ortamento dinâmico está ilustrada na Figura 2.3.

Pelas transformações sofridas p ela regra 110 e demonstrada nas Tabelas 2.2, 2.3,

2.4 e 2.5, pode-se classificar as regras 110, 1 2 4, 137 e 193 como equivalentes.

011011 10 b = 110 (convertido na base decimal)

11

• Transformação esquerda pela direita ou transform ação do tipo reflexão

de espelho;

i

t

η

111 110 101 100 011 010 001 000

)(

i

t

ηφ

(

Regra 110)

0 1 1 0 1 1 1 0

Tipo Reflexão em

i

t

η

111 011 101 001 110 010 100 000

)(

i

t

ηφ

0 1 1 0 1 1 1 0

i

t

η

111

110 101 100 011 010 001 000

Reordenado (Regra 124)

0 1 1 1 1 1 0 0

Tabela 2 .2. Transformação do AC elementar 110 em sua regra equivalente 124.

•

Transformação de 0s por 1s ou preto por branco;

i

t

η

111 110 101 100 011 010 001 000

)(

i

t

ηφ

(

Regra 110)

0 1 1 0 1 1 1 0

0 por 1 em

i

t

η

000 001 010 011 100 101 110 111

)(

i

t

ηφ

1 0 0 1 0 0 0 1

i

t

η

111 110 101 100 011 010 001 000

Reordenado (Regra 137)

1 0 0 0 1 0 0 1

Tabela 2.3. Transformação do AC elementar 110 em sua regra equivalente 137.

•

Transformação conjunta.

i

t

η

111 110 101 100 011 010 001 000

)(

i

t

ηφ

(

Regra 124)

0 1 1 1 1 1 0 0

0 por 1 em

i

t

η

000 001 010 011 100 101 110 111

)(

i

t

ηφ

1 0 0 0 0 0 1 1

i

t

η

111 110 101 100 011 010 001 000

Reordenado (Regra 193)

1 1 0 0 0 0 0 1

Tabela 2.4. Transformação do AC elementar 124 em sua regra equivalente 193.

12

i

t

η

111 110 101 100 011 010 001 000

)(

i

t

ηφ

(

Regra 137)

1 0 0 0 1 0 0 1

Tipo Reflexão em

i

t

η

111 011 101 001 110 010 100 000

)(

i

t

ηφ

1 0 0 0 1 0 0 1

i

t

η

111 110 101 100 011 010 001 000

Reordenado (Regra 193)

1 1 0 0 0 0 0 1

Tabela 2.5. Transformação do AC elementar 137 em sua regra equivalente 193.

A Figura 2.3 mostra a evolução destas 4 regras em 100 p assos de tempo, sobre

um reticulado de 100 células , para uma mesma configuração inicial. A visualização das

configurações geradas pela evol ução d e um autômato celular, resulta numa figura

denominada diagrama espaço-temporal. E sses diagramas possibilitam efetuar análise de

regras de autômatos celulares, através da detecção de padrões visuais gerado s durante a

evolução. Os 4 diagramas espaço-temporal ilustra dos na Figura 2.3 associados as regras

110, 124, 137, 193, comprovam a equivalência entre as re gras, p ois o mesmo padrão é

apresentado em todas as evoluções .

Figura 2.3. Diagrama espaço-temporal das regras 110, 124, 137 e 193 [Wolfram, 2002].

Regra 11 0 Regra 12 4

Regra 13 7 Regra 19 3

13

Para as 256 regras dos autômatos cel ulares elementares, existem 88 classes de

regras equivalentes. A Tabela 2.6 mostra todas as classes de regras equivalentes do

espaço elementar de regras . Cad a classe é represent ada por uma regra que está colocada

na primeira coluna. As regras equivalentes são representadas logo após a regra

representante da classe, na segunda coluna. A regra escolhida para ser a represent ante é

aquela com menor número de todas as regras equivalentes da classe.

REPRESENTANTE

DA CLASSE

REGRAS

EQUIVALENTES

REPRESENTANTE

DA CLASSE

REGRAS

EQUIVALENTES

REPRESENTANTE

DA CLASSE

REGRAS

EQUIVALENTES

0 255 35 49,59,115 108 201

1 127 36 219 110 124,137,193

2 16,191,247 37 91 122 161

3 17,63,119 38 52,155,211 126 129

4 223 40 96,235,249 128 254

5 95 41 97,107,121 130 144,190,246

6 20,159,215 42 112,171,241 132 222

7 21,31,87 43 113 134 148,158,214

8 64,239,253 44 100,203,217 136 192,238,252

9 65,111,125 45 75,89,101 138 174,208,244

10 80,175,245 46 116,139,209 140 196,206,220

11 47,81,117 50 179 142 212

12 68,207,221 51 146 182

13 69,79,93 54 147 150

14 84,143,213 56 98,185,227 152 188,194,230

15 85 57 99 154 166,180,210

18 183 58 114,163,177 156 198

19 55 60 102,153,195 160 250

22 151 62 118,131,145 162 176,186,242

23 72 237 164 218

24 66,189,231 73 109 168 224,234,248

25 61,67,103 74 88,173,229 170 240

26 82,167,181 76 205 172 202,216,228

27 39,53,83 77 178

28 70,157,199 78 92,141,197 184 226

29 71 90 165 200 236

30 86,135,149 94 133 204

32 251 104 233 232

33 123 105

34 48,187,243 106 120,169,225

Tabela 2.6 . Classes de regras equivalentes do espaço elementar [Wolfram, 1994].

Aplicando uma determin ada regra a uma configuração de autômato celular,

pode-se obter apenas uma única configuração sucessora, porém o número de

predecessores é arbitrário e conhecido como pr é-imagens. O tamanho do espaço de

14

estados de um autômato celular binário com reticulado de N células é

2

N

. P ara

autômato celular com reticulado de tamanho finito, qualquer caminho encontra

inevitavelmente uma repetição de um estado prévio e o que leva a um ciclo de estados.

2.5 Comportamento dinâmico e classificação dos autômatos

celulares

Autômatos Celulares são estruturas computacionais simples, que durante sua

evolução, podem produzir resultados complexos [ Wolfram, 2002]. Para melhor

entendimento , a Figura 2.4 ilustra a evolução da regra 254, apl icada em 4 passos

temporais, a uma simples configuração inicia l representada por uma célula central preta.

Figura 2.4. Evolução da regra 254 [Wolfram, 2002].

O com portamento dessa regra que pode ser classificada como simples, durante

sua evolução, apresenta a cada passo temporal, células da cor preta preenchendo os

espaços no reticulado de maneira uniforme. Modificando sensivelmente esta regra, e

partindo da mesma configuração inicial, pode-se observar um comportamento

interessante na evolução do AC, ilustrad o na Figura 2.5.

15

Figura 2.5. Evolução temporal da regra 250 [Wolfram, 2002].

Com uma simples mudança na regra, o AC apresenta um comportamento

diferente, preenchendo o reticulado com células al ternadas de cor branca e preta, como

um tabuleiro de xadrez. Se modificarmos novamente a regra, podemos obter um

resultado bem mais complexo que os dois anteriormente apresentados.

A regra 90, ilustrada na Figura 2.6, apresenta estruturas triangulares, que se

repetem recursivamente, durante sua evolução.

Figura 2.6. Regra 90 aplicada em 50 passos de tempo [Wolfram, 2002].

Existem diferentes esqu emas de classificação do comportamento dinâmico de

um autômat o celular, dependendo do grau de refinamento desejado. O esquema de

16

classificação mais simples é separar as regras d os autômatos celulares em duas

categorias: as de d inâmica periódica e as de dinâmica não-periódica. Uma vez que as

dinâmicas dos aut ômatos celulares de reticulado finito são sempre periódicas , o critério

se transforma em d eterminar se a dinâmica possui uma periodicidade ‘longa’ ou ‘curta’.

Periodicidade ‘longa’ pode ser entendida como o tamanho do ciclo aumentand o

exponencialmente com o tamanho do reticulado e periodicidade ‘curta’ como o tamanho

do ciclo independente do tamanho d o reticulado.

De acordo com a periodicidade e o comportamento dinâmico que cad a regra

elementar apresenta, Wol fram propôs uma classificação para os autômat os celulares

[Wolfram, 1984], q ue são as m ais referenciadas atualmente (ver Figura 2.7):

•

Classe 1: quase todas as confi gurações iniciais convergem, após um

período transiente, para a mesma configuração fix a.

•

Classe 2: existem muitos estados finais possív eis, mas todos eles

pertencem a um grupo de estruturas simples que se repetem infinitas vezes a cada n

passos de tempo.

•

Classe 3: o compo rtam ento é mais complicado, e pode parecer, m uitas

vezes, aleatório, embora estruturas em escala menor po ssam ser v isualizados.

•

Classe 4: envo lve uma mistura entre a ordem e a ale atoriedade.

Estruturas localizadas são produzidas e repedidas aleatoriamente, interagindo e

possuindo u ma complexidade própria.

17

Figura 2.7. Classes dinâmicas dos autômatos celulares [Wolfram, 1984]. (a) autômato

celular classe 1, (b) autômato celular classe 2, (c) autômato celular classe 3 e ( d) autômato

celular classe 4.

Wentian Li e Norman Packard propuseram uma série de refinamentos na

classificação original de Wolfram [Li e Packard, 1990]. Eles apresentaram um esquema

de classi ficação que divide o esp aço de regras em seis classes, descritas abaixo:

•

Regras Nulas: a configuração limite é formada exclusivamente por

seqüência de 0s ou exclusivamente por sequência de 1s. Regras do Es paço Elementar: 0,

8, 32, 40, 128, 136, 160 e 168.

•

Regras Ponto-Fixo: a configuração limite não se altera ao reaplicarmo s a

regra do autômato celular. Regras do Espaço Elementar (as regras marcadas com * são

aquelas que possuem deslocamento espacial, ou seja, a configuração do autômato

celular é a mesma d a anterior, com o descolamento de uma célula no ret icul ado): 2*, 4,

10*, 12, 13, 24*, 34*, 36, 42*, 44, 46*, 56* , 57*, 58*, 72, 76, 77, 78, 104, 130*, 132,

138*, 140, 152*, 162*, 164, 170*, 172, 184*, 200, 2 04 e 232.

•

Regras Ciclo Duplo: a configuração li mite não se altera ao reaplicarmos

a regra do autômato celular duas vezes. Regras do Espaço Elem entar (as regras

marcadas com * são aquelas que possu em deslocamento espacial): 1, 3*, 5, 6*, 7*, 9*,

18

11*, 14*, 1 5*, 19, 2 3, 25, 27*, 28, 29, 33, 35*, 37, 38*, 43*, 50 , 51, 74*, 108, 13 4*,

142*, 156 e 178 *.

•

Regras P eriódicas: a configuração l imite não se alter a à aplicação da

regra N vezes, com o tamanho do ciclo N, ou ind ependente ou fracamente dependente

do tamanho do reticu la do. Regras do Espaço Elementar: 26, 41, 62, 94 e 154. Em

particular, as regras 62 e 94 exibem dinâmicas de ciclo triplo.

•

Regras Com plex as: embora a dinâmica limite possa ser periódica, o

intervalo de transição pode ser extremamente longo e, tipicamente, este intervalo cresce

mais que linearment e com o tamanh o do sistema. Regras do Espaço Elementar: 54 e

110.

•

Regras Caóticas: produzem dinâmicas não periódicas e se caracterizam

pela div ergência exponencial do comprimento d o seu ciclo com o tamanho do reticulado

e pela instabilidade com respeito a p erturbações. Regras do Espaço Elementar: 18, 22,

30, 45, 6 0, 73, 90, 105, 106, 126, 146, 150 e 122. A regra 73 pode ser classificad a como

Localmente Caótica; pois seu comportamento é periódico com regiões de

comportament o caótico.

2.6 Sensibilidade às condições inicia is

Observando a aparência produzida pel a evolução de aut ômatos celulares, é

possível identificar as 4 classes de autômatos celulares proposto por Wolfram[1984] e

mostradas na Figura 2.7. Dentro d essa classificação, uma característica importante para

ser analis ada é a sensibilidade a condições iniciais [W olfram, 2002].

Mudanças nas condi ções iniciais representam um comportamento dife rente, para

cada tipo de classe. A Figura 2. 8, mostra a evolução de autômatos celulares pertencentes

a cada uma das 4 class es. Os pontos escuros nos reticulados, representam as células que

sofreram mudanças, conse qüente a ún ica c élula modificada n a configuração inicial.

Na classe 1, representada pela regra 160 da Figura 2.8 , o estado fi nal alcançado é

sempre o mesmo in depen dente das con dições iniciais, dessa form a, as alterações nas

condições iniciais não causam e feito nesse tipo de classe. A informação sobre as

condições iniciais é perdida rapidamente, pois a configuração do autômato sempre

evolui de forma rápi da para um mesmo estado final.

19

Em autômatos celulares da clas se 2, repr esentado pela regra 108 na Figura 2.8,

mudanças nas condi ções iniciais persistem durante a evolução do autômato celular, mas

elas sempre se mantém em uma pequena região do autômato. As informações da

condição inicial são mantidas durante a evolução do autômato celular, e perman ecem

isoladas, nunca se com unicando com outras partes do reticulado.

Para a classe 3, entretanto, o com portamento apresentado é diferente. Qualqu er

alteração feita nas condições iniciais se propaga de m aneira uniforme. Uma

característica dos au tômatos celulares da classe 3 é que eles ap resentam uma

comunicação de informação de grande abrang ência dentro do reticulado de forma que

qualquer alteração na condição inicial quase sempre se propagará por todo o reticulado.

Essa característica pod e ser observada através da reg ra 126 na Figura 2.8 .

Na classe 4, representada pela regra 110 da Figura 2.8, as mudanças nas

condições inici ais também se propagam, mas de maneira aleatória. Cada classe de

autômato celular lida com a i nformação de forma particular, esta ca racterística, ocasiona

classes co m diferentes sensibil idades para as condições iniciais.

Regra 160

Regra 108

Regra 126 Regra 110

Regra 160

Regra 108

Regra 126 Regra 110

Figura 2.8. Figura que demonstra os efeitos causados com pequena alteração na

condição inicial para as quatro classes de autômatos celulares [Wolfram, 2002].

20

Autômatos celulares da classe 4 representam comportamento intermed iário entre

as classes 2 e 3. A propagação da informação contida nas condições iniciais é possível ,

mas nem sempre ocorre, ver Figura 2 .9.

Figura 2.9. Efeitos causados com pequena modificação na condição inicial na regra 110

– classe 4 de autômato celular [Wolfram, 2002].

Uma mudança se propaga, e afeta alguma estrutura localizada no espaço, que se

desloca n o reticulado ao l ongo do tempo [Wolfram, 200 2].

21

Capítulo 3

Caracterização de autômato celular através de autômatos

finitos

3.1 Introdução

A teoria de autômat os é um ramo da ciência da com putação que estuda os

componentes comp utacionais abstratos, ou as máqu inas, através de suas representações

matemáticas. Desde a dé cada d e 1930 , quando Alan Mathison Turing iniciou o estudo

dessas máquinas e a criação da Máquina de Turing, até o final da década de 19 50,

quando originou-se a Teoria das Linguagens Formais e a classificação conhecida como

Hierarquia de Chom sky [Chomsky, 1959], as máquinas passaram por um processo de

estudo e evolução. Todos estes desenvolvi mentos teóricos estão relacionados com o que

a ciência da computação faz atual mente. Co nceitos derivados de autôma tos finitos e

gramáticas formais são utilizados com destaque em aplicações como anális e léxica e

sintática de linguagens de programação, modelos de sistemas biológicos, desenhos de

circuitos e desenvolvi mento de importantes tipos de

software

[Hopcroft, Motwani e

Ullman, 2001].

Em [Trafaniuc, 2004], utili zou-se de autômatos finito s para caracterização do

comportament o de autômatos celulares. O desenvolvimen to de recurs os para

representação gráfica, comparação e análise de complexidade dessas máquinas,

permitiram avaliar dinamicamente os au tômatos celulares de outra maneira.

Este capítulo apresenta conceitos, definições e rep resentações de máquinas

finitas de estados, explica a relação existente com os autômatos celulares, e faz uma

abordagem aos métodos desenvolvidos em [Trafaniuc, 2004], reutilizados n este

trabalho.

22

3.2 Alfabetos, palavras, l inguagens formais e gramáticas

Uma linguagem formal

L

pode ser defi nida como conjun to de palavras form a das por

símbolos de um alfabeto

Σ

. Se gue descrição de alguns componentes necessários

para compreensão da defin ição apresentada:

•

Alfabeto e Símbolo: um alfabeto é um conjunto fin ito de símbolos. Portanto, um

conjunto vazio também é con siderado um alfabeto. Um símbolo ou caractere

ı

é uma entidade abstrata básica que assume valores des se conjunto fini to

Σ

. O

tamanho do alfabeto é representado por ||

Σ

||;

•

Palavra: uma palavra, cadeia de caracteres ou sentença sobre um alfabeto

Σ

, é

uma s eqüência finita de símbolos (do alfabeto) ju stapostos. O comprimento da

palavra

Ȧ

, |

Ȧ

|, representa o número de símbolos em

Ȧ

. A palavra vazia,

representada pelo símbolo

ε

, é uma p alavra formada por zero símbolos

[Hopcroft, Motwani e U llman, 200 1];

•

Sub-palavra, prefixo e sufixo : Uma sub-palavra é uma parte contígua da

palavra. A concatenação de duas palavras

x

e

y

é representada por

xy

. U m

prefixo

x

de uma palavra

y

é uma sub-palavra que consiste d e algum número de

símbolos iniciais de

y

, que é

y=xz

, para algum

z

. Um sufixo

x

de uma pal a vra

y

é

uma sub-palavra tal que

y=zx

. Um símbolo pode ser ident ificado dentro de uma

palavra pela sua posição

i

da seguinte forma

Ȧ

i

. Por convenção, assu me-se

0

≥

i

, sendo assim o primeiro símbolo da cadeia é

Ȧ

0

.

Suponha o alfabeto

Σ =

{a,b}, então o conjunto vazio { } e o conjunto {

ε

} são

linguagens formais. O conjunto de todas as palavr as de comprimento

C

no alfabeto

Σ

é

representado por

Σ

C

. O conjunto de pal avras de qualquer compri mento incluindo a

palavra vazia é representado por

Σ

*

. Anal ogamente,

Σ

+

representa o conjunto de todas

as palavras sobre

Σ

excetuando-se a palavra vazia, ou seja,

Σ

+

=

Σ

*

- {

ε

}. Existem dois

procedimentos essenciais para repres entar linguagens: como reconhecedores ou

aceitadores (autômatos), procedimentos que indicam quando uma sequência faz parte da

23

linguagem, e como geradores (gramáticas), proced imentos que enumeram os elem entos

da linguagem. Segue definição de gramática:

•

Gramática: É o tipo mais comum de sistema gerador. Fundamentalmente, uma

gramática é composta por regras de produção, ou regras de re-escrita, através das

quais é possível obter todos os elementos da linguagem a partir de um símbol o

inicial, usando as regras para re-escrever (pro duzir) os elementos. Formalmente,

definimos uma gramática

G como sendo uma construção G ={N,

Σ

, P, S}, onde

N é um alfabeto de símbolo s auxiliares, cha mados de símbolo s não-terminais,

ou, simplesmente, de não-terminais;

o

Σ

é o alfabeto n o qual a linguagem é definida, cujos elementos

são os símbolos terminais, ou, simplesmente, terminais;

o

P é o conjunto de regras de re-escrita, chamadas simplesmente de

regras ou produ ções;

o

S

∈

N, é o símbolo inicial.

3.3 Linguagens regulares, autômatos fin itos e representação

gráfica de máquinas

De acordo com a hierarquia de Chomsky, as li nguagens regulares ou Tipo-3

encontram-se na classe mais simples de linguagens. Nesta seção, a definição formal de

linguagem regular será efetuada através do sist ema reconhecedor correspondente, o

autômato finito.

Um autômato finito é formalmente definido pela quíntupla

},,,,{

0

FqQA

δ

Σ

=

,

onde:

•

Q

representa o co njunto finito de estados

;

•

Σ

é o alfabeto d e símbolos;

•

QQ

→

Σ

×

:

δ

é a regra de transição, normalmente representa da na seguinte

forma

paq

=

),(

δ

, onde

q

é o estado atual,

a

é o símbo lo que a máquina lê, e

p

é o novo estado;

•

0

q

é o conjunto de estados iniciais da máquina e

Qq

∈

0

;

24

•

F

representa o conj unto de estados finais, ou es tado s de aceitação da máqu ina.

As trans ições de estado de um autômato finito ocorrem de acordo com a

representação da máquina; para uma dada transição

paq

=

),(

δ

, o estado

q

é o estado

atual e o estado

p

é o destin o para uma entrada

a

. Para um dado estado

q

e um símbolo

a

a transição

),( aq

δ

pode estar definida, ou não. Caso ela não esteja, a máquina entra em

estado de erro, e s e mpre que a máquina encontra um erro durante a leitura de uma

palavra ela pára a o pera ção imediatamente. A função de transição pode ser estendida

para trabalhar com pala vras utilizando a seguinte notação:

),( sq

i

δ

onde

s

é uma

palavra de sí mbolos. Um autômato reconhece uma palavra se ao final da leitu ra da

mesma a máquina não ent rou em estado de erro. E, o autômato aceita u ma palavra se

depois de reconhecê-la a máquina se encontra em um estad o de aceitação do conjun to

F

[Hanson, 1993].

Um autômato finito é determinístico se nel e há apenas um estado inicial

q

0

, e

para todos os estados as transições de

q

para outros estados o correm até uma vez p ara

cada símbol o. A designação determinístico é baseada no fato de que os símbolos que a

máquina lê determinam a seqüência de transições qu e será reali zada. Em um autômato

finito determinístico um estado pode ter mais de u ma transição, mas cada uma delas

utiliza símbolos diferentes.

Seja A um autômato finito (sistema reconhecedor). A linguagem reconhecida

por A, é uma linguagem regular e pode ser definida pela sentença :

L(A ) = {x

∈ Σ

* |

δ

’(q

0

, x)

∈

F}

A linguagem

L(A)

é o conjunto de todas as palavras reconhecidas pela máquina

A

. Então, pode-se afirmar que o autômato finito

A

reconhece uma linguagem regular

L

se o mesmo aceita todas as palavras de

L

, e não aceita as palavras que não pertencem a

L

.

Através da relação existente entre autômatos finitos e linguagens regulares,

podemos efetuar a com paração de máquinas desse tipo. Imagine a existên cia de do is

autômatos finitos

A

1 e

A

2

, e as seguintes lin guagens regulares

L

1

=L(A

1

) e L

2

=L(A

2

).

Quando

L

1

é idêntico a

L

2

, po de-se afirmar que os d ois autôm atos finitos

A

1 e

A

2

são

equivalentes, ou seja, reconhe cem a mesma linguagem regular. Quando

L

1

é um

subconjunto de

L

2

, pode-se afirmar que o autômato finito

A

1

⊂

A

2

.

25

Uma outra forma de representar uma linguagem regular é através de uma

expressão regular (sistema gerador). Uma expressão regular é construí da a partir dos

seguintes elementos:

1. O alfabeto de símbolos

¦

∈

σ

;

2.

xy

representa a concaten ação de

x

e

y

;

3.

x + y

representa

x

ou

y;

4.

x

+

representa uma o u mais co ncatenações de

x

.

5.

x

*

representa qualquer número de concatenações de

x

, i ncluindo

nenhuma (o que representa a cadeia vazia);

Como exemplo, as expressões regulares para as linguagens aceitas na Figura 3.1,

são: (0+1)

*

para a máquina da esquerda; e (0+11)

*

para a m áquina da direita.

Figura 3.1. Representação gráfica de autômatos f initos determinísticos com alfabeto

binário

Σ

={0,1} que (a) aceita todas as palavras formadas por

Σ

; (b ) aceita a linguagem

(0+11)*.

Os exemplos de autômatos finitos apresentados na Figura 3.1, utilizam a

representação gráfica de máquinas, seguindo a seguint e notação:

•

cada estado é rep resentado por um círcu lo;

•

as setas indicam as transições, e seus índices ou cores indicam o símbolo que é

lido p ara que a mesma ocorra;

•

estado i nicial é representados com uma seta; e

•

os estad os finais são representados por u m círculo duplo.

q0

q1

q0

1

0

(a)

(b)

26

3.4 Semi-autômato

De acordo com Klaus Sutner, autor da biblioteca ‘

Automata Package

’, um semi-

autômato pod e ser definido por [Sutner, 2003] :

},,{

δ

Σ

=

QSA

, onde:

•

Q

representa o co njunto finito de estados

;

•

Σ

é o alfabeto d e símbolos;

•

Q

Q 2: →Σ×

δ

é a regra de transição, onde

Q

2

é o conjunto potência de Q e

pode ser represen tada na seguinte forma

},...,3,2,1{),( pnpppaq

=

δ

, onde

q

é

o estado atual ,

a

é o símbol o que a máqui na lê, e {

p1, p2, p3 , . . . . , pn}

é o

conjunto de possíveis novos estados;

•

Não possui definição de q0 (estado inicial) e F(estados finais), porque todos os

estados são i niciais e finiais.

Pela definição apresentada, semi-aut ômato é um autômato finito não-

determinístico, onde todos os estados d a máquina são i niciais e finais. Portanto, uma

seqüência que será lida pelo autômato pode começar em qualquer estado, e da mesma

forma, terminar em qualquer estado que será reconhecida como uma cadeia válida. Essa

classe de máquina é manipulada e utilizada no processo it erativo desenv olvido e

apresentado em Seção 3.10.

3.5 Configuração de autômatos celulares e relação com

autômatos finitos

Durante a evolução temporal, os autômatos celulares apresentam uma relação

direta com linguagens regulares. Um méto do de caracterizar a evolução de um autômato

celular el ementar vem da t eoria das lingu agens formais [Sarkar, 2000]. O co njunto de

estados que pode surgir após um número finito de iterações na evolução de um

autômato celular unidimensional forma uma linguagem regular, que pode ser

reconhecida por um autômato finito corresponden te [Wolfram, 1984]. Dessa forma,

para cada pass o temporal de uma regra elementar em evolução, pode-se obter uma

máquina de estado correspondente (ver Figura 3.2).

27

Figura 3.2. Relação entre a evolução temporal de um autômato celular elementar e um

autômato finito.

Algumas regras de au tômato celular, apresentam a mesma relação entre

autômatos finit os e configuração de au tômatos celulares, mesmo se tratando da

condição lim ite [Wolfram, 1984]. Ou sej a, para algumas re gras de autômato celular,

existe um autômato finito que reconheçe todas as con figurações possíveis do diagrama

espaço tempo ral, quando o tempo ‘t’ tende a infi nit o. Os t ermos ‘autômato finito limite’

e ‘grafo limite’, utili zados posteriormente neste trabalho, fazem referênci a a essas

máquinas, relacionadas ao comportamento limite.

3.6 Estado inicial do reticula do e sua representação

O estado inicial de um autômato celul ar binário pode ser representado por um

autômato finito onde todas as configurações possíveis de células brancas e pretas (0 e 1,

respectivamente) p odem ocorrer [Wolfram , 20 02]. O autômato fin ito que representa a

condição inicial de um autômato celular binário, deve ser capaz de reconhecer qualquer

cadeia binária. A Figura 3.3 ilustra o grafo de dua s maneiras:

‘autômato finito 5’ reconhece

todas as configurações da

regra ele mentar que aparecem

no instante de tempo t=5

‘autômato finito 13’ reconhece

todas as configurações da regra

elementar que aparecem no

instante de tempo t=13

Evolução tempora l de N Condiçõe s iniciais aplicado a mesma regra elememtar

1

2

N

28

Figura 3.3. Autômato finito representando graficamente a condição inici al de um

autômato celular binário : (a) seguindo a mesma notação descrita na Figura 3.1; (b) forma de

visualização implementada no software Mathematica e utilizada em [Trafaniuc, 2004].

Toda a apresentação de dados e experimentos desenvo lvidos nesta pesq uisa,

utilizará a notação (b) da Figura 3.3. Nesta nota ç ão, todos os estados são finais e o

último estado num erado é o inicial. Outra observação, está relacionada às arestas dos

grafos, que não possuem índice, mas apenas cores. A cor vermelha representa o símbolo

‘0’ e a cor preta o símbolo ‘1’. Durante todo esse trabalho, o t ermo ‘grafo’ é utilizado

para fazer referências à representação gráfica de autômatos finitos determinísticos,

conforme notação descrita.

3.7 Evolução de autômato finito a cada passo de tempo

Para cada confi guração de autômato celular, relacionada a um autômato finito

em particular, é obtido um novo autômato finito, após a evolução de um passo temporal

do autômato celular. A Figura 3.4 apresenta o diagr ama espaço-temporal e os grafos

correspondentes aos 2 primeiros instantes de tempo das regras 255 e 4, do espaço

elementar. Através do s grafos pode-se verificar as possíveis seqüências de células

brancas e pretas (0s e 1s) que podem ocorrer a cada passo de tempo . Em cada caso, as

possíveis seqüências são representadas pelos caminhos percorridos no autômato finito.

q0

0

1

(a)

(b)

29

0

20

40

60

80

100

120

140

0

10

20

30

40

50

0

20

40

60

80

100

120

140

0

10

20

30

40

50

t=0t=0

t=1 t=2

0

1

Regra 255 (1111.1111)

b

Regra 004 (0000.0100)

b

0

20

40

60

80

100

120

140

0

10

20

30

40

50

0

20

40

60

80

100

120

140

0

10

20

30

40

50

t=0t=0

t=1 t=2

0

1

Regra 255 (1111.1111)

b

Regra 004 (0000.0100)

b

Figura 3.4. Diagrama espaço temporal e grafos gerados para 02 passos temporais das

regras 255 e 4 do espaço elementar [Trafaniuc, 2004].

O autômato finito que representa a condição inicial (t=0), para ambas as regras,

representa as condições ini ciais possíveis, onde qualquer seqüência binári a pode

ocorrer. A partir do passo de tempo t=1 da regra elementar 255, o autômato finito passa

a aceitar apenas células pretas, enquanto que para a regra 4 as seqüências reconhecidas

pelo autômato finito são formadas por células pretas isoladas por p elo menos uma

célula branca. As duas regras são respect ivamente parte das classes 1 e 2 de autômatos

celulares. Ao contrário das regras 4 e 255, a maior parte das regras, não estabilizam em

uma configuração limite após o primeiro passo de tempo. Essas regras p assam a

aumentar progressi vame nte o número de estados e, com a evolução do autômato celular,

o conjunto de seqüências que podem ocorrer fica progressivamente menor e o autômato

finito resultante mais complexo. Para regras de classes 3 ou 4, após alguns passos de

tempo, o autômato finito apresenta um rápido crescimento no grau de comp lexi dade.

Este aument o da complexidade do grafo pode ser explicado pela própria complexidade

das regras [Wolfram, 2002]. Observando a Figura 3. 5, a evolução da regra 126 e a

representação gráfica dos autômatos finitos, para o s três pri meiros instantes de tempo

(t=1, t=2 e t =3), pode-se detectar um cres cimento e xponencial da comp lexi dade em

linguagem re gular, representada pelo número de estados e transições entre eles .

30

Figura 3.5. Grafos gerados a cada passo de tempo para a regra 126 [Trafaniuc, 2004].

Normalmente essa complexidade aumen ta com o tempo, porém, mesmo assim,

há regras de autômatos celulares em que a con figuração limite pode ser representada

através de linguagens regulares formais [Wolfram, 1984].

Durante este documento, a ut iliz ação de termos como ‘grafos em evolução

temporal’ o u ‘autômatos finitos em evolução temporal’ são uti lizados para referenciar

os in úmeros grafos relacionados a cada instante de tempo de um autômato celular em

evolução temporal.

3.8 Complexidade em lin guag em regular e caracterização de

autômatos celulares

A análise da complexidad e de linguagens regulares representadas pelo número

de nós e arestas de um grafo para caracterização de autômatos celulares foi iniciada em

[Trafaniuc, 2004]. Nesse trabalho, util izando-se de representações gr áficas de máquinas

para mapear o espaço de estados, e recursos de manipu lação e detecção de estruturas em

grafos, pôde-se detectar característ icas para algum as regras de autômatos celulares, que

permitiram reconstrui r por método iterativo [Wolfram, 2002], a tabela de comp lexi dade

31

de linguagens regulares de [W olfram, 1994], obtendo alguns resultados diferent es e

novos. O presente trabalho segue a mesma linha de raciocínio, extraindo características

do autô mato celular em função da complexidade d e linguagens regulares associadas.

3.9 Tabela de complexidade das linguagens regul ares

Como já mencionado, foi demonstrado em [Wolfram, 1984] que o con junto de

configurações que pode m aparecer na evolução de um autômato celular unidimensi onal,

após um número t fini to de iterações, forma um a linguagem regular. As configurações

possíveis p ara cada instante de tempo, correspondem aos caminhos possíveis d e se

percorrer dentro de um autômato finito.

A Tabela A.1. [Wolfram, 1994], que representa a tabela de complexidade das

linguagens r egular es, tem como base as 256 regras elementares de autômatos celulares e

apresenta o número mí nimo de estados e transições dos autômat os finitos em cada caso.

As dimens ões apresentadas são baseadas em autômatos finitos determinísticos, onde um

estado da máquina é inicial e todos os estados são finais. A tab ela é constituída por 136

linhas, que representam as 255 regras ag rupadas por equivalências obtidas apenas p elas

transformações de 0s por 1s. Para formação dest a tabela, n ão são consideradas

equivalentes as regras obtidas pela transformação por tipo reflex ão e, portanto, não são

excluídas da t abela. Por exemplo, verificando a Figura 2.3 que apresentam as regras

equivalentes 110, 124, 137 e 193, a Tabela A.1. apresenta a regra 110 e 124, porque são

equivalentes apenas pela transformação por tipo reflexão. Entretant o, as outras duas

regras 137 e 193, são equivalentes às regras 110 e 124 respectivamente, pela

transformação de 0s por 1s, dessa forma nã o aparecem na tabela po rque são

consideradas de mesmo grupo. As regras equ ivalentes por transformação de 0s por 1s

são agrupadas porque um autômato finito relacionado a essas regras apres e ntariam as

mesmas conexões e mesmos números de nós, invertendo ap enas as cores das arestas.

Por outro lado, regras equi valentes pela transformação por tipo reflex ão retratam

máquinas não equivalentes, com conexões ou nós diferentes. A primeira coluna da

tabela indica o n úmero da regra elemen tar, e as colunas seguintes indicam a dimensão

do autômato finito para determinados passos de tempo, q ue são: 1, 2, 3, 4, 5, pas sos de

tempo maiores que 5, e infinit o. Para se efet uar a lei tura da dimensão das máquinas, os

números que estão dentro do s colchetes significam o número d e transições, e fora dos

colchetes o número de estados.

O hífen indica que a linguag em regular é a mesma do

32

passo de tempo anterio r. As entradas na última coluna apresentam o tamanho dos

autômatos fini tos representando o limite de estados que po de ser at ingido para qualquer

passo de tempo. Para algumas regras foram apresentadas fórmulas para compor o

autômato finito para um determin ado passo de tempo

t

. Para ilustrar o funcionamento da

Tabela A.1, an alisaremo s os dados da regra 10 da tabela, junto com o grafo

correspondente, na Figura 3.6.

Regra t = 1 t =2 t = 3 t = 4 t = 5 t >5 

10 4[6] - - - - 4[6] 4[6]

Figura 3.6. Leitura da Tabela A.1. [Wolfram, 1994].

Em [Trafaniuc, 2004] reconstruiu-se a tabela de complexidade de linguagens

regulares. A nova tabela exibe dados da tabela original [Wolfram, 1994 ] e de forma

comparativa, os nov os dad os gerados. Outras informações adicionais ilustram a tabela,

como a classificação dinâmica [Li e Packard, 1990] e a equivalência de regras.

Trafaniuc [2004] obteve novos resultad os e algumas d iferenças com relação à tabela

anterior, principalmente em regras ciclo-dup lo e ponto-fixo. Estes resultados são

apresentados n a Tabela A.2.

1

2

3

4

Dados extraído da Tabela A.1.

t=1

Indica uma máquina de

4 estados e 6 transições

Após o instante de

tempo t=1, o autômato

se repete.

Complexidade do autômato finito que

representa a configuração limite da regra 10

O autômato fi nito gerado para o passo de tempo t=1 e t=2

apresenta 4 estados e 6 transições, conforme a tabela

acima. Após o instante t=1, o AC atinge a con figuração

limite.

1

2

3

4

t=2

33

3.10 Funções NetCAStep, TrimNet e MinNet

NetCAStep, TrimNet e MinNet [Wolfram , 2002] sã o funçõ es desenvol vidas no

Mathematica

e utilizadas para gerar e representar máquinas de estados finitos , a cada

passo d e tempo na evolução de autômatos celulares elementares.

Dado um semi-autômato qualquer, relacionado a configur a ções de autômato

celular para um in stante de tempo t, a função NetCAStep [Wolfram, 20 02] reto rna um

autômato finito relacionado ao instante de tempo t+1.

Os parâm etros de entrada da função Net CAStep são:

•

o núm ero de estados do autômato celular, que no caso é binário k=2;

•

raio da vizinhança do autômato celular, no caso do s autômatos ce lulares

elementar, raio=1;

•

número da regra de autômato celular;

•

a lista de transi ções de estado do semi-autôm ato de instante t, a partir da qual

será aplicada a regra do autômato celular.

A função NetCAStep gera co mo saída, uma l ista de transiç ões d e estados

correspondente a um autômato finito não-determinístico (AFND) [Wolfram, 2002].

Sobre a li sta de transições de estado resultante da fu nção NetCAStep é aplicada a

função TrimN et [Wolfram, 2002], qu e por sua vez, preserva todos os estados acessíveis

por qualquer nó da rede. Para exemplificar, verifique o grafo da esquerda na Figura 3.7

abaixo, que representa uma cert a máquina.

1

2

3

4

5

Figura 3.7. Execução da função TrimNet.

Perceba-se que o s estados 3 e 5 não são acessí veis se a máquina for iniciada

pelos nós 1, 2 e 4. Por outro lado, os nós 1, 2 e 4 da máquina podem ser acessados por

1

5

TrimNet

1

2

3

1

34

qualquer nó inicial na rede. O grafo da direita na Figura 3.7, ilustra a lista de transição

com a retirada dos nós.

Finalm ente, a l ista de transições de estado gerada pela função TrimNet é

aplicada na entrada da fun ção MinNet [Wolfram, 2002] . O resultado obtido é uma lista

de transições de estado, referente a u m autômato finito m ínimo e determinístico

equivalente, com o último estado inicial e tod os finais. Para esta função , é importante

destacar a seguinte informação fornecida:

“Em geral, MinNet produzirá uma rede onde

qualquer sequência permitid a de valores corresponderá a um caminho in iciado pelo nó

1”

[Wolfram, 2002, página 957 ] . Baseados em experimentos realizados com a

aplicação da função para as regras 18, 22, 72 e 126 e, comparando os resultados obtidos

com os respecti vos autômatos finitos determinísticos destacados em [ Wol fram, 1984],

detectou-se que, o estado inicial produzido pelo MinNet é o último nó da rede, ao

contrário da in formação em [Wolfram, 2002].

A saída da composição adequada das fun ções NetCAStep, Trim Net e MinNet é

um autôm ato finito determinístico que reconhece to das as configurações possíveis para

um passo de tempo seguinte, na evolução de uma regra dos autômatos celulares

elementares. A Figura 3.8 ilustra o funcionamento do fluxograma com as 3 funções

conectadas.

Figura 3.8. Seqüência de utilização de NetCAStep, TrimNet e MinNet.

NetCAStep

Entrada :

- semi-autômato

- número da Regra de AC.

Saída:

- autômato finito não

determinístico relacionado ao

instante seguinte de tempo.

TrimNet

Entrada :

- autômato finito

Saída (S.A.N.D.):

- semi-autômato mantendo

apenas os nós acessíveis por

qualquer nó da rede.

Entrada:

- semi-autômato

MinNet

Saída: (A.F.D.)

- autômato finito

determinístico equivalente

Deseja gerar

autômato para

sim

não

35

3.11 Métodos de análise desenvolvidos em [Trafaniuc, 2004]

Utilizando com o base as funções mencionadas na seção anteri or, desenvolveu-se

no

Mathematica

métodos para analisar e exibir a evo lução das regras elementares de

autômatos celulares. Através destes desenvolvimentos, a tabela de complexidade de

linguagens regulares [Wolfram, 1994] foi recon struída, e para algumas regras

elementares, foi possível detectar padrões e express ões de crescimento do autômato

finito determinístico que estavam v azias na tabela original.

Em [Trafaniuc, 2004] o termo ‘grafo de processo’ ou ‘grafo de transição de

estados’ [Hanson, 1993] é definido como um semi-autômato. Desta forma, a seguin te

informação

“Todos os autômatos finitos obtidos e estudados no presente trabalho serão

grafos de processo”

[Trafaniuc, 2004, página 18], está equivocada, já que todas as

máquina geradas e representadas visualmente são derivadas da saída da função M inNet,

portanto são autômatos finitos determinísticos. Em [Trafaniuc, 2 004] o problema de

divergência entre o funcionamento da função MinNet e a descrição em [Wolfram,

2002], explicado na S eção 3.1 0, tamb ém não foi identificado.

O método iterativo implementado em [Trafaniuc, 2004] utilizava uma seqüência

de realimentação diferente da apresentada na Figura 3.8, com a saída da função MinNet

efetuando a realim entação do laço. Para o desenvolvimento deste trabalho, essa

seqüência foi conceitualment e modificada, justificada pelo tipo de entrada esperada pela

função NetCAStep (Figura 3.8). A m udança n esta seqüência também foi uma tentativa

para explicar algumas diferenças encontradas entre os resultados de [Tra faniuc, 2 004] e

[Wolfram, 1994]. Porém, para as 26 regras detalhadamente analisada neste trabalho, os

resultados se mantiveram iguais.

Um pont o importante para análise desta diferença, pode ser constatado através

da observação da regra 108 que apresenta dados divergentes entre as tabelas. Em

[Wolfram, 2002, página 27 8] a complexidade desta regra é exibida para 4 passos de

tempo. Contando o número de nós e arestas de cada grafo apresen ta dos no livro e

comparados com os dados da regra 108 apresentado s em [Trafaniuc, 2004], observamos

que são iguais (a Figura 3.9 il ustra o processo de validação). Através dessa observação,

podemos conclu ir que muito provavelmente existia um erro no código original ut ilizada

na const rução de [Wolfram, 1994] que foi corrigido em [Wolfram, 2002].

36

Figura 3.9. Validação dos dados apresentados em tabela de [Trafaniuc, 2004].

Na primeira parte do método Trafaniuc [2004] utilizou-se de um algoritmo

iterativo, utilizando as funções NetCAStep, M innet e TrimNet, e aplicou às 256 regras

de autômatos celulares com cinco número máximo de iterações (ver Figura 3 .10).

Figura 3.10. Ilustração do algoritmo utilizado e m [Trafaniuc, 2004].

retirado da Tabela A.2 [Trafaniuc, 2 004]

retirado livro NKS [Wolfram, 2002]

NetCAStep, TrimNet

e MinNet

Autômato finito referente ao

instante t+1, na evolução do A C

Realimentação passando como

parâmetro autô mato de t+1

Autômato

de t é Igual ao

Autômato de

t+1 ?

N iteração

atingido ?

Não

Sim

256 regras elementares

Regras do Grupo1

Regras do Grupo2

37

Como resultado da aplicação d o algoritmo, as 256 regras elementares foram

divididas em dois grupo s, de aco rdo com os crité rios de parada:

•

Grupo 1: regras que apresentam crescimento de complexidade no autômato

finito limite a cada passo de temp o, e o método é interrompido quando o número

máximo d e passos de execução é atingid o;

•

Grupo 2: regras qu e não apresentam crescimento de complexidade no autô mato

finito limite a cada passo de tempo, e o método é interrompido quando o

autômato finito limite é atingido

Para exemplificar, a Tabela 3.1 exibe a evolução de autômatos finitos para regra

do grupo 1 e 2.

Regra Passo 1 Passo 2 Passo 3 Grupo

19

2

128

1

Tabela 3.1. Evolução dos grafos para regras com critérios de paradas distintos.

Observe-se que, para cada passo, a regra 128 apres enta um grafo mais complexo,

ao contrário da regra 19 que apresenta máquinas i guais para o passo 2 e 3 .

38

3.12 Detecção d e estrut uras comuns em passos d e tempo

consecutivos

Observando grafos em e volução, pode-se det ectar que para algumas regras do

grupo 1, uma parte das estruturas dos autômatos não se alteram, e se repetem em passos

de tempos consecutivo s. Na Tabela 3.1, repare que a regra 128 apresenta para cad a

instante de tempo um novo grafo, porém esses grafos possuem estrutura que se mantêm

durante a evolução. O que diferencia um instante do outro é a inclusão de novas

transições, representadas por arestas em vermelho. A presença destas estruturas em

passos consecutivos da evolução temporal, funcionam como um indicad or das regras

para as qu ais há possibilidades de se obter expressões de crescimento e repres entação

dos grafos dela derivados. C om o objetivo de i dentificar essas regras, criou-se um

método de busc a autom ático para identificação de estruturas básicas presentes na

evolução de autômatos celulares elementa res. Abaixo, segue em 4 passos o algoritmo

desenvolvido e m [Trafaniuc, 2004], exemplificado para a regra 128:

1. Gerar os grafos das regras de transição, para dois passos de tempo

consecutivos, t e t+1, de uma regra do espaço elementar (ver a Figura 3.11).

Figura 3.11. Grafos de tempos c onsecutivos (t e t+1) da regra 128.

2. Gerar todos os possíveis subgrafos do passo de tempo t+1 que tenham o

mesmo número de estados que o grafo do passo de tempo t. A Figura 3.12

exibe todos os subgrafos possíveis do Grafo T+1 com 4 estados;

1

2

3

4

12

3

4 5

6

Grafo T

(instante t com 4 estados)

Grafo T+1

(instante t+1 com 6 estados)

39

Figura 3.12. Geração de subgrafos de t+1 com mesma quantidade de nós que o grafo em

t.

3. Selecionar todos os sub grafos gerados com base no passo de tempo t+1 que

se encaixam perfeitamen te no grafo do passo de tempo t. Ou seja, selecionar

os subgrafos gerados no passo 2, q ue também são subgrafos do grafo no

tempo t. Para melhor entendimento, verifique a Figura 3.13;

Figura 3.13. Seleção de subgrafos candidatos para identificação da estrutura comum em

passos de tempos consecutivos.

4. Realizar uma operação de diferenç a entre o grafo de t e todos os subgrafos

de t+1 selecionados no passo 3. Essa operação de diferença é executada p ela

função

GraphDifference

do pacote

DiscreteMath `Combina torica

do

Mathematica

, e retorna as diferentes arestas entre dois grafos com mesmo

número de nós. O subgra fo que apresentar a menor diferença no número de

12

3

4 5

6

Grafo

T+1

Subgrafos derivad os do

Grafo B com 4 estados.

Todos os subgrafos

derivados do Grafo

T+1 com 4 estados

Selecionar os subgrafos

que en caixam

perfeitamente

Os dois s ubgrafos F e A do Grafo

T+1 encaixam perfeitamente no

Grafo T.

1

2

3

4

Grafo T

D E F

A B C

F A

40

transições de estados, é selecionad o. No caso de empate, o primeiro subgrafo

é selecionado.

Figura 3.14. Seleção de subgrafo com menor diferença.

O processo de detecção de subgrafos desenvolvido em [Trafaniuc, 2004],

em resumo é uma ope ração en tre grafos de tamanhos diferentes, que identifica o

maior grafo passado como parâmetro e retorna o maior subgrafo comum com

mesmo n úmero de nós do grafo menor. O termo ‘máximo subgrafo comum’ é

utilizado nest e trabalho para fazer referência ao sub grafo retornado por esta

operação. Lembrar que em alguns casos para essa op eração, a inexistência do

máximo subgrafo comum pode ocorrer.

Em [Trafaniuc, 2004], o algoritmo foi executad o para cinco instantes de

tempo da regra de autômat o celular em evolução. Foram selecionados apenas as

regras que apresentam subgrafo com um de temp os consecutivos, entre os cinco

instantes ex e cutados.

1

2

3

4

Grafo T

Subgrafos de

T+1 Candidatos

1

2

3

4

Subgrafo

Selecionado

Resultado da

Diferença

41

Regra 12 8 Grafo

T

Máximo

Subgrafo

comum

Grafo

T+1

Passo 1 e 2

1

2

3

4

1

2

3

4

12

3

4

5

6

Passo 2 e 3

12

3

4

5

6

1

2

3

4

5

6

1

2

3

4

5

6

7

8

Passo 3 e 4

1

2

3

4

5

6

7

8

1

23

4

5

6

7

8

1

23

4

5

6

7

8

9

10

Passo 4 e 5

1

23

4

5

6

7

8

9

10

1

2

3

4

5

6

7

8

9

10

1

2

3

4

5

6

7

8

9

10

11

12

Tabela 3.2. Resultado do método de busca de subgrafos comum da Regra 128.

Observe que a regra 128 apresenta subgrafos em comum entre dois

passos de tempo consecutivos, nos 5 passos temporais de ev olução em que fo i

executada. Após a apli cação do método às regras do gru po 1, identificaram-se 26

regras (11, 14, 23, 35, 43, 50, 56, 70, 81, 9 8, 113, 1 28, 13 2, 136, 140, 142, 162,

168, 172, 176, 184, 192, 196, 212, 224 e 232) que apresentaram estruturas

comuns em passos de tempos consecutivos, e que foram analisadas e

investigadas posteriormente. E ssas regras são class ificadas como ciclo-duplo,

nula ou ponto-fixo.

42

Capítulo 4

Análise da complexidade em linguagem regular

relacionada a autômato celular

4.1 Análise automática do crescimento de grafo s

Como explicado na Seção 3.12, os processos desen volvidos por Trafaniuc

[2004], selecionaram 26 regras. E m continui dade Trafaniuc [2 004] passou a observar

visualmente os grafos e os relacionamentos existentes, obtendo manualmente algumas

expressões de crescimento de nós e arestas, ou expressão de crescimento de

complexidade, do s autô matos finitos det erminísticos em função do tempo. Como parte

do objetivo deste trab a lho, essa tarefa foi automatizada. O método original [Trafaniuc,

2004], que gerava e exibia resultados no mesmo processo, foi modificad o e dividido em

dois módulo s: módulo de geração e armazenamento de dados, e o módulo de análise de

resultados. As mesmas 26 regras (11 , 14, 23, 35, 43, 50, 56, 70, 81, 98, 113, 128, 132,

136, 140, 142 , 162, 168, 172, 176, 184, 192, 196, 2 12, 224 e 232) que apresentaram

estruturas em comum, para passos de tempos consecutivos, identificadas na Seção 3.12

[Trafaniuc, 2004], foram executadas nos novos módulos para avaliação.

4.1.1 Módulo de geração e armazenamento de dados

O m ódulo de geração foi desenvolvido c om base no algoritmo de [Trafaniuc,

2004] ilustrado na Figura 3.10, ut ilizando as funções Net CAStep, Minnet, TrimNet

[Wolfram, 2002], e a função de det ecção de s ubgrafos comuns, descrito na Seção 3.12.

Porém, verificou-se que para algumas regras de autômato celul ar, além dos grafos em

evolução, e subgrafo s comuns de grafos em tempos consecutivos (ver exemplo na

Tabela 3 .2), seriam n e ces sárias informações adi cionais para p ermitir que o módulo de

análise detectasse características presentes nas regras. Dessa forma, foi desenvolvida e

incluída ao módulo, uma nova operação que representasse a diferença entre grafos,

durante a evolução temporal.

43

Todos os resultados gerados neste módulo são armazenados de forma

estruturada em arquivos de disco.

Figura 4.1. Módulo de geração e armazenamento.

Para cada regra elementar executada, os seguintes dad os são gerados:

•

autômato finito determinístico referentes a cada pa sso temporal;

•

subgrafos comuns para grafos de tempos consecutivos;

•

grafos que representam a diferença entre autômatos finitos determiní stico

de temp os consecutivos.

4.1.2 Operação de diferença entre grafos

A detecção d o máximo subgrafo comum apresentado na Seção 3.12 permite

identificar regras que apresentam estrutura em comum para instantes consecutivos de

tempo. Porém não permi tem identificar e, por conseqüência comparar essas es truturas

ao longo de um período. Dessa forma, s ur giu a necessidade de obter uma informação

que demonstrasse a diferença entre grafos de tem pos cons e cutivos. No pacote

Método iterativo de evolução

temporal (NetCastep, Minnet,

Trimnet,)

Dados armazenados de fo rma

estruturada:

- número da regra;

- grafo em evolução tempora l;

- subgrafo comum em tempos

consecutivos de grafos;

- diferença de grafos em tempos

consecutivos;

Módulo de

g

eração

e

a

rmazenamento

de dados

Gravação de resultados em

arquivos de disco

44

DiscreteMath`Combin a tori ca

do

Mathematica

, existe a função

GraphDifference

que

efetua a diferença de dois grafos co m o mesmo número de nó s. Essa função não foi

utilizada diretamente na com paração de máquinas de tempos consecutivo s, porque o

número de nós normalmente cresce com o tempo. Por essa razão, houve a necessi dade

de criar u ma nova função

Durante a criação dessa funç ão, levou-se em consideração o universo d e regras

em que el a seria utilizada, ou seja, as 26 regras mencionadas na Seção 4.1. Dessa

maneira pôde-se partir da premissa que a operação ocorreri a entre grafos que

apresentam máximo subgrafo comum para passos de tempos consecut ivos. O algoritmo

desenvolvido para operação de diferença é demonstrado no s passos seguintes:

1. Obter o máximo subgrafo comum (descrito na Seção 3.12) entre o grafo

no ins tante t e o grafo no in stante t+1;

2. Como o máximo su bgrafo comum possui o mesmo número de n ós do

grafo de instante t, utilizar a função

GraphDifference

e obter a diferença

de arestas entre o máximo subgrafo comum e o grafo de t. Essa diferença

de arestas representa o grafo excluído em t na construção de t+1, e é

mencionada n este documento como ‘estrutura excluída’ (ver Figura 4.2);

Figura 4.2. Ilustração da implementação da operação de diferença.

3. Extrair do grafo do instante t+1 o máximo subgrafo comum utilizado no

passo 2 , mantendo o mesmo número de nós do grafo t+1;

Estrutur a

Excluída

Extrai o

máximo

subgrafo

comum

GRAFO

T +1

Máximo

subgrafo

comum de

T e T+1

Estrutura

Adicionada

GraphDifference

GRAFO

T

GraphDifference

resultado da operação

formado pelo par de

estruturas

45

4. Utilizar a função

GraphDifference

e obter a d iferença de arestas entre o

máximo subgrafo comum do passo 3 e o grafo de t+1. Essa diferença de

arestas represent a o grafo adicionado em t+1 que n ã o existe em t, e é

mencionada nes te documento como ‘estrutura adicionada’ (ver Figura

4.2);

Além d a diferença de número de nós, a operação que representa a diferença entr e

grafos foi desenvolvida conside rando o fato de que, um grafo em evolução temporal

sofre algumas t ransformações. Ou seja, para cada avanço do passo temporal, estruturas

são excluídas e adicionadas ao grafo. O res ultado da operação de diferença

desenvolvido é representado pelos grafos ‘Es trutura Adicionada’ e ‘Estrut ura Excl uída’.

A Figur a 4. 3 ilustra o resultado da operação de diferença para grafos em in stantes

consecutivos de tempo para regra elementar 1 84.

1

2

3

4

12

3

4

5

6

12

3

4

5

6

1

2

3

4

1

2

3

4

12

3

4 5

6

Figura 4.3. Operação de diferença aplicada entre grafos da regra 184 nos instantes t=1 e

t=2.

t=1

t=2

Estrutura Adicionada

Estrutura Excluída

t=1

t=2

Estrutura excluída

Máximo subgrafo comum

Estrutura adicionada

REGRA 184

46

Na ilustração, a estrutura excluída é destacada em vermelho e a estrutura

adicionada destac ada em verde. As duas estruturas forma o retorno da operação de

diferença. As arestas marcadas em azul, representam o que foi mant ido, ou seja, o

máximo subgrafo comum entre t e t+1. Essas informações coletadas durante a execução

do método iterativo, permitem efetuar importantes observações e análise do

comportament o de algumas regras em evolução.

O termo ‘estrutura líquida adicionada’ utilizado neste documento está

relacionado ao par de grafos estrutura adicionada e excluída, e tem o objetivo de fazer

referência a transformação sofrida pelo grafo T para construir T+1.

4.1.3 Módulo de análise d e resultados

O módulo de análise de resultados efetua a recuperação dos dados gerados pelo

módulo de geração e, em função dessas informações, analisa e exibe resultados que

caracterizam as regras elementares de autômatos celulares. As regras analisada por este

módulo apresentam:

•

tipo do crescimento dos grafos durante a evolução de um autômato

celular (li near ou não-linear);

•

expressão de crescimen to do número de nós em função do tempo;

•

expressão de crescimen to do número de arestas em função do tempo;

•

instante de tempo em qu e o grafo inicia um crescimento cíclico;

•

dimensão do ciclo de crescimento do s grafos (simples, duplo);

•

estrutura(s) adi c ionada(s) ciclicamente durante a evolução temporal.

O Apêndice A.3 exibe o resultado das 26 regras analisadas pelo módu lo, com 8

iterações. Para cada regra analisada, as informações ant eriormente citadas são

organizadas nos tópicos explicados abaixo, que é ilustrado na Figura 4.4. com

resultados da r egra 70:

47

REGRA ELEMENTAR 70

Grafo em Evolução

GRAFO T COMUM GRAFO T+1 ESTR.ADIC. ESTR.EXCLUÍDA

1

2

3

1

2

3

1

2

3

4

5

6

7

1

2

3

4

5

6

7

1

2

3

1

2

3

4

5

6

7

1

2

3

4

5

6

7

1

2

3

4

5

6

7

8

9

1

2

3

4

5

6

7

8

9

1

2

3

4

5

6

7

1

2

3

4

5

6

7

8

9

12

3

4

5

6

7

8

9

1

23

4

5

6

7

8

9

10

1

23

4

5

6

7

8

9

10

1

2

3

4

5

6

7

8

9

1

23

4

5

6

7

8

9

10

1

2

3

4

5

6

7

8

9

10

1

2

3

4

5

6

7

8

9

10

11

1

2

3

4

5

6

7

8

9

10

11

1

23

4

5

6

7

8

9

10

1

2

3

4

5

6

7

8

9

10

11

1

2

3

4

5

6

7

8

9

10

11

1

2

3

4

5

6

7

8

9

10

11

12

1

2

3

4

5

6

7

8

9

10

11

12

1

2

3

4

5

6

7

8

9

10

11

48

1

2

3

4

5

6

7

8

9

10

11

12

1

2

3

4

5

6

7

8

9

10

11

12

1

2

3

4

5

6

7

8

9

10

11

12

13

1

2

3

4

5

6

7

8

9

10

11

12

13

1

2

3

4

5

6

7

8

9

10

11

12

1

2

3

4

5

6

7

8

9

10

11

12

13

1

23

4

5

6

7

8

9

10

11

12

13

1

2

34

5

6

7

8

9

10

11

12

13

14

1

2

34

5

6

7

8

9

10

11

12

13

14

1

2

3

4

5

6

7

8

9

10

11

12

13

Análise do Crescimento

- Crescim en to Linear: Sim

- Expres sao de Crescimento Nó: 6+t Início e m t= 3

- Expres sao de Crescimento Aresta: 12+t Início em t=

3

Estrutura Repetitiva

1

2

3

4

5

6

7

1

2

3

4

5

6

1

2

3

1

2

3

4

Análise do Ciclo das Estruturas Repetitivas

- Estrutu ra 1 => Ciclo: 0 Inicio e m t = 2

- Estrut ura 2 => Ciclo: 0 Inicio e m t = 3

- Estrut ura 3 => Ciclo: 2 Inicio e m t = 4

- Estrut ura 4 => Ciclo: 2 Inicio e m t = 5

Figura 4.4. Resultados da regra ele mentar 11 retirada do Apêndice A.3.

1.

Grafo em Evolução:

são exibidos todos os grafos utiliz ados na análise, ou seja,

os grafos de cada instante de tempo, máximo subgrafo comum para grafo de

passos consecutivos e os grafos que representam a diferença de grafos: estrutura

excluída e adicionada.

2.

Análise de Crescimento:

informa se o número de nós e arestas do grafo cresce

linearmente com o tempo. Quando afirmativo, as exp ressões de cres cimento são

apresentadas, junto com o instante de tempo em que se inicia a linearidade. Ver

pela Figura 4.4 que a regra 70 possui crescimento l inear a partir do instante de

49

tempo t=3. Dessa forma, a expressão de crescimento tanto para o número de nós

(6+ t), quanto para o número de arestas (12+t) são apresentadas. E ssa linearidade

é calculada uti lizad o a função

FindFit

com base nos n úmeros de nós e arestas

dos grafo s de T para cada instante de tempo.

3.

Estrutura Repetitiva:

neste item s ão exibidas as diferentes estruturas

adicionadas aos grafos durante o período de dado coletado. Para obter essas

estruturas o algoritmo efetua um agrupamento de todas as es truturas da coluna

‘Estr.adic’. Observe pela Figura 4.4. que 4 estruturas são exibidas nesse item

para regra 70, ou seja, se a coluna que exibe os grafos que representam as

estruturas adicionais forem verificadas e agrup adas para o períod o executado,

será identificado 4 diferentes grafos. A mesma informaç ão poderia ser extraída

da coluna estrutura excluída, porém como não acrescenta nenhuma informação

adicional, não foi implementada na análi se de resultados.

4.

Análise do Ciclo das Estruturas Repetitivas:

todas as estruturas repetitivas

apresentadas no item anterior possuem uma cl assificação conforme o ciclo de

repetição. Dependendo da regra, as estrutu ras podem aparecer somente em uma

única iteração (ci clo = 0), durante todas as iterações (ciclo = 1 ou ciclo simples),

ou em i terações int ercaladas com outra estrutu ra repetitiva (ciclo = 2 ou ciclo

duplo), e ass im por diante. Para exemplificar, observe os dados da regra 70, na

Figura 4.4. A regra apresenta 4 estruturas repetitivas, onde as duas primeir as não

possuem ciclo de repetição (ciclo=0), ou seja, aparecem somente em uma única

iteração (t=1 para t=2 e t=2 para t=3). As demais estruturas rep etitivas,

classificadas como ci clo duplo (ciclo = 2), i ndicam que após a iteração t=3 para

t=4, ficam intercalando entre si. Uma observ ação neste item é v álida para a

interpretação do tempo ‘início em t’ apresentada. Como a estrutura rep etitiva

considera sempre dois grafos de inst antes de tempos consecutivos, quando o

tempo t é apresentad o, considerar que a estrutura aparece na iteração do instante

(t-1) para t.

5.

Quadro Resumo:

exibe todas as regras que fo ram executadas e analisadas,

classificando-as por linearidade no crescimento. Apresenta as regras com os

respectivos ciclos. Por exemplo, à regra 70 associa-se ‘Ciclo {0, 2}’, sendo que

o zero indica que inicialmente não existe estrutura(s) repetitiva(s), mas após um

50

ou mais instantes de tempo, a regra passa a apresentar estruturas com ciclo

duplo representada pelo número 2 .

4.2 Em busca da caracterização do comportamento limite

A estratégia de trabalho adotada para o desenvolvimento de um algoritmo capaz

de obter o autômato finito determinístico que corresponda ao comportamento limite de

um autôm ato celular foi observar e as sociar dados gerados pelos módulos, para algumas

regras com comportamento limit e conhecido. Como não foi possível obter esse

algoritm o, esta seção descreve o que foi observado e estudado.

Na dinâmica de autômatos celulares existem configurações que são transient es e

de certo modo podem aparecer previamente somente durante a evolução. O conceito de

configuração limite está relacionado às configurações que são importantes num período

longo de execução, ou seja, configurações não transien tes [Kari, 2005]. Na real idade, a

configuração limite de um autômato celular é uma configuração única contendo apenas

a configuração estável, ou é infinita e contém algumas configu rações não perió dicas.

Dessa maneira, para os casos em que a co nfiguração é estável após n passos, a

configuração limite é finita [Hurd, 1987].

Como já mencionado, o conjunto de configurações gerados por um autôm ato

celular, para um número finito de passos, forma uma linguagem regular. Quando se trata

de limite de tempo infinito, apenas algumas regras podem ser caracteriza das por uma

linguagem regular. Os a utômatos celulares com comportamento de classe 1 e 2 fazem

parte dessas regras, por outro lado, as regras com comportamento d e classe 3 e 4, que

apresentam como conjunto de configuração linguagem regular com crescimento de

complexidade exponencial ao tempo, provavelmente apresentarão c onjuntos de

configuração limite corresp ondente a linguagens formais mais complicadas [Wolfram,

1984].

As 26 regras selecionadas e an alisadas no presente trabalho são classificadas

dinamicament e como classe 1 e 2 [Wolfram, 1984]. Mesmo trabalhan do em universo

restrito, com regras que conver gem a linguagens regulares em suas con f igurações

limites, a tarefa de desenvolver um algoritmo para obtenção da linguagem regular

correspondente ao comportamento limite não foi concluída co m sucesso. To dos os

51

dados gerados e analisados nos módulos de crescimento tratados na Seção 4.5

permitiram concluir informações import antes relativas ao comportament o dinâmico e

limite das regras no ent anto, encontrou-se grande difi culdade em conectar esses dado s

com o comportamento limite, através de um único algoritmo.

Os próximos itens desta seção ilustram o estudo efetuado utilizando como base a

regra 184, destacando associações importantes observad a s e pontos críticos

encontrados, durante a tentativa de desenvolvimento do algoritmo.

4.2.1 Grafo limite da reg ra elementar 184

A regra elementar 184 foi utilizada como base para o desenvolvimento do

algoritm o de geração de grafo limite por ser u ma regra com co mportamento limite

conhecido. Ela possui basicamente 3 configurações limites, representadas por uma

linguagem re gular, e que dependem exclusivamen te da configuração inicial do autômat o

celular:

•

Configuração inicial com número de 1s igual ao nú mero de 0s

(#1s = #0s)

,

implica em configuração limi te com 0s e 1s intercalados, conforme a Figura

4.5;

Figura 4.5. Regra 184 em evolução temporal com condição inicial (#1s = #0s).

•

Configuração inicial com número de 1s maior que o número de 0s

(#1s > #0s )

,

implica em configuração limite com formação de grupos de 1s, intercalados por

blocos 01, conforme a Figura 4.6;

0

1

52

Figura 4.6. Regra 184 em evolução temporal com condição inicial (#1s > #0s).

•

Configuração inicial com número de 0s maior que o número de 1s

(#1s < #0s)

,

implica em configuração limite com formação de grupos de 0s, intercalados por

blocos 10, conforme a Figura 4.7;

Figura 4.7. Regra 184 em evolução temporal com condição inicial (#1s < #0s).

Considerando as 3 variações de configuraçõ es limites, construiu-se manualmente

o autômato finito que reconhece a linguagem regular formada pelo comportamento

limite da regra 184 (verificar a Figura 4.8). O aut ômato finito passou a ser o grafo alvo

do algoritmo em desenvolvimento.

0

1

0

1

53

1

2

3

4

5

Figura 4.8. Grafo limite da r egra 184.

4.2.2 Grafos e a relação com diagrama espa ço temporal

Para obter o grafo limite apresentado na Figura 4.8, foi efetuada uma análise das

estruturas presentes nos grafos da regra 184. Observando os 5 grafos da Figur a 4.9 ,

podemos destacar dois pontos que aparecem em todos os instantes de te mpo, ponto A

(em cinza) e B (em vermelho). Percebe-se que no ponto A, existe uma aresta de cor

preta em

loop

, representand o uma cadeia de um ou mais caracteres 1 (exp ressão regular

1

+

). O ponto B, repre senta uma expressão regular análoga, agora considerando o

caractere 0 (expressão regular 0

+

).

54

REGRA 184

1

2

3

4

12

3

4 5

6

1

2

3

4

5

6

7

8

1

23

4

5

6

7 8

9

10

1

2

3

4

5

6

7

8

9

10

11

12

Figura 4.9. Análise de estruturas presentes nos grafos relacionados à regra 184.

Dessa forma, podemos dizer que o ponto A representa blocos de 1s e o ponto B,

blocos de 0s, visíveis em um d iagrama espaço temporal da regra 184 (verificar a Figura

4.10).

Figura 4.10. Análise do diagrama e spaço temporal da regra 184.

A

B

A

B

A

B

A

B

A

B

A

B

Ponto A – grupo de 1s

Ponto B – grupo de 0s

Distância entre grupo de 1s e grupo de 0s

Distância entre grupo de 0s e grupo de 1s

1

t=5

t = 1

t = 2

t = 3

t = 4

55

Observando as Figuras 4.9 e 4.10, podemos relacionar estruturas dos grafos, com

o diagrama da evolução temporal da regra 184. A Fi gura 4.9 destaca em azul o caminho

necessário a ser percor rido para conectar o ponto B ao ponto A, ou seja, bloco de 0s ao

bloco de 1s. Pelos 5 grafos, observe-se que a conexão entre os pontos é imediata, ou

seja, a qualquer instante de tempo finito , poderão aparecer cadeias de 0s seguido s de

cadeias de 1s (expressão regular 0

+

1

+

). Essa informação pode ser confirmada n a Figura

4.10, d estacad a também em azul.

A Figura 4.9 destaca em verde o caminho necessário a ser percorrido para

conectar o ponto A ao ponto B, ou seja, bloco de 1s ao bloco de 0s. Observe pelos 5

grafos, que a distância de conexão entre os pontos aumenta a cada instante de t empo, e

já no primeiro instante (t=1), uma seqüên cia de caracteres alternados 01 deve ser

percorrida; ou seja, da segunda linha (t=1) em diante da Figura 4.10 não é possível

visualizar grupos de 1s junto com grupos de 0s, e a seqüência de blocos alternadas de 01

aumenta a cada instante de tempo, separando os dois grupos (ponto A e B).

Pelo fato dos grafos da regra 184 não serem simétricos, o diagrama espaço

temporal da regra 184 poderá apresentar bloco de 0s segui do de bloco de 1s, porém

nunca apresen tará bloco d e 1s junto com bloco de 0s. Mas como o grafo limite da regra

184 é simétrico, quando a evolução temp oral ati nge o comportamento limite (t tende a

infinito), o diagrama n ã o apresentará bloco de 0s seguido de bloco de 1s e vice-versa.

Essas associações permitiram compreender porque a regra 184, para cada instante

definido de tempo, apresenta aumento da com plexidade dos grafos em evolução. A

transformação necessária do grafo não simétrico para um grafo simétrico (quando atinge

a condição limite), foi uma d as grandes difi culda des encontradas no desenvolvimento

do proces so.

4.2.3 Componentes do comportamento limite

Após a análise do comportam ento dinâmico dos grafos em evolução da regra

184, procurou-se observar os resultados d o módulo de análise e criar ass ociações para

obter o grafo limite d a Figura 4 .8.

O resultado da operação de diferença de grafos permitiu identificar que uma

estrutura é adicionada e outra excluída de forma rep etitiva, a cada passo tem poral (v er

Figura 4.11). A estrutura adicional está relacionada à seqüência alternada d e blocos 01

56

que separam o bloco de 1s do bloco de 0s, explicada na seção anterior. A estrutura

eliminada está relacionada à transformação que o grafo sofre, para encaixe da estrut ura

adicional ao novo instante de tempo.

Intuitiv amente a informação que compõe o grafo limite parece estar no grafo

referente ao instante de tempo que antecede o início da repetição, e o resultado da

operação de diferença de grafos (estru tura adicionada e estrut ura excluída).

Estrutura adicio nada Estrutura excluída

Figura 4.11. Resultados da operação de diferença de grafos.

Como o ciclo d e repetição identificado inicia-se na primeira aplicação da

operação de diferença, en tre os instantes t=1 e t= 2, a operação ‘alvo’ não desenvolvida

neste trab alho receberia os parâmetros ilustrados na Figura 4.12 para a regra 184.

Figura 4.12. Ilustração da operação de obtenção do grafo limite para a regra 184.

A dificuldade na geração dessa operação foi encontrar uma lógica de asso ciação

entre esses componentes, e obter o grafo limi te. Se analisarmos o primeiro parâmetro da

operação representado pelo grafo t=1, verificamos a presença dos pontos A e B,

ilustrados na Figura 4.9, que são informações referentes a blocos de 0s e bloco s de 1s,

presentes em todos os grafos da regra 184. De fato, os pontos A e B também aparecem

no grafo l imite, com a diferença de que estão locali zados em nós qu e nunca se

encontram (nós 2 e 5). Se afirmarm os qu e o segundo e o terceiro parâmetros indicam

OPERA

ÇÃ

O

57

que a cada passo t emporal uma estru tura é i nserida repetidamente do ponto A para o

ponto B, para o tempo tendendo a infinito, o ponto A p assará a não possuir conexão

direta com o ponto B. Porém, faltou alguma informação o u associação que possibilitasse

afirmar o contrário, já que no grafo limite, o ponto B tamb ém não po ssui conexão com o

ponto A. Seguind o essa linha de raciocínio, e trabal hando com esses componentes é que

se tento u obter o al goritmo que gerasse o grafo limite.

58

Capítulo 5

Conclusão

5.1 Introdução

Como já citado, o presente trabalho é uma cont inuidade à pes quisa iniciada em

[Trafaniuc, 2004] e, dessa forma, foi uti lizad o o recurso de análise da complexidade de

grafos correspondente a configura ções de autômatos celulares elementa res. A utilização

desta abordagem permite efetuar visualmente associações da evolução d os autômatos

finitos relacionados a configurações celulares ao longo de um período, com

características presentes no comportamento dinâmi co de regras elementares.

O objetivo desta pesquisa teve como foco a automatização de processos para

caracterização de regras de autômatos celulares elementares. Es sa caracterização

compreendia desde dados como a expressão de cres cimento, até o autômato finito

correspondente a configuração limite de autômato celular.

Todo o desenvolvimento foi conduzido com o software

Mathematica

versão 5.1,

[Wolfram, 2006], pela facilidade que apresenta na manipulação de grafos e autô matos

celulares. Em muitos experimentos foi utilizada a biblioteca

Automata Package

versão

5.0, des envolvida por Klaus Sutner [2006].

O desenv olvimento principal foi dividido em dois m ódulos: módulo de geração e

armazenamento de dados e o módulo de análise de resultados. O primeiro mó dulo

utiliza as mesmas funç ões NetCAStep, TrimNet e MinNet [Wolfram, 2002], utilizadas

por [Trafaniuc, 2004]. Porém, além dos grafos para cada instante de tempo e das

estruturas comuns presentes em grafos de tempos consecutivos, foi desenvolvido neste

módulo uma operação de diferença entre grafos, conforme apresentado na Seção 4.1 .2.

Através desta operação, foi possível observar de outra maneira o comportamento

dinâmico das regras, durante a geração de grafos referentes a tempos consecutivos e,

por cons eqüência, a obt enção de alguns resultados que preencheram a tabela de

complexidade das linguagens regulares [Wolfram, 1994] que ai nda estavam vagos em

[Trafaniuc, 2004] (ver Seção 5.2).

59

O segun do módulo, responsável pela anál ise de resultados, foi desenvo lvido para

computar os dados coletados pelo primeiro módulo, e extrair informações do

crescimento do autômato finito que reconhece a co nfiguração limite de um autômato

celular. Esse módulo foi parcialmente co nstruído, dado que o algoritmo para ob tenção

do autô mato finito referente à co nfiguração limite, não pôde ser concebido .

5.2 Detalhamento dos Resultados

As mesm as 26 regras elementares (11, 14, 23, 35, 43, 50, 56, 70, 81, 98, 11 3,

128, 132, 1 36, 14 0, 142, 162, 168, 17 2, 176 , 184, 192, 196, 212, 224 e 232) que

apresentaram máximo subgrafo comum para passos de tempos consecutivos de

autômatos fini tos, anali sadas manualmente em [Trafaniuc, 2004], foram submetidas aos

módulos de geração e análise. A implementação da operação de diferença, já

mencionada, permitiu ao módulo extrair informações importantes ao crescimento dos

grafos. Pôde-s e detectar, por exemplo, estruturas adicionais repetitivas ao crescimento ,

o ciclo de aparição dessas estruturas e o instante em que o ciclo de repetição se inicia. O

resultado da análise de crescimento das 26 regras, com todas as informações o btidas

pelo m ódulo, pode ser verificado no Apêndice A.3.

Como resultado o módulo indi cou que 23 regras apresentaram crescime nto

linear na complexidade dos autômatos finitos, con forme detalhado a seguir:

1. Crescimento linear des de o p rimeiro instante de tempo

17 regras (23, 43, 113, 128, 132, 136, 140, 142, 162, 168, 176, 184, 192, 196,

212, 224 e 232) apresentaram cres cimento linear na comp lexi dade do autômato

finito, desde o p rimeiro instante de tempo. A Figura 5 .1 ilus tra a regra elementar

43.

REGRA ELEMENTAR 43

Grafo em Evolução

GRAFO T COMUM GRAFO T+1 ESTR.ADIC. ESTR.EXCLUÍDA

60

1

2

3

4

5

6

7

8

1

2

3

4

5

6

7

8

1

2

3

4

5

6

7

8

9

10

11

12

1

2

3

4

5

6

7

8

9

10

11

12

1

2

3

4

5

6

7

8

1

2

3

4

5

6

7

8

9

10

11

12

1

2

3

4

5

6

7

8

9

10

11

12

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

1

2

3

4

5

6

7

8

9

10

11

12

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

1

2

3

4

5

6

7

8

9

0

11

12

13

14

15

16

17

18

19

20

1

2

3

4

5

6

7

8

9

0

1

12

13

14

15

16

17

18

19

20

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

1

2

3

4

5

6

7

8

9

0

11

12

13

14

15

16

17

18

19

20

1

2

3

4

5

6

7

8

9

0

11

12

13

14

15

16

17

18

19

20

1

2

3

4

5

6

7

8

9

10

1

2

3

14

15

16

17

18

19

20

21

22

23

24

1

2

3

4

5

6

7

8

9

10

1

2

3

14

15

16

17

18

19

20

21

22

23

24

1

2

3

4

5

6

7

8

9

0

11

12

13

14

15

16

17

18

19

20

1

2

3

4

5

6

7

8

9

10

1

2

3

14

15

16

17

18

19

20

21

22

23

24

1

2

3

4

5

6

7

8

9

10

1

2

3

14

15

16

17

18

19

20

21

22

23

24

1

2

3

4

5

6

7

8

9

10

11

12

3

4

5

16

17

18

19

20

21

22

23

24

25

26

27

28

1

2

3

4

5

6

7

8

9

10

11

12

3

4

5

16

17

18

19

20

21

22

23

24

25

26

27

28

1

2

3

4

5

6

7

8

9

10

1

2

3

14

15

16

17

18

19

20

21

22

23

24

1

2

3

4

5

6

7

8

9

10

11

12

3

4

5

16

17

18

19

20

21

22

23

24

25

26

27

28

1

2

3

4

5

6

7

8

9

10

11

12

3

4

5

16

17

18

19

20

21

22

23

24

25

26

27

28

1

2

3

4

5

6

7

8

9

10

11

12

13

14

5

6

7

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

1

2

3

4

5

6

7

8

9

10

11

12

13

14

5

6

7

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

1

2

3

4

5

6

7

8

9

10

11

12

3

4

5

16

17

18

19

20

21

22

23

24

25

26

27

28

61

1

2

3

4

5

6

7

8

9

10

11

12

13

14

5

6

7

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

1

2

3

4

5

6

7

8

9

10

11

12

13

14

5

6

7

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

7

8

9

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

6

7

8

9

0

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

1

2

3

4

5

6

7

8

9

10

11

12

13

14

5

6

7

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

Análise do Crescimento

- Crescim en to Linear: Sim

- Express ao de Crescimento Nó: 4 (1+t) Iníc io em t= 1

- Expres sao de Crescimento Aresta: 8+6 t Início em t= 1

Estrutura Repetitiva

1

2

3

4

5

6

7

8

9

10

Análise do Ciclo das Estruturas Repetitivas

- Estrutu ra 1 => Ciclo: 1 Inicio e m t = 2

Figura 5.1. Resultados da regra ele mentar 43 com crescimento linear desde o primeiro

instante de tempo.

Observe que visualizando apenas as colunas grafo t, comum e grafo t+1,

exibidas em [Trafaniuc, 200 4] fica difícil o bservar que a regra possui

crescimento linear. Através das colunas estrutura adicionada e ex c luída

implementad as neste trab a lho, torna-se mais fácil essa percepção, uma vez

detectado que sempre a mesma estrutura é adicionada e excluída do grafo para

todos os instantes de tempo executado. Na análi se automática executada pelo

módulo, a informação de repetição e crescimento linear p ode s er confirmada

pelo item ‘Análise de Ciclo’ da Figura 5. 1, onde a regra 43 apresenta uma única

estrutura repetitiva que se apresenta com ciclo=1 e início em t=2.

62

2. Crescimento linear após o primeiro instante de tempo

03 regras (56, 98 e 172) apresen taram crescimento li near na complexidade do

autômato finit o, após o primeiro instante de tempo. A Figura 5.2 ilus tra a regra

elementar 56.

REGRA ELEMENTAR 56

Grafo em Evolução

GRAFO T COMUM GRAFO T +1 ESTR.ADIC. ESTR.EXCLUÍDA

1

2

3

1

2

3

1

2

3

4

1

2

3

4

1

2

3

1

2

3

4

1

2

3

4

12

3

4

5

6

12

3

4

5

6

1

2

3

4

12

3

4

5

6

1

2

3

4

5

6

1

2

3

4

5

6

7

8

1

2

3

4

5

6

7

8

12

3

4

5

6

1

2

3

4

5

6

7

8

1

23

4

5

6

7

8

1

23

4

5

6

7

8

9

10

1

23

4

5

6

7

8

9

10

1

2

3

4

5

6

7

8

1

23

4

5

6

7

8

9

10

1

2

3

4

5

6

7

8

9

10

1

2

3

4

5

6

7

8

9

10

11

12

1

2

3

4

5

6

7

8

9

10

11

12

1

23

4

5

6

7

8

9

10

63

1

2

3

4

5

6

7

8

9

10

11

12

1

2

34

5

6

7

8

9

10

11

12

1

2

34

5

6

7

8

9

10

11

12

13

14

1

2

34

5

6

7

8

9

10

11

12

13

14

1

2

3

4

5

6

7

8

9

10

11

12

1

2

34

5

6

7

8

9

10

11

12

13

14

1

2

3

4

5

6

7

8

9

10

11

12

13

14

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

1

2

34

5

6

7

8

9

10

11

12

13

14

Análise do Crescimento

- Crescim en to Linear: Sim

- Expres sao de Crescimento Nó: 2 t Início em t= 2

- Expres sao de Crescimento Aresta: 3 t Iníc io em t= 2

Estrutura Repetitiva

1

2

3

12

3

4

5

Análise do Ciclo das Estruturas Repetitivas

- Estrutu ra 1 => Ciclo: 0 Inicio e m t = 2

- Estrut ura 2 => Ciclo: 1 Inicio e m t = 3

Figura 5.2. Resultados da regra ele mentar 56 com crescimento linear desde o segundo

instante de tempo.

Essas regras (que exibem crescimento linear após o pri meiro instante de tempo)

apresentam maio r dificuldade ainda para detecção do crescimento linear, sem

utilização dos grafos de diferença. A Figura 5.2 mo stra que a regra elementar 56

possui crescimento linear de nós e arestas do segundo instante de t emp o em

diante, e que, entre a iteração dos grafos de t=1 para t=2, a estrutura repetitiva 1

é apresentada uma única vez. Já a estrutura repetitiva 2, que se repete entre a

iteração t = 2 para t=3 em diante, inclui a característica de linearidade no

crescimento.

64

3. Crescimento linear e estruturas repetitivas com ciclo duplo

2 regras (50 e 70), mesmo com estru turas adicionais repetitiv as a cada dois

instantes de tempo (ciclo= 2), apresentaram crescimento linear do número de nó s

e arestas.

REGRA ELEMENTAR 50

Grafo em Evolução

GRAFO T COMUM GRAFO T +1 ESTR.ADIC. ESTR.EXCLUÍDA

1

2

3

1

2

3

1

2

3

4

5

6

7

1

2

3

4

5

6

7

1

2

3

1

2

3

4

5

6

7

1

2

3

4

5

6

7

1

2

3

4

5

6

7

8

9

1

2

3

4

5

6

7

8

9

1

2

3

4

5

6

7

1

2

3

4

5

6

7

8

9

1

2

3

4

5

6

7

8

9

1

2

3

4

5

6

7

8

9

10

11

1

2

3

4

5

6

7

8

9

10

11

1

2

3

4

5

6

7

8

9

1

2

3

4

5

6

7

8

9

10

11

1

2

3

4

5

6

7

8

9

10

11

1

2

3

4

5

6

7

8

9

10

11

12

13

1

2

3

4

5

6

7

8

9

10

11

12

13

1

2

3

4

5

6

7

8

9

10

11

65

1

2

3

4

5

6

7

8

9

10

11

12

13

1

2

3

4

5

6

7

8

9

10

11

12

13

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

1

2

3

4

5

6

7

8

9

10

11

12

13

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

1

2

3

4

5

6

7

8

9

0

11

12

13

14

15

16

17

18

19

1

2

3

4

5

6

7

8

9

0

11

12

13

14

15

16

17

18

19

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

Análise do Crescimento

- Crescim en to Linear: Sim

- Expres sao de Crescimento Nó: 3+2 t Início em t= 2

-

Expressao de Crescimento Aresta: 3 (2+t) Início em t=

2

Estrutura Repetitiva

1

2

3

4

5

6

7

1

2

3

4

5

6

7

1

2

3

4

5

6

Análise do Ciclo das Estruturas Repetitivas

- Estrutu ra 1 => Ciclo: 0 Inicio e m t = 2

- Estrut ura 2 => Ciclo: 2 Inicio e m t = 3

- Estrut ura 3 => Ciclo: 2 Inicio e m t = 4

Figura 5.3. Resultados da regra ele mentar 50 com ciclo=2 e crescimento linear .

Essas duas regras apresentam crescimento li near porque, coincidentemente, as

duas estruturas repetitivas que se intercalam na evolução, adicionam o mesmo

número de nó s e arestas em cada instante de tempo.

66

Figura 5.4. Estrutura adicionada e excluída da regra 50 com cre scimento linear.

Observe pela Figura 5.4 que o número de arestas da es trutura líquida ad icionadas

ao grafo no próximo instante de tempo é o mesmo.

4. Crescimento linear e estruturas repetitivas com ciclo zero

A regra 81 mesmo não apresentando estrutu ra adicional repetitiva (ciclo=0),

apresentou crescimen to linear do número d e nós e arestas após o instante t=3

(ver Figura 5.5).

REGRA ELEMENTAR 81

Grafo em Evolução

GRAFO T COMUM GRAFO T +1 ESTR.ADIC. ESTR.EXCLUÍDA

1

2

3

1

2

3

1

2

3

4

5

1

2

3

4

5

1

2

3

Estrutura adicionada Estrutura excluída

Estrutura adicionada

com 6 arestas e

excluída com 3, então

a estrutura liquida tem

3 arestas

Estrutura adicionada

com 5 arestas e

excluída com 2, então

a estrutura liquida tem

3 arestas

67

1

2

3

4

5

1

2

3

4

5

1

2

3

4

5

6

7

8

1

2

3

4

5

6

7

8

1

2

3

4

5

1

2

3

4

5

6

7

8

12

3

4

5

6

7

8

1

23

4

5

6

7

8

9

10

1

23

4

5

6

7

8

9

10

1

2

3

4

5

6

7

8

1

23

4

5

6

7

8

9

10

1

23

4

5

6

7

8

9

10

1

2

3

4

5

6

7

8

9

10

11

12

1

2

3

4

5

6

7

8

9

10

11

12

1

23

4

5

6

7

8

9

10

1

2

3

4

5

6

7

8

9

10

11

12

1

23

4

5

6

7

8

9

10

11

12

1

2

34

5

6

7

8

9

10

11

12

13

14

1

2

34

5

6

7

8

9

10

11

12

13

14

1

2

3

4

5

6

7

8

9

10

11

12

1

2

34

5

6

7

8

9

10

11

12

13

14

1

2

34

5

6

7

8

9

10

11

12

13

14

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

1

2

34

5

6

7

8

9

10

11

12

13

14

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

1

2

34

5

6

7

8

9

10

11

12

13

14

15

16

1

2

3

45

6

7

8

9

10

11

12

13

14

15

16

17

18

1

2

3

45

6

7

8

9

0

11

12

13

14

15

16

17

18

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

Análise do Crescimento

- Crescim en to Linear: Sim

- Expres sao de Crescimento Nó: 2 (1+t) Iníc io em t= 3

- Expres sao de Crescimento Aresta: 4+3 t Início em t= 3

68

Estrutura Repetitiva

1

2

3

4

1

2

3

4

5

6

7

1

2

3

4

5

1

2

3

4

5

1

2

3

4

5

6

1

2

3

4

5

6

1

3

4

5

6

7

Análise do Ciclo das Estruturas Repetitivas

- Estrutu ra 1 => Ciclo: 0 Inicio e m t = 2

- Estrut ura 2 => Ciclo: 0 Inicio e m t = 3

- Estrut ura 3 => Ciclo: 0 Inicio e m t = 4

- Estrut ura 4 => Ciclo: 0 Inicio e m t = 5

- Estrut ura 5 => Ciclo: 0 Inicio e m t = 6

- Estrut ura 6 => Ciclo: 0 Inicio e m t = 7

- Estrut ura 7 => Ciclo: 0 Inicio em t = 8

Figura 5.5. Resultados da regra ele mentar 81 sem estrutura repetitiva mas com

crescimento linear.

A regra 81 apresenta um comportam ento bastante interessante. Observe-se pelas

colunas estrutura adicionada e excluída na Figura 5.5 que, para os dois primeiros

instantes de tempo, os pares correspondentes d e estrutura adicionada e ret irada

aparecem uma única vez. Depoi s disso, a est rutura líquida adicionada apresenta

mesmo número de n ós e arestas, seguindo a mes ma explicação de crescim ento

linear da Figura 5.4. Uma segunda obs ervação é que analisando visualmente as

colunas estrutura adicionada e estrutura excluída, pode-se observar um

crescimento lin ear dessas estrutu ras ao longo do tempo.

Além dessas regr as com crescimento linear, o m ódulo detectou 03 regras (11, 14

e 35) que não apresentaram crescimento linea r do número de nós e arestas, porém

apresentaram estrutu ras adicionais repetitivas com ciclo dupl o. O núme ro de arestas que

varia de acordo com o instante de t empo (par e ímpar) é que impede a linearid ade no

crescimento. Essa percepção também só foi possível com a análise de ciclo e estruturas

repetitivas incluídas neste trabalho (ver Figura 5.6).

REGRA ELE ME NTA R 11

Grafo em Evolução

GRAFO T COMUM GRAFO T +1 ESTR.ADIC. ESTR.EXCLUÍDA

69

1

2

3

1

2

3

12

3

4

5

6

12

3

4

5

6

1

2

3

12

3

4

5

6

1

2

3

4

5

6

1

2

3

4

5

6

7

8

1

2

3

4

5

6

7

8

12

3

4

5

6

1

2

3

4

5

6

7

8

1

2

3

4

5

6

7

8

1

23

4

5

6

7

8

9

10

1

23

4

5

6

7

8

9

10

1

2

3

4

5

6

7

8

1

23

4

5

6

7

8

9

10

1

2

3

4

5

6

7

8

9

10

1

2

3

4

5

6

7

8

9

10

11

12

1

2

3

4

5

6

7

8

9

10

11

12

1

23

4

5

6

7

8

9

10

1

2

3

4

5

6

7

8

9

10

11

12

1

2

3

4

5

6

7

8

9

10

11

12

1

2

34

5

6

7

8

9

10

11

12

13

14

1

2

34

5

6

7

8

9

10

11

12

13

14

1

2

3

4

5

6

7

8

9

10

11

12

1

2

34

5

6

7

8

9

10

11

12

13

14

1

2

3

4

5

6

7

8

9

10

11

12

13

14

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

1

2

34

5

6

7

8

9

10

11

12

13

14

70

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

1

2

3

45

6

7

8

9

10

11

12

13

14

15

16

17

18

1

2

3

45

6

7

8

9

0

11

12

13

14

15

16

17

18

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

Análise do Crescimento

- Crescim en to Linear: Não

- Expres sao de Crescimento Nó: 2 (1+t) Iníc io em t= 2

- Expres sao de Crescimento Aresta: --- - -

Estrutura Repetitiva

1

2

3

4

5

1

2

3

4

5

1

2

3

4

Análise do Ciclo das Estruturas Repetitivas

- Estrutu ra 1 => Ciclo: 0 Inicio e m t = 2

- Estrut ura 2 => Ciclo: 2 Inicio e m t = 3

- Estrut ura 3 => Ciclo: 2 Inicio e m t = 4

Figura 5.6. Resultados da regra ele mentar 11 crescimento linear para tempo par e í mpar.

Observe que essas regras mesmo assemelhando-se a regra 50 da Figura 5.3, por

apresentarem ciclo duplo na iteração de tempo t=2 pa ra t=3 em diante, não possui

crescimento linear. Essas três regras não apresentam o crescimento linear p orque as

duas estruturas repetitivas que se intercalam na evo lução, não apresentam o mesmo

número de arestas . Porém, como essas estruturas são repetitivas e intercalam, através de

observações de grafos d essas regras, pôde-se extrair expressõ es de crescimento para

tempo par e ímpar.

Para todas as 26 regras analisadas, obteve-se uma expressão de crescimento do

número de nós e arestas do grafo em função do tempo . Dessas 26, as expressões de 06

regras (11, 14, 35, 50, 70 e 81), não haviam sido preenchidas na tabela de complexidade

das lin guagens regulares nem em [Wolfram, 1 994] nem em [Trafaniuc, 2004].

A Tabela 5.1 abai xo, ilust ra as expressões de crescim ento do núm ero de nós e

arestas ob tidas neste trabalho:

71

Numero de Nós Número de A resta

Regra

Expressão Observaçã o Expre ssão Observação

9 + 5( t/2 -1) t 2 (Par)11 2 (1+t) t 2

12+ 5/2(t-3) t 2 (Í mpar)

10 + 5(t/2 -1) t 2 (Par)14 2 (1+t) t  2

12+ 5/2(t-3) t 2 (Í mpar)

6 + 3( t/2 -1) t 2 (Par) 10 + 4(t/2 -1) t 2 (Par)35

7+3/2( t-3) t 2 (Ímpar) 11+ 2(t-3) t 2 (Í mpar)

50 3+2 t t 2 3 (2+t) t 2

70 6+t t 3 12+t t 2

81 2 (1+t) t 3 4+3 t t 3

Tabela 5.1. Ex pressões de crescimento da tabela de complexidade [W olfram, 1 994] que

permaneciam vazia

5.3 Comentários finais

Nesta pesqu isa detectou-se que a função MinNet [Wolfram, 20 02, página 957]

está com o descritivo errado no livro. Através de experimentos efetuados comprovar am

que a função retorna o últim o estado como inicial, e não o primeiro como mencionado.

Essa desvio de informação nos levou em mui tos moment os desta pesquisa a trabalhar

com alguns conceitos errados, principalmente com relação a que cada função(MinNet,

TrimNet e SetCAStep) utilizadas no processo iterativo efetua de fato. Relacionado a

esta mesma função, e talvez relacionado a esse erro de descrição, Trafaniuc [2004]

referencia em alguns pontos de sua pesquisa, de forma errada, à máquina ge rada por

esta função como semi-autômato, ao inv és de autômato finito determinístico.

As diferenças encont radas entre as t abelas de complexidade em linguagem

regular de [Wolfram, 1994 ] e [Trafaniuc, 2002], foram investigadas e podem ser

atribuídas a um possível erro ex istente no código anterior utilizado por Wolfram para

construção da tabela [1 994] e corrigid o em [2002]. A comparação de grafos da regra

108 exibidos pelo próp rio Wolfram [2002] e constatação da condição de igualdade com

dados d a tabela de [Traf aniu c, 2002], é que nos induz a acreditar nessa hipótese.

72

Todos os resultado da análise automática desenvolvida nest a pesquisa gerou

informações novas e importantes na análise de cr escimento da complexidade de

autômatos finitos, porém, a informação relativa ao comportamento limite da regra

permanece em aberto. Neste trabalho, a manipulação de grafos foi o recurso mais

utilizado e focado na tentativa de obter o autômato finito determin ístico que

representasse o comportamento limite de uma regra elementar. Em algumas situações,

tentou-se utilizar expressões regulares utilizando a biblioteca

Automata Package

para

conversão d e máquinas em expressões. Porém, es sas con versões normalmente

resultavam em expressões regulares extremamente grandes e complexas, que

impossibi litavam a associação ou desenvolvimento de algum raciocínio lógico. Outro

ponto a ser destacado, é que mesmo encontrando alguns componentes importantes na

caracterização do comportamento limi te, conforme apresent ado na Seção 4.2.3, intui-se

que ainda falta alguma informação adicional que permitirá finalizar a operação de

obtenção do co mportamento limite, para uma regra elemen tar.

73

Apêndice

A.1. Tabela de complexidade das linguagens regulares

[Wolfram, 1994].

74

75

Tabela A.1. Complexidade das linguagens regulares [Wolfram, 1994].

76

Resultados diferentes entre as duas tabelas

Novos Resultados

Regras Equivalentes já apresentadas

*

- regras válidas a partir do segundo passo de tempo

Estados Transições Estados Transições Esta dos Transições Estados Transições Estados Transições Estados Transições Estados Transições Estados Transições Estados Transições Estados Transições Estados Transições Estados Transições Estados Transições Estados Transições

0 nula 1 1 - - - - - - - - 1 1 1 1 1 1 - - - - - - - - 1 1 1 1 255

1 ciclo-duplo 4 6 - - - - - - - - 4 6 4 6 4 6 - - - - - - - - 4 6 4 6 127

2 ponto-fixo 3 4 - - - - - - - - 3 4 3 4 3 4 - - - - - - - - 3 4 3 4 16,191,247

3 ciclo-duplo 3 5 - - - - - - - - 3 5 3 5 3 5 - - - - - - - - 3 5 3 5 17,63,119

4 ponto-fixo 2 3 - - - - - - - - 2 3 2 3 2 3 - - - - - - - - 2 3 2 3 223

5 ciclo-duplo 9 15 - - - - - - - - 9 15 9 15 9 15 - - - - - - - - 9 15 9 15 95

6 ciclo-duplo 9 16 13 22 22 37 26 44 31 52 10 17 21 37 28 49 33 57 43 75 20,159,215

7 ciclo-duplo 4 7 7 12 12 21 14 24 16 27 4 7 8 14 11 19 13 22 15 25 21,31,87

8 nula 3 4 1 1 - - - - - - 1 1 1 1 3 4 1 1 - - - - - - 1 1 1 1 64,239,253

9 ciclo-duplo 9 16 22 40 44 80 106 198 266 500 9 15 20 35 36 63 67 115 213 387 65,111,125

10 ponto-fixo 4 6 - - - - - - - - 4 6 4 6 4 6 - - - - - - - - 4 6 4 6 80,175,245

11 ciclo-duplo 3 5 7 12 10 17 12 20 14 23 3 5 6 9 8 12 10 14 12 17 47,81,117

12 ponto-fixo 2 3 - - - - - - - - 2 3 2 3 2 3 - - - - - - - - 2 3 2 3 68,207,221

13 ponto-fixo 6 11 10 17 12 19 14 21 16 23 5 8 9 15 11 17 13 21 15 23 69,79,93

14 ciclo-duplo 3 5 7 12 10 17 12 20 14 23 3 5 6 10 8 12 10 15 12 17 84,143,213

15 ciclo-duplo 1 2 - - - - - - - - 1 2 1 2 1 2 - - - - - - - - 1 2 1 2 85

16 ponto-fixo 3 4 - - - - - - - - 3 4 3 4 3 4 - - - - - - - - 3 4 3 4 2,191,247

17 ciclo-duplo 3 5 - - - - - - - - 3 5 3 5 3 5 - - - - - - - - 3 5 3 5 3,63,119

18 caótica 5 9 47 91 143 270 5 9 47 91 143 270 183

19 ciclo-duplo 3 5 5 8 - - - - - - 5 8 5 8 3 5 4 6 - - - - - - 5 8 5 8 55

20 ciclo-duplo 10 17 21 37 32 57 37 65 50 89 9 16 13 22 22 37 26 44 31 52 6,159,215

21 ciclo-duplo 4 7 9 16 12 21 14 24 16 27 4 7 7 12 11 19 13 22 15 25 7,31,87

22 caótica 15 29 280 551 4506 8963 15 29 274 539 151

23 ciclo-duplo 11 20 15 26 19 32 23 38 27 44 10 18 14 24 18 30 22 36 26 42 -

24 ponto-fixo 2 3 3 4 - - - - - - 3 4 3 4 2 3 3 4 - - - - - - 3 4 3 4 66,189,231

25 ciclo-duplo 6 11 26 50 55 106 114 220 333 649 5 9 16 30 35 66 82 154 169 318 61,67,103

26 periódica 13 25 92 179 2238 4454 82,167,181

27 ciclo-duplo 10 18 14 25 18 32 21 37 24 42 9 16 14 23 16 26 20 31 22 34 39,53,83

28 ciclo-duplo 3 5 8 14 10 17 11 18 12 19 3 5 7 12 8 13 10 17 - - 10 17 10 17 70,157,199

29 ciclo-duplo 4 7 - - - - - - - - 4 7 4 7 4 7 - - - - - - - - 4 7 4 7 71

30 caótica 1 2 - - - - - - - - 1 2 1 2 1 2 - - - - - - - - 1 2 1 2 86,135,149

32 nula 2 3 5 7 7 9 9 11 11 13 2t+1 2t+3 4 6 2 3 5 7 7 9 9 11 11 13 (2t+1) (2t+3) 4 6 251

33 ciclo-duplo 5 9 11 20 26 47 40 68 41 68 5 9 11 20 21 37 35 58 36 58 123

34 ponto-fixo 2 3 - - - - - - - - 2 3 2 3 2 3 - - - - - - - - 2 3 2 3 48,187,243

35 ciclo-duplo 4 7 7 13 9 16 10 18 12 21 4 7 6 10 7 11 9 14 10 15 49,59,115

36 ponto-fixo 3 5 3 4 - - - - - - 3 4 3 4 3 5 3 4 - - - - - - 3 4 3 4 219

37 ciclo-duplo 15 29 15 29 91

38 ciclo-duplo 5 9 5 8 - - - - - - 5 8 5 8 5 9 5 8 - - - - - - 5 8 5 8 52,155,211

40 nula 10 17 12 19 15 22 18 25 21 28 9 16 11 17 14 20 17 23 20 26 96,235,249

41 periódica 14 27 128 250 1049 2069 14 27 94 185 97,107,121

42 ponto-fixo 3 5 - - - - - - - - 3 5 3 5 3 5 - - - - - - - - 3 5 3 5 112,171,241

43 ciclo-duplo 9 16 13 22 17 28 21 34 25 40 8 14 12 20 16 26 20 32 24 38 (4t +4) (6t+8) 113

44 ponto-fixo 4 7 11 20 18 32 23 40 27 46 5 9 11 19 15 25 16 25 20 30 100,203,217

45 caótica 1 2 - - - - - - - - 1 2 1 2 1 2 - - - - - - - - 1 2 1 2 75,89,101

46 ponto-fixo 3 5 5 8 - - - - - - 5 8 5 8 3 5 116,139,209

Regras

Equivalentes

REGRA CLASSE

Tabela Wolfram 1986 Nova Tabela Utilizando as funções do NKS

t=1 t=2 t=3 t=4 t=5 t>5 Infinito t=1 t=2 Infinitot=3 t=4 t=5 t>5

A.2. Tabela de complexidade das linguagens regulares [Trafaniuc, 2004].

77

Resultados diferentes entre as duas tabelas

Novos Resultados

Regras Equivalentes já apresentadas

*

- regras válidas a partir do segundo passo de tempo

Estados Transições Estados Transições Estados Transições Estados Transições Estados Transições Estados Transições Estados Transições Estados Transições Estados Transições Estados Transições Estados Transições Estados Transições Estados Transições Estados Transiçõe s

48 ponto-fixo 2 3 - - - - - - - - 2 3 2 3 2 3 - - - - - - - - 2 3 2 3 34,187,243

49 ciclo-duplo 4 7 6 10 7 11 9 14 10 15 4 7 6 11 8 14 9 16 11 19 35,59,115

50 ciclo-duplo 3 5 8 14 10 17 12 20 14 23 3 5 7 12 9 15 11 18 13 21 179

51 ciclo-duplo 1 2 - - - - - - - - 1 2 1 2 1 2 - - - - - - - - 1 2 1 2 -

52 ciclo-duplo 4 7 5 9 - - - - - - 5 9 5 9 5 9 5 8 - - - - - - 5 8 5 8 38,155,211

53 ciclo-duplo 10 18 15 25 17 28 21 33 23 36 8 14 11 19 14 24 17 29 20 34 27,39,83

54 complexa 9 16 17 32 94 179 675 1316 8 14 16 30 93 177 147

56 ponto-fixo 3 5 5 9 7 12 9 15 11 18 3 5 4 6 6 9 8 12 10 15 (2t)* (3t)* 98,185,227

57 ponto-fixo 11 20 15 27 15 26 24 42 32 55 10 18 14 25 13 22 21 36 28 47 99

58 ponto-fixo 10 18 20 35 33 55 55 88 76 122 8 14 16 27 29 48 44 70 63 97 114,163,177

60 caótica 1 2 - - - - - - - - 1 2 1 2 1 2 - - - - - - - - 1 2 1 2 102,153,195

61 ciclo-duplo 5 9 16 30 10 76 94 177 185 350 6 11 26 50 53 102 112 216 327 637 25,67,103

62 periódica 5 9 21 39 61 114 81 150 129 240 5 9 14 25 41 76 70 131 79 143 118,131,145

64 nula 3 4 1 1 - - - - - - 1 1 1 1 3 4 1 1 - - - - - - 1 1 1 1 8,239,253

65 ciclo-duplo 9 15 20 35 42 75 88 157 220 401 9 16 22 40 42 76 104 194 261 490 9,239,253

66 ponto-fixo 2 3 3 4 - - - - - - 3 4 3 4 2 3 3 4 - - - - - - 3 4 3 4 24,189,231

68 ponto-fixo 2 3 - - - - - - - - 2 3 2 3 2 3 - - - - - - - - 2 3 2 3 12,207,221

69 ponto-fixo 5 8 10 17 12 19 14 23 16 25 5 9 9 15 11 17 13 19 15 21 13,79,93

70 ciclo-duplo 3 5 8 14 9 15 11 19 11 19 3 5 7 12 9 15 10 16 11 17 28,157,199

72 ponto-fixo 5 9 5 8 - - - - - - 5 8 5 8 5 9 3 4 - - - - - - 3 4 3 4 237

73 caótica 15 29 82 155 390 757 1443 2796 15 29 75 141 109

74 ciclo-duplo 13 25 45 85 66 123 69 125 75 135 13 25 88,173,229

76 ponto-fixo 3 5 - - - - - - - - 3 5 3 5 3 5 - - - - - - - - 3 5 3 5 205

77 ponto-fixo 11 20 15 26 19 32 23 38 27 44 10 18 14 24 18 30 22 36 26 42 -

78 ponto-fixo 10 18 15 27 18 30 20 34 22 36 9 16 13 21 17 27 17 25 21 31 92,141,197

80 ponto-fixo 4 6 - - - - - - - - 4 6 4 6 4 6 - - - - - - - - 4 6 4 6 10,175,245

81 ciclo-duplo 3 5 7 11 9 14 11 16 13 19 3 5 5 8 8 13 10 16 12 19 11,47,117

82 periódica 13 25 167 331 3134 6257 13 25 92 179 26,167,181

84 ciclo-duplo 3 5 7 12 9 14 11 17 13 19 3 5 5 8 8 13 10 16 12 19 14,143,213

85 ciclo-duplo 1 2 - - - - - - - - 1 2 1 2 1 2 - - - - - - - - 1 2 1 2 15

86 caótica 1 2 - - - - - - - - 1 2 1 2 1 2 - - - - - - - - 1 2 1 2 30,135,149

88 ciclo-duplo 13 25 63 117 114 210 117 213 1288 2106 13 25 42 79 62 115 65 117 71 127 74,173,229

89 caótica 1 2 - - - - - - - - 1 2 1 2 1 2 - - - - - - - - 1 2 1 2 45,75,101

90 caótica 1 2 - - - - - - - - 1 2 1 2 1 2 - - - - - - - - 1 2 1 2 165

92 ponto-fixo 10 18 14 23 18 29 18 27 22 33 8 14 12 21 15 24 17 28 19 30 78,141,197

94 periódica 15 29 230 455 3904 7760 15 29 230 455 133

96 nula 9 16 11 17 14 20 17 23 20 26 10 16 12 19 15 22 18 25 21 28 40,235,249

97 periódica 14 27 99 195 626 1237 14 27 128 250 41,107,121

98 ponto-fixo 3 5 4 6 6 9 8 12 10 15 3 5 4 7 6 10 8 13 10 16 (2t)* (3t+1)* 56,185,227

100 ponto-fixo 5 9 11 19 17 29 18 29 22 34 4 7 7 12 14 24 18 30 22 36 44,203,217

102 caótica 1 2 - - - - - - - - 1 2 1 2 1 2 - - - - - - - - 1 2 1 2 60,153,195

104 ponto-fixo 15 29 265 525 2340 4647 1394 2675 1542 2913 15 29 265 525 233

105 caótica 1 2 - - - - - - - - 1 2 1 2 1 2 - - - - - - - - 1 2 1 2 -

106 caótica 1 2 - - - - - - - - 1 2 1 2 1 2 - - - - - - - - 1 2 1 2 120,169,225

108 ciclo-duplo 9 16 11 19 - - - - - - 11 19 11 19 8 14 8 13 - - - - - - 8 13 8 13 201

Regras

Equivalentes

REGRA CLASSE

Tabela Wolfram 1986 Nova Tabela Utilizando as funções do NKS

t=1 t=2 t=3 t=4 t=5 t>5 Infinito t=1 t=2 Infinitot=3 t=4 t=5 t >5

78

Resultados diferentes entre as duas tabelas

Novos Resultados

Regras Equivalentes já apresentadas

*

- regras válidas a partir do segundo passo de tempo

Estados Transições Estados Transiçõ es Estados Transições Estados Transições Estados Transições Estados Transições Estados Transições Estados Transições Estados Transições Estados Transições Estado s Transiçõ es Estados Transições Estados Transições Estados Transições

110 complexa 5 9 20 38 160 312 1035 2037 5 9 20 38 124,137,193

112 ponto-fixo 3 5 - - - - - - - - 3 5 3 5 3 5 - - - - - - - - 3 5 3 5 42,171,241

113 ciclo-duplo 9 16 13 2 2 17 28 21 34 25 40 8 14 12 20 16 26 20 32 24 38 (4t+4) (6t+8) 43

114 ponto-fixo 10 18 20 35 33 56 50 82 72 115 9 16 19 33 32 53 54 86 75 120 58,163,177

116 ponto-fixo 3 5 5 8 - - - - - - 5 8 5 8 3 5 3 4 - - - - - - 3 4 3 4 46,139,209

118 periódica 5 9 16 29 49 92 7 4 139 95 175 5 9 19 35 59 110 79 146 122 226 62,131,145

120 caótica 1 2 - - - - - - - - 1 2 1 2 1 2 - - - - - - - - 1 2 1 2 106,169,225

122 caótica 15 29 179 347 5088 9933 15 29 161

124 complexa 5 9 20 38 208 407 1356 2672 5 9 20 38 110,137,193

126 caótica 3 5 13 23 107 198 2867 5476 3 5 13 23 106 196 129

128 nula 4 6 6 8 8 10 10 12 12 14 (2t+2) (2t+4) 3 5 4 6 6 8 8 10 10 12 12 14 (2t+2) (2t+4) 3 5 254

130 ponto-fixo 9 15 14 21 18 25 22 29 26 33 9 16 13 22 17 28 21 34 25 40 144,190,246

132 ponto-fixo 5 9 7 12 9 15 11 18 13 21 5 9 7 12 9 15 11 18 13 21 (2t+3) (3t+6) 222

134 ciclo-duplo 14 27 44 82 99 182 125 224 14 27 64 119 109 201 178 327 182 324 148,158,214

136 nula 3 5 4 6 5 7 6 8 7 9 (t+2) (t+4) 3 5 3 5 4 6 5 7 6 8 7 9 (t+2) (t+4) 3 5 192,238,252

138 ponto-fixo 3 5 - - - - - - - - 3 5 3 5 3 5 - - - - - - - - 3 5 3 5 174,208,244

140 ponto-fixo 4 7 5 9 6 11 7 13 8 15 4 7 5 8 6 9 7 10 8 11 (t+3) (t+6) 196,206,220

142 ciclo-duplo 9 16 13 2 2 17 28 21 34 25 40 8 14 12 20 16 26 20 32 24 38 (4t+4) (6t+8) 212

144 ponto-fixo 9 16 16 28 20 34 24 40 28 46 9 15 14 21 18 25 22 29 26 33 130,190,246

146 caótica 15 29 92 177 1587 3126 15 29 92 177 182

148 ciclo-duplo 14 27 68 127 113 209 188 347 14 27 44 82 99 182 125 224 159 282 134,158,214

150 caótica 1 2 - - - - - - - - 1 2 1 2 1 2 - - - - - - - - 1 2 1 2 -

152 ponto-fixo 6 11 20 37 30 55 32 59 36 65 5 9 14 25 21 36 25 43 33 56 188,194,230

154 periódica 1 2 - - - - - - - - 1 2 1 2 1 2 - - - - - - - - 1 2 1 2 166,180,210

156 ciclo-duplo 11 20 20 35 24 42 28 47 34 58 10 18 19 33 23 40 27 45 33 56 198

160 nula 9 15 16 24 25 35 36 48 49 63 (t+2)^2

(t+2)(t+4)

9 15 9 15 16 24 25 35 36 48 49 63 (t+2)^2

(t+2)(t+4)

9 15 250

162 ponto-fixo 5 8 7 10 9 12 11 14 13 16 5 8 7 10 9 12 11 14 13 16 (2t+3) (3t+6) 176,186,242

164 ponto-fixo 15 29 116 227 667 1310 1214 2363 15 29 116 227 667 1310 1214 2363 218

168 nula 4 7 5 8 6 9 7 10 8 11 t+3 t+6 3 5 4 7 5 8 6 9 7 10 8 11 (t+3) (t+6 ) 3 5 224,234,248

170 ponto-fixo 1 2 - - - - - - - - 1 2 1 2 1 2 - - - - - - - - 1 2 1 2 240

172 ponto-fixo 10 18 11 20 12 22 13 24 14 26 8 14 11 19 12 20 13 21 14 22 (t+9)* (t+17)* 202,216,228

176 ponto-fixo 6 11 8 14 10 17 12 20 14 23 5 8 7 10 9 12 11 14 13 16 (2t+3 ) (2t+6) 162,186,242

178 ciclo-duplo 11 20 15 26 19 32 23 38 27 44 10 18 14 24 18 30 22 36 26 42 -

180 periódica 1 2 - - - - - - - - 1 2 1 2 1 2 - - - - - - - - 1 2 1 2 154,166,210

184 ponto-fixo 4 7 6 10 8 13 10 16 12 19 4 7 6 10 8 13 10 16 12 19 (2t+2) (3t+4) 226

188 ponto-fixo 5 9 14 25 21 36 25 43 33 55 6 11 20 37 30 55 29 53 33 59 152,194,230

192 nula 3 5 4 6 5 7 6 8 7 9 3 5 4 6 5 7 6 8 7 9 (t+2) (t+4) 136,238,252

196 ponto-fixo 4 7 5 8 6 9 7 10 8 11 4 7 5 8 6 9 7 10 8 11 (t+3) (2t+5) 140,206,220

200 ponto-fixo 3 5 - - - - - - - - 3 5 3 5 3 5 - - - - - - - - 3 5 3 5 236

204 ponto-fixo 1 2 - - - - - - - - 1 2 1 2 1 2 - - - - - - - - 1 2 1 2 -

208 ponto-fixo 3 5 - - - - - - - - 3 5 3 5 3 5 - - - - - - - - 3 5 3 5 138,174,244

212 ciclo-duplo 9 16 13 2 2 17 28 21 34 25 40 8 14 12 20 16 26 20 32 24 38 (4t+4) (6t+8) 142

216 ponto-fixo 10 18 11 19 12 20 13 21 14 22 9 16 10 18 11 20 12 22 13 24 172,202,228

224 nula 4 7 5 8 6 9 7 10 8 11 t+3 t+6 3 5 4 7 5 8 6 9 7 10 8 11 (t+3) (t+6 ) 3 5 168,234,248

232 ponto-fixo 11 20 15 26 19 32 23 38 27 44 10 18 14 24 18 30 22 36 26 42 (4t+6) (6t+12) -

240 ponto-fixo 1 2 - - - - - - - - 1 2 1 2 1 2 - - - - - - - - 1 2 1 2 170

t=3 t=4 t=5 t>5 Infinitot>5 Infinito t=1 t=2

Regras

Equivalentes

REGRA CLASSE

Complexidade das linguagens regulares[Wolfram 1994] Funções NetCAStep, TrimNet e MinNet

t=1 t=2 t=3 t=4 t= 5

Tabela A.2. Tabela que demonstra a complexidade da s linguagens regulares, retirada do trabalho de pesquisa [Trafaniuc, 2004].

79

A.3. Resultado da análise au tomática de crescimento

Segue ab aixo , a exibição da análise de resultado automática emitida pelo módulo de

análise, para as 26 regras, com 8 iterações.

* * * * * MODULO DE ANALISE * * * * *

REGRA ELE ME NTA R 11

Grafo em Evolução

GRAFO T COMUM GRAFO T +1 ESTR.ADIC. ESTR.EXCLUÍDA

1

2

3

1

2

3

12

3

4

5

6

12

3

4

5

6

1

2

3

12

3

4

5

6

1

2

3

4

5

6

1

2

3

4

5

6

7

8

1

2

3

4

5

6

7

8

12

3

4

5

6

1

2

3

4

5

6

7

8

1

2

3

4

5

6

7

8

1

23

4

5

6

7

8

9

10

1

23

4

5

6

7

8

9

10

1

2

3

4

5

6

7

8

1

23

4

5

6

7

8

9

10

1

2

3

4

5

6

7

8

9

10

1

2

3

4

5

6

7

8

9

10

11

12

1

2

3

4

5

6

7

8

9

10

11

12

1

23

4

5

6

7

8

9

10

80

1

2

3

4

5

6

7

8

9

10

11

12

1

2

3

4

5

6

7

8

9

10

11

12

1

2

34

5

6

7

8

9

10

11

12

13

14

1

2

34

5

6

7

8

9

10

11

12

13

14

1

2

3

4

5

6

7

8

9

10

11

12

1

2

34

5

6

7

8

9

10

11

12

13

14

1

2

3

4

5

6

7

8

9

10

11

12

13

14

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

1

2

34

5

6

7

8

9

10

11

12

13

14

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

1

2

3

45

6

7

8

9

10

11

12

13

14

15

16

17

18

1

2

3

45

6

7

8

9

0

11

12

13

14

15

16

17

18

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

Análise do Crescimento

- Crescim en to Linear: Não

- Expres sao de Crescimento Nó: 2 (1+t) Iníc io em t= 2

- Expres sao de Crescimento Aresta: --- - -

Estrutura Repetitiva

1

2

3

4

5

1

2

3

4

5

1

2

3

4

Análise do Ciclo das Estruturas Repetitivas

- Estrutu ra 1 => Ciclo: 0 Inicio e m t = 2

- Estrut ura 2 => Ciclo: 2 Inicio e m t = 3

- Estrut ura 3 => Ciclo: 2 Inicio e m t = 4

REGRA ELE ME NTA R 14

Grafo em Evolução

GRAFO T COMUM GRAFO T +1 ESTR.ADIC. ESTR.EXCLUÍDA

81

1

2

3

1

2

3

12

3

4

5

6

12

3

4

5

6

1

2

3

12

3

4

5

6

1

2

3

4

5

6

1

2

3

4

5

6

7

8

1

2

3

4

5

6

7

8

12

3

4

5

6

1

2

3

4

5

6

7

8

1

2

3

4

5

6

7

8

1

23

4

5

6

7

8

9

10

1

23

4

5

6

7

8

9

10

1

2

3

4

5

6

7

8

1

23

4

5

6

7

8

9

10

1

2

3

4

5

6

7

8

9

10

1

2

3

4

5

6

7

8

9

10

11

12

1

2

3

4

5

6

7

8

9

10

11

12

1

23

4

5

6

7

8

9

10

1

2

3

4

5

6

7

8

9

10

11

12

1

2

3

4

5

6

7

8

9

10

11

12

1

2

34

5

6

7

8

9

10

11

12

13

14

1

2

34

5

6

7

8

9

10

11

12

13

14

1

2

3

4

5

6

7

8

9

10

11

12

1

2

34

5

6

7

8

9

10

11

12

13

14

1

2

3

4

5

6

7

8

9

10

11

12

13

14

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

1

2

34

5

6

7

8

9

10

11

12

13

14

82

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

1

2

3

45

6

7

8

9

10

11

12

13

14

15

16

17

18

1

2

3

45

6

7

8

9

0

11

12

13

14

15

16

17

18

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

Análise do Crescimento

- Crescim en to Linear: Não

- Expres sao de Crescimento Nó: 2 (1+t) Iníc io em t= 2

- Expres sao de Crescimento Aresta: --- - -

Estrutura Repetitiva

12

3

4

5

6

1

2

3

4

1

2

3

4

5

Análise do Ciclo das Estruturas Repetitivas

- Estrutu ra 1 => Ciclo: 0 Inicio e m t = 2

- Estrut ura 2 => Ciclo: 2 Inicio e m t = 3

- Estrut ura 3 => Ciclo: 2 Inicio e m t = 4

REGRA ELE ME NTA R 23

Grafo em Evolução

GRAFO T COMUM GRAFO T +1 ESTR.ADIC. ESTR.EXCLUÍDA

1

23

4

5

6

7

8

9

10

1

2

3

4

5

6

7

8

9

10

1

2

34

5

6

7

8

9

10

11

12

13

14

1

2

34

5

6

7

8

9

10

11

12

13

14

1

23

4

5

6

7

8

9

10

1

2

34

5

6

7

8

9

10

11

12

13

14

1

2

3

4

5

6

7

8

9

10

11

12

13

14

1

2

3

45

6

7

8

9

10

11

12

13

14

15

16

17

18

1

2

3

45

6

7

8

9

0

11

12

13

14

15

16

17

18

1

2

34

5

6

7

8

9

10

11

12

13

14

83

1

2

3

45

6

7

8

9

10

11

12

13

14

15

16

17

18

1

2

3

45

6

7

8

9

10

11

12

13

14

15

16

17

18

1

2

3

4

56

7

8

9

0

1

2

13

14

15

16

17

18

19

20

21

22

1

2

3

4

56

7

8

9

0

1

2

13

14

15

16

17

18

19

20

21

22

1

2

3

45

6

7

8

9

10

11

12

13

14

15

16

17

18

1

2

3

4

56

7

8

9

10

1

12

13

14

15

16

17

18

19

20

21

22

1

2

3

4

56

7

8

9

0

1

2

13

14

15

16

17

18

19

20

21

22

1

2

3

4

5

67

8

9

10

11

2

3

4

15

16

17

18

19

20

21

22

23

24

25

26

1

2

3

4

5

67

8

9

10

11

2

3

4

15

16

17

18

19

20

21

22

23

24

25

26

1

2

3

4

56

7

8

9

10

1

12

13

14

15

16

17

18

19

20

21

22

1

2

3

4

5

67

8

9

10

11

2

3

4

15

16

17

18

19

20

21

22

23

24

25

26

1

2

3

4

5

67

8

9

10

11

2

3

4

15

16

17

18

19

20

21

22

23

24

25

26

1

2

3

4

5

6

78

9

10

11

12

13

4

5

6

17

18

19

20

21

22

23

24

25

26

27

28

29

30

1

2

3

4

5

6

78

9

10

11

12

13

4

5

6

17

18

19

20

21

22

23

24

25

26

27

28

29

30

1

2

3

4

5

67

8

9

10

11

2

3

4

15

16

17

18

19

20

21

22

23

24

25

26

1

2

3

4

5

6

78

9

10

11

12

13

4

5

6

17

18

19

20

21

22

23

24

25

26

27

28

29

30

1

2

3

4

5

6

78

9

10

11

12

13

4

5

6

17

18

19

20

21

22

23

24

25

26

27

28

29

30

1

2

3

4

5

6

7

89

10

11

12

13

14

15

6

7

8

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

1

2

3

4

5

6

7

89

10

11

12

13

14

15

6

7

8

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

1

2

3

4

5

6

78

9

10

11

12

13

4

5

6

17

18

19

20

21

22

23

24

25

26

27

28

29

30

1

2

3

4

5

6

7

89

10

11

12

13

14

15

6

7

8

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

1

2

3

4

5

6

7

89

10

11

12

13

14

15

6

7

8

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

1

2

3

4

5

6

7

8

910

11

12

13

14

15

16

17

8

9

0

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

1

2

3

4

5

6

7

8

910

11

12

13

14

15

16

7

8

9

0

1

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

1

2

3

4

5

6

7

89

10

11

12

13

14

15

6

7

8

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

Análise do Crescimento

- Crescim en to Linear: Sim

- Expres sao de Crescimento Nó: 6+4 t Início em t= 1

- Expres sao de Crescimento Aresta: 6 (2 +t) Iní cio em

t= 1

Estrutura Repetitiva

84

1

2

34

5

6

7

8

9

10

11

12

Análise do Ciclo das Estruturas Repetitivas

- Estrutu ra 1 => Ciclo: 1 Inicio e m t = 2

REGRA ELE ME NTA R 35

Grafo em Evolução

GRAFO T COMUM GRAFO T +1 ESTR.ADIC. ESTR.EXCLUÍDA

1

2

3

4

1

2

3

4

12

3

4

5

6

12

3

4

5

6

1

2

3

4

12

3

4

5

6

1

2

3

4

5

6

1

2

3

4

5

6

7

1

2

3

4

5

6

7

12

3

4

5

6

1

2

3

4

5

6

7

1

2

3

4

5

6

7

1

2

3

4

5

6

7

8

9

1

2

3

4

5

6

7

8

9

1

2

3

4

5

6

7

85

1

2

3

4

5

6

7

8

9

1

23

4

5

6

7

8

9

1

23

4

5

6

7

8

9

10

1

23

4

5

6

7

8

9

10

1

2

3

4

5

6

7

8

9

1

23

4

5

6

7

8

9

10

1

23

4

5

6

7

8

9

10

1

2

3

4

5

6

7

8

9

10

11

12

1

2

3

4

5

6

7

8

9

10

11

12

1

23

4

5

6

7

8

9

10

1

2

3

4

5

6

7

8

9

10

11

12

1

2

3

4

5

6

7

8

9

10

11

12

1

2

3

4

5

6

7

8

9

10

11

12

13

1

2

3

4

5

6

7

8

9

10

11

12

13

1

2

3

4

5

6

7

8

9

10

11

12

1

2

3

4

5

6

7

8

9

10

11

12

13

1

2

3

4

5

6

7

8

9

10

11

12

13

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

1

2

3

4

5

6

7

8

9

10

11

12

13

Análise do Crescimento

- Crescim en to Linear: Não

- Expres sao de Crescimento Nó: --- - -

- Expres sao de Crescimento Aresta: --- - -

Estrutura Repetitiva

12

3

4

1

2

3

1

2

3

4

5

Análise do Ciclo das Estruturas Repetitivas

- Estrutu ra 1 => Ciclo: 0 Inicio e m t = 2

- Estrut ura 2 => Ciclo: 2 Inicio e m t = 3

- Estrut ura 3 => Ciclo: 2 Inicio e m t = 4

REGRA ELE ME NTA R 43

86

Grafo em Evolução

GRAFO T COMUM GRAFO T +1 ESTR.ADIC. ESTR.EXCLUÍDA

1

2

3

4

5

6

7

8

1

2

3

4

5

6

7

8

1

2

3

4

5

6

7

8

9

10

11

12

1

2

3

4

5

6

7

8

9

10

11

12

1

2

3

4

5

6

7

8

1

2

3

4

5

6

7

8

9

10

11

12

1

2

3

4

5

6

7

8

9

10

11

12

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

1

2

3

4

5

6

7

8

9

10

11

12

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

1

2

3

4

5

6

7

8

9

0

11

12

13

14

15

16

17

18

19

20

1

2

3

4

5

6

7

8

9

0

1

12

13

14

15

16

17

18

19

20

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

1

2

3

4

5

6

7

8

9

0

11

12

13

14

15

16

17

18

19

20

1

2

3

4

5

6

7

8

9

0

11

12

13

14

15

16

17

18

19

20

1

2

3

4

5

6

7

8

9

10

1

2

3

14

15

16

17

18

19

20

21

22

23

24

1

2

3

4

5

6

7

8

9

10

1

2

3

14

15

16

17

18

19

20

21

22

23

24

1

2

3

4

5

6

7

8

9

0

11

12

13

14

15

16

17

18

19

20

1

2

3

4

5

6

7

8

9

10

1

2

3

14

15

16

17

18

19

20

21

22

23

24

1

2

3

4

5

6

7

8

9

10

1

2

3

14

15

16

17

18

19

20

21

22

23

24

1

2

3

4

5

6

7

8

9

10

11

12

3

4

5

16

17

18

19

20

21

22

23

24

25

26

27

28

1

2

3

4

5

6

7

8

9

10

11

12

3

4

5

16

17

18

19

20

21

22

23

24

25

26

27

28

1

2

3

4

5

6

7

8

9

10

1

2

3

14

15

16

17

18

19

20

21

22

23

24

1

2

3

4

5

6

7

8

9

10

11

12

3

4

5

16

17

18

19

20

21

22

23

24

25

26

27

28

1

2

3

4

5

6

7

8

9

10

11

12

3

4

5

16

17

18

19

20

21

22

23

24

25

26

27

28

1

2

3

4

5

6

7

8

9

10

11

12

13

14

5

6

7

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

1

2

3

4

5

6

7

8

9

10

11

12

13

14

5

6

7

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

1

2

3

4

5

6

7

8

9

10

11

12

3

4

5

16

17

18

19

20

21

22

23

24

25

26

27

28

87

1

2

3

4

5

6

7

8

9

10

11

12

13

14

5

6

7

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

1

2

3

4

5

6

7

8

9

10

11

12

13

14

5

6

7

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

7

8

9

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

6

7

8

9

0

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

1

2

3

4

5

6

7

8

9

10

11

12

13

14

5

6

7

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

Análise do Crescimento

- Crescim en to Linear: Sim

- Expres sao de Crescimento Nó: 4 (1+t) Iníc io em t= 1

- Expres sao de Crescimento Aresta: 8+6 t Início em t=

1

Estrutura Repetitiva

1

2

3

4

5

6

7

8

9

10

Análise do Ciclo das Estruturas Repetitivas

- Estrutu ra 1 => Ciclo: 1 Inicio e m t = 2

REGRA ELE ME NTA R 50

Grafo em Evolução

GRAFO T COMUM GRAFO T +1 ESTR.ADIC. ESTR.EXCLUÍDA

1

2

3

1

2

3

1

2

3

4

5

6

7

1

2

3

4

5

6

7

1

2

3

88

1

2

3

4

5

6

7

1

2

3

4

5

6

7

1

2

3

4

5

6

7

8

9

1

2

3

4

5

6

7

8

9

1

2

3

4

5

6

7

1

2

3

4

5

6

7

8

9

1

2

3

4

5

6

7

8

9

1

2

3

4

5

6

7

8

9

10

11

1

2

3

4

5

6

7

8

9

10

11

1

2

3

4

5

6

7

8

9

1

2

3

4

5

6

7

8

9

10

11

1

2

3

4

5

6

7

8

9

10

11

1

2

3

4

5

6

7

8

9

10

11

12

13

1

2

3

4

5

6

7

8

9

10

11

12

13

1

2

3

4

5

6

7

8

9

10

11

1

2

3

4

5

6

7

8

9

10

11

12

13

1

2

3

4

5

6

7

8

9

10

11

12

13

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

1

2

3

4

5

6

7

8

9

10

11

12

13

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

1

2

3

4

5

6

7

8

9

0

11

12

13

14

15

16

17

18

19

1

2

3

4

5

6

7

8

9

0

11

12

13

14

15

16

17

18

19

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

Análise do Crescimento

- Crescim en to Linear: Sim

- Expres sao de Crescimento Nó: 3+2 t Início em t= 2

- Expres sao de Crescimento Aresta: 3 (2 +t) Iní cio em

89

t= 2

Estrutura Repetitiva

1

2

3

4

5

6

7

1

2

3

4

5

6

7

1

2

3

4

5

6

Análise do Ciclo das Estruturas Repetitivas

- Estrutu ra 1 => Ciclo: 0 Inicio e m t = 2

- Estrut ura 2 => Ciclo: 2 Inicio e m t = 3

- Estrut ura 3 => Ciclo: 2 Inicio e m t = 4

REGRA ELE ME NTA R 56

Grafo em Evolução

GRAFO T COMUM GRAFO T +1 ESTR.ADIC.

ESTR.EXCLUÍDA

1

2

3

1

2

3

1

2

3

4

1

2

3

4

1

2

3

1

2

3

4

1

2

3

4

12

3

4

5

6

12

3

4

5

6

1

2

3

4

12

3

4

5

6

1

2

3

4

5

6

1

2

3

4

5

6

7

8

1

2

3

4

5

6

7

8

12

3

4

5

6

90

1

2

3

4

5

6

7

8

1

23

4

5

6

7

8

1

23

4

5

6

7

8

9

10

1

23

4

5

6

7

8

9

10

1

2

3

4

5

6

7

8

1

23

4

5

6

7

8

9

10

1

2

3

4

5

6

7

8

9

10

1

2

3

4

5

6

7

8

9

10

11

12

1

2

3

4

5

6

7

8

9

10

11

12

1

23

4

5

6

7

8

9

10

1

2

3

4

5

6

7

8

9

10

11

12

1

2

34

5

6

7

8

9

10

11

12

1

2

34

5

6

7

8

9

10

11

12

13

14

1

2

34

5

6

7

8

9

10

11

12

13

14

1

2

3

4

5

6

7

8

9

10

11

12

1

2

34

5

6

7

8

9

10

11

12

13

14

1

2

3

4

5

6

7

8

9

10

11

12

13

14

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

1

2

34

5

6

7

8

9

10

11

12

13

14

Análise do Crescimento

- Crescim en to Linear: Sim

- Expres sao de Crescimento Nó: 2 t Início em t= 2

- Expres sao de Crescimento Aresta: 3 t Iníc io em t= 2

Estrutura Repetitiva

1

2

3

12

3

4

5

Análise do Ciclo das Estruturas Repetitivas

- Estrutu ra 1 => Ciclo: 0 Inicio e m t = 2

- Estrut ura 2 => Ciclo: 1 Inicio e m t = 3

91

REGRA ELE ME NTA R 70

Grafo em Evolução

GRAFO T COMUM GRAFO T +1 ESTR.ADIC.

ESTR.EXCLUÍDA

1

2

3

1

2

3

1

2

3

4

5

6

7

1

2

3

4

5

6

7

1

2

3

1

2

3

4

5

6

7

1

2

3

4

5

6

7

1

2

3

4

5

6

7

8

9

1

2

3

4

5

6

7

8

9

1

2

3

4

5

6

7

1

2

3

4

5

6

7

8

9

12

3

4

5

6

7

8

9

1

23

4

5

6

7

8

9

10

1

23

4

5

6

7

8

9

10

1

2

3

4

5

6

7

8

9

1

23

4

5

6

7

8

9

10

1

2

3

4

5

6

7

8

9

10

1

2

3

4

5

6

7

8

9

10

11

1

2

3

4

5

6

7

8

9

10

11

1

23

4

5

6

7

8

9

10

1

2

3

4

5

6

7

8

9

10

11

1

2

3

4

5

6

7

8

9

10

11

1

2

3

4

5

6

7

8

9

10

11

12

1

2

3

4

5

6

7

8

9

10

11

12

1

2

3

4

5

6

7

8

9

10

11

92

1

2

3

4

5

6

7

8

9

10

11

12

1

2

3

4

5

6

7

8

9

10

11

12

1

2

3

4

5

6

7

8

9

10

11

12

13

1

2

3

4

5

6

7

8

9

10

11

12

13

1

2

3

4

5

6

7

8

9

10

11

12

1

2

3

4

5

6

7

8

9

10

11

12

13

1

23

4

5

6

7

8

9

10

11

12

13

1

2

34

5

6

7

8

9

10

11

12

13

14

1

2

34

5

6

7

8

9

10

11

12

13

14

1

2

3

4

5

6

7

8

9

10

11

12

13

Análise do Crescimento

- Crescim en to Linear: Sim

- Expres sao de Crescimento Nó: 6+t Início e m t= 3

- Expres sao de Crescimento Aresta: 12+t Início em t= 3

Estrutura Repetitiva

1

2

3

4

5

6

7

1

2

3

4

5

6

1

2

3

1

2

3

4

Análise do Ciclo das Estruturas Repetitivas

- Estrutu ra 1 => Ciclo: 0 Inicio e m t = 2

- Estrut ura 2 => Ciclo: 0 Inicio e m t = 3

- Estrut ura 3 => Ciclo: 2 Inicio e m t = 4

- Estrut ura 4 => Ciclo: 2 Inicio e m t = 5

REGRA ELE ME NTA R 81

Grafo em Evolução

GRAFO T COMUM GRAFO T +1 ESTR.ADIC. ESTR.EXCLUÍDA

1

2

3

1

2

3

1

2

3

4

5

1

2

3

4

5

1

2

3

93

1

2

3

4

5

1

2

3

4

5

1

2

3

4

5

6

7

8

1

2

3

4

5

6

7

8

1

2

3

4

5

1

2

3

4

5

6

7

8

12

3

4

5

6

7

8

1

23

4

5

6

7

8

9

10

1

23

4

5

6

7

8

9

10

1

2

3

4

5

6

7

8

1

23

4

5

6

7

8

9

10

1

23

4

5

6

7

8

9

10

1

2

3

4

5

6

7

8

9

10

11

12

1

2

3

4

5

6

7

8

9

10

11

12

1

23

4

5

6

7

8

9

10

1

2

3

4

5

6

7

8

9

10

11

12

1

23

4

5

6

7

8

9

10

11

12

1

2

34

5

6

7

8

9

10

11

12

13

14

1

2

34

5

6

7

8

9

10

11

12

13

14

1

2

3

4

5

6

7

8

9

10

11

12

1

2

34

5

6

7

8

9

10

11

12

13

14

1

2

34

5

6

7

8

9

10

11

12

13

14

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

1

2

34

5

6

7

8

9

10

11

12

13

14

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

1

2

34

5

6

7

8

9

10

11

12

13

14

15

16

1

2

3

45

6

7

8

9

10

11

12

13

14

15

16

17

18

1

2

3

45

6

7

8

9

0

11

12

13

14

15

16

17

18

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

Análise do Crescimento

- Crescim en to Linear: Sim

- Expres sao de Crescimento Nó: 2 (1+t) Iníc io em t= 3

- Expres sao de Crescimento Aresta: 4+3 t Início em t= 3

94

Estrutura Repetitiva

1

2

3

4

1

2

3

4

5

6

7

1

2

3

4

5

1

2

3

4

5

1

2

3

4

5

6

1

2

3

4

5

6

1

3

4

5

6

7

Análise do Ciclo das Estruturas Repetitivas

- Estrutu ra 1 => Ciclo: 0 Inicio e m t = 2

- Estrut ura 2 => Ciclo: 0 Inicio e m t = 3

- Estrut ura 3 => Ciclo: 0 Inicio e m t = 4

- Estrut ura 4 => Ciclo: 0 Inicio e m t = 5

- Estrut ura 5 => Ciclo: 0 Inicio e m t = 6

- Estrut ura 6 => Ciclo: 0 Inicio e m t = 7

- Estrut ura 7 => Ciclo: 0 Inicio em t = 8

REGRA ELE ME NTA R 98

Grafo em Evolução

GRAFO T COMUM GRAFO T +1 ESTR.ADIC. ESTR.EXCLUÍDA

1

2

3

1

2

3

1

2

3

4

1

2

3

4

1

2

3

1

2

3

4

1

2

3

4

12

3

4

5

6

12

3

4

5

6

1

2

3

4

12

3

4

5

6

12

3

4

5

6

1

2

3

4

5

6

7

8

1

2

3

4

5

6

7

8

12

3

4

5

6

1

2

3

4

5

6

7

8

1

2

3

4

5

6

7

8

1

23

4

5

6

7

8

9

10

1

23

4

5

6

7

8

9

10

1

2

3

4

5

6

7

8

95

1

23

4

5

6

7

8

9

10

1

2

3

4

5

6

7

8

9

10

1

2

3

4

5

6

7

8

9

10

11

12

1

2

3

4

5

6

7

8

9

10

11

12

1

23

4

5

6

7

8

9

10

1

2

3

4

5

6

7

8

9

10

11

12

1

2

34

5

6

7

8

9

10

11

12

1

2

34

5

6

7

8

9

10

11

12

13

14

1

2

34

5

6

7

8

9

10

11

12

13

14

1

2

3

4

5

6

7

8

9

10

11

12

1

2

34

5

6

7

8

9

10

11

12

13

14

1

2

3

4

5

6

7

8

9

10

11

12

13

14

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

1

2

34

5

6

7

8

9

10

11

12

13

14

Análise do Crescimento

- Crescim en to Linear: Sim

- Expres sao de Crescimento Nó: 2 t Início em t= 2

- Expres sao de Crescimento Aresta: 1+3 t Início em t=

2

Estrutura Repetitiva

1

2

3

12

3

4

1

2

3

4

5

Análise do Ciclo das Estruturas Repetitivas

- Estrutu ra 1 => Ciclo: 0 Inicio e m t = 2

- Estrut ura 2 => Ciclo: 0 Inicio e m t = 3

- Estrut ura 3 => Ciclo: 1 Inicio e m t = 4

REGRA ELE ME NTA R 113

Grafo em Evolução

GRAFO T COMUM GRAFO T +1 ESTR.ADIC. ESTR.EXCLUÍDA

96

1

2

3

4

5

6

7

8

1

2

3

4

5

6

7

8

1

2

3

4

5

6

7

8

9

10

11

12

1

2

3

4

5

6

7

8

9

10

11

12

1

2

3

4

5

6

7

8

1

2

3

4

5

6

7

8

9

10

11

12

1

2

3

4

5

6

7

8

9

10

11

12

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

1

2

3

4

5

6

7

8

9

10

11

12

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

1

2

3

4

5

6

7

8

9

0

11

12

13

14

15

16

17

18

19

20

1

2

3

4

5

6

7

8

9

0

1

12

13

14

15

16

17

18

19

20

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

1

2

3

4

5

6

7

8

9

0

11

12

13

14

15

16

17

18

19

20

1

2

3

4

5

6

7

8

9

0

11

12

13

14

15

16

17

18

19

20

1

2

3

4

5

6

7

8

9

10

1

2

3

14

15

16

17

18

19

20

21

22

23

24

1

2

3

4

5

6

7

8

9

10

1

2

3

14

15

16

17

18

19

20

21

22

23

24

1

2

3

4

5

6

7

8

9

0

11

12

13

14

15

16

17

18

19

20

1

2

3

4

5

6

7

8

9

10

1

2

3

14

15

16

17

18

19

20

21

22

23

24

1

2

3

4

5

6

7

8

9

10

1

2

3

14

15

16

17

18

19

20

21

22

23

24

1

2

3

4

5

6

7

8

9

10

11

12

3

4

5

16

17

18

19

20

21

22

23

24

25

26

27

28

1

2

3

4

5

6

7

8

9

10

11

12

3

4

5

16

17

18

19

20

21

22

23

24

25

26

27

28

1

2

3

4

5

6

7

8

9

10

1

2

3

14

15

16

17

18

19

20

21

22

23

24

1

2

3

4

5

6

7

8

9

10

11

12

3

4

5

16

17

18

19

20

21

22

23

24

25

26

27

28

1

2

3

4

5

6

7

8

9

10

11

12

3

4

5

16

17

18

19

20

21

22

23

24

25

26

27

28

1

2

3

4

5

6

7

8

9

10

11

12

13

14

5

6

7

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

1

2

3

4

5

6

7

8

9

10

11

12

13

14

5

6

7

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

1

2

3

4

5

6

7

8

9

10

11

12

3

4

5

16

17

18

19

20

21

22

23

24

25

26

27

28

97

1

2

3

4

5

6

7

8

9

10

11

12

13

14

5

6

7

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

1

2

3

4

5

6

7

8

9

10

11

12

13

14

5

6

7

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

7

8

9

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

6

7

8

9

0

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

1

2

3

4

5

6

7

8

9

10

11

12

13

14

5

6

7

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

Análise do Crescimento

- Crescim en to Linear: Sim

- Expres sao de Crescimento Nó: 4 (1+t) Iníc io em t= 1

- Expres sao de Crescimento Aresta: 8+6 t Início em t=

1

Estrutura Repetitiva

1

2

3

4

5

6

7

8

9

10

Análise do Ciclo das Estruturas Repetitivas

- Estrutu ra 1 => Ciclo: 1 Inicio e m t = 2

REGRA ELE ME NTA R 128

Grafo em Evolução

GRAFO T COMUM GRAFO T +1 ESTR.ADIC. ESTR.EXCLUÍDA

1

2

3

4

1

2

3

4

12

3

4

5

6

12

3

4

5

6

1

2

3

4

98

12

3

4

5

6

1

2

3

4

5

6

1

2

3

4

5

6

7

8

1

2

3

4

5

6

7

8

12

3

4

5

6

1

2

3

4

5

6

7

8

1

23

4

5

6

7

8

1

23

4

5

6

7

8

9

10

1

23

4

5

6

7

8

9

10

1

2

3

4

5

6

7

8

1

23

4

5

6

7

8

9

10

1

2

3

4

5

6

7

8

9

10

1

2

3

4

5

6

7

8

9

10

11

12

1

2

3

4

5

6

7

8

9

10

11

12

1

23

4

5

6

7

8

9

10

1

2

3

4

5

6

7

8

9

10

11

12

1

2

34

5

6

7

8

9

10

11

12

1

2

34

5

6

7

8

9

10

11

12

13

14

1

2

34

5

6

7

8

9

10

11

12

13

14

1

2

3

4

5

6

7

8

9

10

11

12

1

2

34

5

6

7

8

9

10

11

12

13

14

1

2

3

4

5

6

7

8

9

10

11

12

13

14

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

1

2

34

5

6

7

8

9

10

11

12

13

14

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

1

2

3

45

6

7

8

9

10

11

12

13

14

15

16

1

2

3

45

6

7

8

9

10

11

12

13

14

15

16

17

18

1

2

3

45

6

7

8

9

0

11

12

13

14

15

16

17

18

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

Análise do Crescimento

- Crescim en to Linear: Sim

- Expres sao de Crescimento Nó: 2 (1+t) Iníc io em t= 1

- Expres sao de Crescimento Aresta: 2 (2 +t) Iní cio em

99

t= 1

Estrutura Repetitiva

1

2

3

4

Análise do Ciclo das Estruturas Repetitivas

- Estrutu ra 1 => Ciclo: 1 Inicio e m t = 2

REGRA ELE ME NTA R 132

Grafo em Evolução

GRAFO T COMUM GRAFO T +1 ESTR.ADIC. ESTR.EXCLUÍDA

1

2

3

4

5

1

2

3

4

5

1

2

3

4

5

6

7

1

2

3

4

5

6

7

1

2

3

4

5

1

2

3

4

5

6

7

1

2

3

4

5

6

7

1

2

3

4

5

6

7

8

9

1

2

3

4

5

6

7

8

9

1

2

3

4

5

6

7

100

1

2

3

4

5

6

7

8

9

1

2

3

4

5

6

7

8

9

1

2

3

4

5

6

7

8

9

10

11

1

2

3

4

5

6

7

8

9

10

11

1

2

3

4

5

6

7

8

9

1

2

3

4

5

6

7

8

9

10

11

1

2

3

4

5

6

7

8

9

10

11

1

2

3

4

5

6

7

8

9

10

11

12

13

1

2

3

4

5

6

7

8

9

10

11

12

13

1

2

3

4

5

6

7

8

9

10

11

1

2

3

4

5

6

7

8

9

10

11

12

13

1

2

3

4

5

6

7

8

9

10

11

12

13

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

1

2

3

4

5

6

7

8

9

10

11

12

13

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

1

2

3

4

5

6

7

8

9

0

11

12

13

14

15

16

17

18

19

1

2

3

4

5

6

7

8

9

0

11

12

13

14

15

16

17

18

19

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

Análise do Crescimento

- Crescim en to Linear: Sim

- Expres sao de Crescimento Nó: 3+2 t Início em t= 1

- Expres sao de Crescimento Aresta: 3 (2 +t) Iní cio em

t= 1

Estrutura Repetitiva

101

1

2

3

4

5

6

Análise do Ciclo das Estruturas Repetitivas

- Estrutu ra 1 => Ciclo: 1 Inicio e m t = 2

REGRA ELE ME NTA R 136

Grafo em Evolução

GRAFO T COMUM GRAFO T +1 ESTR.ADIC. ESTR.EXCLUÍDA

1

2

3

1

2

3

1

2

3

4

1

2

3

4

1

2

3

1

2

3

4

1

2

3

4

1

2

3

4

5

1

2

3

4

5

1

2

3

4

1

2

3

4

5

12

3

4

5

12

3

4

5

6

12

3

4

5

6

1

2

3

4

5

102

12

3

4

5

6

1

2

3

4

5

6

1

2

3

4

5

6

7

1

2

3

4

5

6

7

12

3

4

5

6

1

2

3

4

5

6

7

1

2

3

4

5

6

7

1

2

3

4

5

6

7

8

1

2

3

4

5

6

7

8

1

2

3

4

5

6

7

1

2

3

4

5

6

7

8

1

2

3

4

5

6

7

8

1

2

3

4

5

6

7

8

9

1

2

3

4

5

6

7

8

9

1

2

3

4

5

6

7

8

1

2

3

4

5

6

7

8

9

1

23

4

5

6

7

8

9

1

23

4

5

6

7

8

9

10

1

23

4

5

6

7

8

9

10

1

2

3

4

5

6

7

8

9

Análise do Crescimento

- Crescim en to Linear: Sim

- Expres sao de Crescimento Nó: 2+t Início e m t= 1

- Expres sao de Crescimento Aresta: 4+t Início em t= 1

Estrutura Repetitiva

103

1

2 3

Análise do Ciclo das Estruturas Repetitivas

- Estrutu ra 1 => Ciclo: 1 Inicio e m t = 2

REGRA ELE ME NTA R 140

Grafo em Evolução

GRAFO T COMUM GRAFO T +1 ESTR.ADIC. ESTR.EXCLUÍDA

1

2

3

4

1

2

3

4

1

2

3

4

5

1

2

3

4

5

1

2

3

4

1

2

3

4

5

1

2

3

4

5

12

3

4

5

6

12

3

4

5

6

1

2

3

4

5

12

3

4

5

6

1

2

3

4

5

6

1

2

3

4

5

6

7

1

2

3

4

5

6

7

12

3

4

5

6

104

1

2

3

4

5

6

7

1

2

3

4

5

6

7

1

2

3

4

5

6

7

8

1

2

3

4

5

6

7

8

1

2

3

4

5

6

7

1

2

3

4

5

6

7

8

1

2

3

4

5

6

7

8

1

2

3

4

5

6

7

8

9

1

2

3

4

5

6

7

8

9

1

2

3

4

5

6

7

8

1

2

3

4

5

6

7

8

9

1

23

4

5

6

7

8

9

1

23

4

5

6

7

8

9

10

1

23

4

5

6

7

8

9

10

1

2

3

4

5

6

7

8

9

1

23

4

5

6

7

8

9

10

1

2

3

4

5

6

7

8

9

10

1

2

3

4

5

6

7

8

9

10

11

1

2

3

4

5

6

7

8

9

10

11

1

23

4

5

6

7

8

9

10

Análise do Crescimento

- Crescim en to Linear: Sim

- Expres sao de Crescimento Nó: 3+t Início e m t= 1

- Expres sao de Crescimento Aresta: 6+t Início em t= 1

Estrutura Repetitiva

105

1

2

3

Análise do Ciclo das Estruturas Repetitivas

- Estrutu ra 1 => Ciclo: 1 Inicio e m t = 2

REGRA ELE ME NTA R 142

Grafo em Evolução

GRAFO T COMUM GRAFO T +1 ESTR.ADIC. ESTR.EXCLUÍDA

1

2

3

4

5

6

7

8

1

2

3

4

5

6

7

8

1

2

3

4

5

6

7

8

9

10

11

12

1

2

3

4

5

6

7

8

9

10

11

12

1

2

3

4

5

6

7

8

1

2

3

4

5

6

7

8

9

10

11

12

1

2

3

4

5

6

7

8

9

10

11

12

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

1

2

3

4

5

6

7

8

9

10

11

12

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

1

2

3

4

5

6

7

8

9

0

11

12

13

14

15

16

17

18

19

20

1

2

3

4

5

6

7

8

9

0

1

12

13

14

15

16

17

18

19

20

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

106

1

2

3

4

5

6

7

8

9

0

11

12

13

14

15

16

17

18

19

20

1

2

3

4

5

6

7

8

9

0

11

12

13

14

15

16

17

18

19

20

1

2

3

4

5

6

7

8

9

10

1

2

3

14

15

16

17

18

19

20

21

22

23

24

1

2

3

4

5

6

7

8

9

10

1

2

3

14

15

16

17

18

19

20

21

22

23

24

1

2

3

4

5

6

7

8

9

0

11

12

13

14

15

16

17

18

19

20

1

2

3

4

5

6

7

8

9

10

1

2

3

14

15

16

17

18

19

20

21

22

23

24

1

2

3

4

5

6

7

8

9

10

1

2

3

14

15

16

17

18

19

20

21

22

23

24

1

2

3

4

5

6

7

8

9

10

11

12

3

4

5

16

17

18

19

20

21

22

23

24

25

26

27

28

1

2

3

4

5

6

7

8

9

10

11

12

3

4

5

16

17

18

19

20

21

22

23

24

25

26

27

28

1

2

3

4

5

6

7

8

9

10

1

2

3

14

15

16

17

18

19

20

21

22

23

24

1

2

3

4

5

6

7

8

9

10

11

12

3

4

5

16

17

18

19

20

21

22

23

24

25

26

27

28

1

2

3

4

5

6

7

8

9

10

11

12

3

4

5

16

17

18

19

20

21

22

23

24

25

26

27

28

1

2

3

4

5

6

7

8

9

10

11

12

13

14

5

6

7

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

1

2

3

4

5

6

7

8

9

10

11

12

13

14

5

6

7

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

1

2

3

4

5

6

7

8

9

10

11

12

3

4

5

16

17

18

19

20

21

22

23

24

25

26

27

28

1

2

3

4

5

6

7

8

9

10

11

12

13

14

5

6

7

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

1

2

3

4

5

6

7

8

9

10

11

12

13

14

5

6

7

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

7

8

9

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

6

7

8

9

0

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

1

2

3

4

5

6

7

8

9

10

11

12

13

14

5

6

7

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

Análise do Crescimento

- Crescim en to Linear: Sim

- Expres sao de Crescimento Nó: 4 (1+t) Iníc io em t= 1

- Expres sao de Crescimento Aresta: 8+6 t Início em t=

1

Estrutura Repetitiva

107

1

2

3

4

5

6

7

8

9

10

Análise do Ciclo das Estruturas Repetitivas

- Estrutu ra 1 => Ciclo: 1 Inicio e m t = 2

REGRA ELE ME NTA R 162

Grafo em Evolução

GRAFO T COMUM GRAFO T +1 ESTR.ADIC. ESTR.EXCLUÍDA

1

2

3

4

5

1

2

3

4

5

1

2

3

4

5

6

7

1

2

3

4

5

6

7

1

2

3

4

5

1

2

3

4

5

6

7

1

2

3

4

5

6

7

1

2

3

4

5

6

7

8

9

1

2

3

4

5

6

7

8

9

1

2

3

4

5

6

7

1

2

3

4

5

6

7

8

9

1

2

3

4

5

6

7

8

9

1

2

3

4

5

6

7

8

9

10

11

1

2

3

4

5

6

7

8

9

10

11

1

2

3

4

5

6

7

8

9

108

1

2

3

4

5

6

7

8

9

10

11

1

2

3

4

5

6

7

8

9

10

11

1

2

3

4

5

6

7

8

9

10

11

12

13

1

2

3

4

5

6

7

8

9

10

11

12

13

1

2

3

4

5

6

7

8

9

10

11

1

2

3

4

5

6

7

8

9

10

11

12

13

1

2

3

4

5

6

7

8

9

10

11

12

13

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

1

2

3

4

5

6

7

8

9

10

11

12

13

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

1

2

3

4

5

6

7

8

9

0

11

12

13

14

15

16

17

18

19

1

2

3

4

5

6

7

8

9

0

11

12

13

14

15

16

17

18

19

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

Análise do Crescimento

- Crescim en to Linear: Sim

- Expres sao de Crescimento Nó: 3+2 t Início em t= 1

- Expres sao de Crescimento Aresta: 3 (2 +t) Iní cio em

t= 1

Estrutura Repetitiva

109

1

2

3

4

5

Análise do Ciclo das Estruturas Repetitivas

- Estrutu ra 1 => Ciclo: 1 Inicio e m t = 2

REGRA ELE ME NTA R 168

Grafo em Evolução

GRAFO T COMUM GRAFO T +1 ESTR.ADIC. ESTR.EXCLUÍDA

1

2

3

4

1

2

3

4

1

2

3

4

5

1

2

3

4

5

1

2

3

4

1

2

3

4

5

1

2

3

4

5

12

3

4

5

6

12

3

4

5

6

1

2

3

4

5

12

3

4

5

6

1

2

3

4

5

6

1

2

3

4

5

6

7

1

2

3

4

5

6

7

12

3

4

5

6

110

1

2

3

4

5

6

7

1

2

3

4

5

6

7

1

2

3

4

5

6

7

8

1

2

3

4

5

6

7

8

1

2

3

4

5

6

7

1

2

3

4

5

6

7

8

1

2

3

4

5

6

7

8

1

2

3

4

5

6

7

8

9

1

2

3

4

5

6

7

8

9

1

2

3

4

5

6

7

8

1

2

3

4

5

6

7

8

9

1

23

4

5

6

7

8

9

1

23

4

5

6

7

8

9

10

1

23

4

5

6

7

8

9

10

1

2

3

4

5

6

7

8

9

1

23

4

5

6

7

8

9

10

1

2

3

4

5

6

7

8

9

10

1

2

3

4

5

6

7

8

9

10

11

1

2

3

4

5

6

7

8

9

10

11

1

23

4

5

6

7

8

9

10

Análise do Crescimento

- Crescim en to Linear: Sim

- Expres sao de Crescimento Nó: 3+t Início e m t= 1

- Expres sao de Crescimento Aresta: 6+t Início em t= 1

Estrutura Repetitiva

111

1

2

3

Análise do Ciclo das Estruturas Repetitivas

- Estrutu ra 1 => Ciclo: 1 Inicio e m t = 2

REGRA ELE ME NTA R 172

Grafo em Evolução

GRAFO T COMUM GRAFO T +1 ESTR.ADIC. ESTR.EXCLUÍDA

1

2

3

4

5

6

7

8

1

2

3

4

5

6

7

8

1

2

3

4

5

6

7

8

9

10

11

1

2

3

4

5

6

7

8

9

10

11

1

2

3

4

5

6

7

8

1

2

3

4

5

6

7

8

9

10

11

1

2

3

4

5

6

7

8

9

10

11

1

2

3

4

5

6

7

8

9

10

11

12

1

2

3

4

5

6

7

8

9

10

11

12

1

2

3

4

5

6

7

8

9

10

11

1

2

3

4

5

6

7

8

9

10

11

12

1

2

3

4

5

6

7

8

9

10

11

12

1

2

3

4

5

6

7

8

9

10

11

12

13

1

2

3

4

5

6

7

8

9

10

11

12

13

1

2

3

4

5

6

7

8

9

10

11

12

112

1

2

3

4

5

6

7

8

9

10

11

12

13

1

2

34

5

6

7

8

9

10

11

12

13

1

2

34

5

6

7

8

9

10

11

12

13

14

1

2

34

5

6

7

8

9

10

11

12

13

14

1

2

3

4

5

6

7

8

9

10

11

12

13

1

2

34

5

6

7

8

9

10

11

12

13

14

1

2

3

4

5

6

7

8

9

10

11

12

13

14

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

1

2

34

5

6

7

8

9

10

11

12

13

14

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

Análise do Crescimento

- Crescim en to Linear: Sim

- Expres sao de Crescimento Nó: 9+t Início e m t= 2

- Expres sao de Crescimento Aresta: 17+t Início em t= 2

Estrutura Repetitiva

1

2

3

4

5

6

7

8

1

2

3

Análise do Ciclo das Estruturas Repetitivas

- Estrutu ra 1 => Ciclo: 0 Inicio e m t = 2

- Estrut ura 2 => Ciclo: 1 Inicio e m t = 3

113

REGRA ELE ME NTA R 176

Grafo em Evolução

GRAFO T COMUM GRAFO T +1 ESTR.ADIC. ESTR.EXCLUÍDA

1

2

3

4

5

1

2

3

4

5

1

2

3

4

5

6

7

1

2

3

4

5

6

7

1

2

3

4

5

1

2

3

4

5

6

7

1

2

3

4

5

6

7

1

2

3

4

5

6

7

8

9

1

2

3

4

5

6

7

8

9

1

2

3

4

5

6

7

1

2

3

4

5

6

7

8

9

1

2

3

4

5

6

7

8

9

1

2

3

4

5

6

7

8

9

10

11

1

2

3

4

5

6

7

8

9

10

11

1

2

3

4

5

6

7

8

9

1

2

3

4

5

6

7

8

9

10

11

1

2

3

4

5

6

7

8

9

10

11

1

2

3

4

5

6

7

8

9

10

11

12

13

1

2

3

4

5

6

7

8

9

10

11

12

13

1

2

3

4

5

6

7

8

9

10

11

1

2

3

4

5

6

7

8

9

10

11

12

13

1

2

3

4

5

6

7

8

9

10

11

12

13

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

1

2

3

4

5

6

7

8

9

10

11

12

13

114

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

1

2

3

4

5

6

7

8

9

0

11

12

13

14

15

16

17

18

19

1

2

3

4

5

6

7

8

9

0

11

12

13

14

15

16

17

18

19

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

Análise do Crescimento

- Crescim en to Linear: Sim

- Expres sao de Crescimento Nó: 3+2 t Início em t= 1

- Expres sao de Crescimento Aresta: 2 (3 +t) Iní cio em

t= 1

Estrutura Repetitiva

1

2

3

4

Análise do Ciclo das Estruturas Repetitivas

- Estrutu ra 1 => Ciclo: 1 Inicio e m t = 2

REGRA ELE ME NTA R 184

Grafo em Evolução

GRAFO T COMUM GRAFO T +1 ESTR.ADIC. ESTR.EXCLUÍDA

115

1

2

3

4

1

2

3

4

12

3

4

5

6

12

3

4

5

6

1

2

3

4

12

3

4

5

6

1

2

3

4

5

6

1

2

3

4

5

6

7

8

1

2

3

4

5

6

7

8

12

3

4

5

6

1

2

3

4

5

6

7

8

1

23

4

5

6

7

8

1

23

4

5

6

7

8

9

10

1

23

4

5

6

7

8

9

10

1

2

3

4

5

6

7

8

1

23

4

5

6

7

8

9

10

1

2

3

4

5

6

7

8

9

10

1

2

3

4

5

6

7

8

9

10

11

12

1

2

3

4

5

6

7

8

9

10

11

12

1

23

4

5

6

7

8

9

10

1

2

3

4

5

6

7

8

9

10

11

12

1

2

34

5

6

7

8

9

10

11

12

1

2

34

5

6

7

8

9

10

11

12

13

14

1

2

34

5

6

7

8

9

10

11

12

13

14

1

2

3

4

5

6

7

8

9

10

11

12

1

2

34

5

6

7

8

9

10

11

12

13

14

1

2

3

4

5

6

7

8

9

10

11

12

13

14

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

1

2

34

5

6

7

8

9

10

11

12

13

14

116

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

1

2

3

45

6

7

8

9

10

11

12

13

14

15

16

1

2

3

45

6

7

8

9

10

11

12

13

14

15

16

17

18

1

2

3

45

6

7

8

9

0

11

12

13

14

15

16

17

18

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

Análise do Crescimento

- Crescim en to Linear: Sim

- Expres sao de Crescimento Nó: 2 (1+t) Iníc io em t= 1

- Expres sao de Crescimento Aresta: 4+3 t Início em t=

1

Estrutura Repetitiva

12

3

4 5

Análise do Ciclo das Estruturas Repetitivas

- Estrutu ra 1 => Ciclo: 1 Inicio e m t = 2

REGRA ELE ME NTA R 192

Grafo em Evolução

GRAFO T COMUM GRAFO T +1 ESTR.ADIC. ESTR.EXCLUÍDA

1

2

3

1

2

3

1

2

3

4

1

2

3

4

1

2

3

117

1

2

3

4

1

2

3

4

1

2

3

4

5

1

2

3

4

5

1

2

3

4

1

2

3

4

5

12

3

4

5

12

3

4

5

6

12

3

4

5

6

1

2

3

4

5

12

3

4

5

6

1

2

3

4

5

6

1

2

3

4

5

6

7

1

2

3

4

5

6

7

12

3

4

5

6

1

2

3

4

5

6

7

1

2

3

4

5

6

7

1

2

3

4

5

6

7

8

1

2

3

4

5

6

7

8

1

2

3

4

5

6

7

1

2

3

4

5

6

7

8

1

2

3

4

5

6

7

8

1

2

3

4

5

6

7

8

9

1

2

3

4

5

6

7

8

9

1

2

3

4

5

6

7

8

1

2

3

4

5

6

7

8

9

1

23

4

5

6

7

8

9

1

23

4

5

6

7

8

9

10

1

23

4

5

6

7

8

9

10

1

2

3

4

5

6

7

8

9

Análise do Crescimento

- Crescim en to Linear: Sim

- Expres sao de Crescimento Nó: 2+t Início e m t= 1

- Expres sao de Crescimento Aresta: 4+t Início em t= 1

118

Estrutura Repetitiva

1

2 3

Análise do Ciclo das Estruturas Repetitivas

- Estrutu ra 1 => Ciclo: 1 Inicio e m t = 2

REGRA ELE ME NTA R 196

Grafo em Evolução

GRAFO T COMUM GRAFO T +1 ESTR.ADIC. ESTR.EXCLUÍDA

1

2

3

4

1

2

3

4

1

2

3

4

5

1

2

3

4

5

1

2

3

4

1

2

3

4

5

12

3

4

5

12

3

4

5

6

12

3

4

5

6

1

2

3

4

5

119

12

3

4

5

6

1

2

3

4

5

6

1

2

3

4

5

6

7

1

2

3

4

5

6

7

12

3

4

5

6

1

2

3

4

5

6

7

1

2

3

4

5

6

7

1

2

3

4

5

6

7

8

1

2

3

4

5

6

7

8

1

2

3

4

5

6

7

1

2

3

4

5

6

7

8

1

2

3

4

5

6

7

8

1

2

3

4

5

6

7

8

9

1

2

3

4

5

6

7

8

9

1

2

3

4

5

6

7

8

1

2

3

4

5

6

7

8

9

1

23

4

5

6

7

8

9

1

23

4

5

6

7

8

9

10

1

23

4

5

6

7

8

9

10

1

2

3

4

5

6

7

8

9

1

23

4

5

6

7

8

9

10

1

2

3

4

5

6

7

8

9

10

1

2

3

4

5

6

7

8

9

10

11

1

2

3

4

5

6

7

8

9

10

11

1

23

4

5

6

7

8

9

10

Análise do Crescimento

- Crescim en to Linear: Sim

- Expres sao de Crescimento Nó: 3+t Início e m t= 1

- Expres sao de Crescimento Aresta: 5+2 t Início em t=

1

Estrutura Repetitiva

120

1

2

3

4

Análise do Ciclo das Estruturas Repetitivas

- Estrutu ra 1 => Ciclo: 1 Inicio e m t = 2

REGRA ELE ME NTA R 212

Grafo em Evolução

GRAFO T COMUM GRAFO T +1 ESTR.ADIC. ESTR.EXCLUÍDA

1

2

3

4

5

6

7

8

1

2

3

4

5

6

7

8

1

2

3

4

5

6

7

8

9

10

11

12

1

2

3

4

5

6

7

8

9

10

11

12

1

2

3

4

5

6

7

8

1

2

3

4

5

6

7

8

9

10

11

12

1

2

3

4

5

6

7

8

9

10

11

12

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

1

2

3

4

5

6

7

8

9

10

11

12

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

1

2

3

4

5

6

7

8

9

0

11

12

13

14

15

16

17

18

19

20

1

2

3

4

5

6

7

8

9

0

1

12

13

14

15

16

17

18

19

20

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

121

1

2

3

4

5

6

7

8

9

0

11

12

13

14

15

16

17

18

19

20

1

2

3

4

5

6

7

8

9

0

11

12

13

14

15

16

17

18

19

20

1

2

3

4

5

6

7

8

9

10

1

2

3

14

15

16

17

18

19

20

21

22

23

24

1

2

3

4

5

6

7

8

9

10

1

2

3

14

15

16

17

18

19

20

21

22

23

24

1

2

3

4

5

6

7

8

9

0

11

12

13

14

15

16

17

18

19

20

1

2

3

4

5

6

7

8

9

10

1

2

3

14

15

16

17

18

19

20

21

22

23

24

1

2

3

4

5

6

7

8

9

10

1

2

3

14

15

16

17

18

19

20

21

22

23

24

1

2

3

4

5

6

7

8

9

10

11

12

3

4

5

16

17

18

19

20

21

22

23

24

25

26

27

28

1

2

3

4

5

6

7

8

9

10

11

12

3

4

5

16

17

18

19

20

21

22

23

24

25

26

27

28

1

2

3

4

5

6

7

8

9

10

1

2

3

14

15

16

17

18

19

20

21

22

23

24

1

2

3

4

5

6

7

8

9

10

11

12

3

4

5

16

17

18

19

20

21

22

23

24

25

26

27

28

1

2

3

4

5

6

7

8

9

10

11

12

3

4

5

16

17

18

19

20

21

22

23

24

25

26

27

28

1

2

3

4

5

6

7

8

9

10

11

12

13

14

5

6

7

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

1

2

3

4

5

6

7

8

9

10

11

12

13

14

5

6

7

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

1

2

3

4

5

6

7

8

9

10

11

12

3

4

5

16

17

18

19

20

21

22

23

24

25

26

27

28

1

2

3

4

5

6

7

8

9

10

11

12

13

14

5

6

7

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

1

2

3

4

5

6

7

8

9

10

11

12

13

14

5

6

7

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

7

8

9

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

6

7

8

9

0

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

1

2

3

4

5

6

7

8

9

10

11

12

13

14

5

6

7

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

Análise do Crescimento

- Crescim en to Linear: Sim

- Expres sao de Crescimento Nó: 4 (1+t) Iníc io em t= 1

- Expres sao de Crescimento Aresta: 8+6 t Início em t=

1

Estrutura Repetitiva

122

1

2

3

4

5

6

7

8

9

10

Análise do Ciclo das Estruturas Repetitivas

- Estrutu ra 1 => Ciclo: 1 Inicio e m t = 2

REGRA ELE ME NTA R 224

Grafo em Evolução

GRAFO T COMUM GRAFO T +1 ESTR.ADIC. ESTR.EXCLUÍDA

1

2

3

4

1

2

3

4

1

2

3

4

5

1

2

3

4

5

1

2

3

4

1

2

3

4

5

1

2

3

4

5

12

3

4

5

6

12

3

4

5

6

1

2

3

4

5

12

3

4

5

6

1

2

3

4

5

6

1

2

3

4

5

6

7

1

2

3

4

5

6

7

12

3

4

5

6

123

1

2

3

4

5

6

7

1

2

3

4

5

6

7

1

2

3

4

5

6

7

8

1

2

3

4

5

6

7

8

1

2

3

4

5

6

7

1

2

3

4

5

6

7

8

1

2

3

4

5

6

7

8

1

2

3

4

5

6

7

8

9

1

2

3

4

5

6

7

8

9

1

2

3

4

5

6

7

8

1

2

3

4

5

6

7

8

9

1

23

4

5

6

7

8

9

1

23

4

5

6

7

8

9

10

1

23

4

5

6

7

8

9

10

1

2

3

4

5

6

7

8

9

1

23

4

5

6

7

8

9

10

1

2

3

4

5

6

7

8

9

10

1

2

3

4

5

6

7

8

9

10

11

1

2

3

4

5

6

7

8

9

10

11

1

23

4

5

6

7

8

9

10

Análise do Crescimento

- Crescim en to Linear: Sim

- Expres sao de Crescimento Nó: 3+t Início e m t= 1

- Expres sao de Crescimento Aresta: 6+t Início em t= 1

Estrutura Repetitiva

124

1

2

3

Análise do Ciclo das Estruturas Repetitivas

- Estrutu ra 1 => Ciclo: 1 Inicio e m t = 2

REGRA ELE ME NTA R 232

Grafo em Evolução

GRAFO T COMUM GRAFO T +1 ESTR.ADIC. ESTR.EXCLUÍDA

1

23

4

5

6

7

8

9

10

1

2

3

4

5

6

7

8

9

10

1

2

34

5

6

7

8

9

10

11

12

13

14

1

2

34

5

6

7

8

9

10

11

12

13

14

1

23

4

5

6

7

8

9

10

1

2

34

5

6

7

8

9

10

11

12

13

14

1

2

3

4

5

6

7

8

9

10

11

12

13

14

1

2

3

45

6

7

8

9

10

11

12

13

14

15

16

17

18

1

2

3

45

6

7

8

9

0

11

12

13

14

15

16

17

18

1

2

34

5

6

7

8

9

10

11

12

13

14

1

2

3

45

6

7

8

9

10

11

12

13

14

15

16

17

18

1

2

3

45

6

7

8

9

10

11

12

13

14

15

16

17

18

1

2

3

4

56

7

8

9

0

1

2

13

14

15

16

17

18

19

20

21

22

1

2

3

4

56

7

8

9

0

1

2

13

14

15

16

17

18

19

20

21

22

1

2

3

45

6

7

8

9

10

11

12

13

14

15

16

17

18

125

1

2

3

4

56

7

8

9

10

1

12

13

14

15

16

17

18

19

20

21

22

1

2

3

4

56

7

8

9

0

1

2

13

14

15

16

17

18

19

20

21

22

1

2

3

4

5

67

8

9

10

11

2

3

4

15

16

17

18

19

20

21

22

23

24

25

26

1

2

3

4

5

67

8

9

10

11

2

3

4

15

16

17

18

19

20

21

22

23

24

25

26

1

2

3

4

56

7

8

9

10

1

12

13

14

15

16

17

18

19

20

21

22

1

2

3

4

5

67

8

9

10

11

2

3

4

15

16

17

18

19

20

21

22

23

24

25

26

1

2

3

4

5

67

8

9

10

11

2

3

4

15

16

17

18

19

20

21

22

23

24

25

26

1

2

3

4

5

6

78

9

10

11

12

13

4

5

6

17

18

19

20

21

22

23

24

25

26

27

28

29

30

1

2

3

4

5

6

78

9

10

11

12

13

4

5

6

17

18

19

20

21

22

23

24

25

26

27

28

29

30

1

2

3

4

5

67

8

9

10

11

2

3

4

15

16

17

18

19

20

21

22

23

24

25

26

1

2

3

4

5

6

78

9

10

11

12

13

4

5

6

17

18

19

20

21

22

23

24

25

26

27

28

29

30

1

2

3

4

5

6

78

9

10

11

12

13

4

5

6

17

18

19

20

21

22

23

24

25

26

27

28

29

30

1

2

3

4

5

6

7

89

10

11

12

13

14

15

6

7

8

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

1

2

3

4

5

6

7

89

10

11

12

13

14

15

6

7

8

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

1

2

3

4

5

6

78

9

10

11

12

13

4

5

6

17

18

19

20

21

22

23

24

25

26

27

28

29

30

1

2

3

4

5

6

7

89

10

11

12

13

14

15

6

7

8

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

1

2

3

4

5

6

7

89

10

11

12

13

14

15

6

7

8

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

1

2

3

4

5

6

7

8

910

11

12

13

14

15

16

17

8

9

0

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

1

2

3

4

5

6

7

8

910

11

12

13

14

15

16

7

8

9

0

1

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

1

2

3

4

5

6

7

89

10

11

12

13

14

15

6

7

8

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

Análise do Crescimento

- Crescim en to Linear: Sim

- Expres sao de Crescimento Nó: 6+4 t Início em t= 1

- Expres sao de Crescimento Aresta: 6 (2 +t) Iní cio em

t= 1

Estrutura Repetitiva

126

1

2

34

5

6

7

8

9

10

11

12

Análise do Ciclo das Estruturas Repetitivas

- Estrutu ra 1 => Ciclo: 1 Inicio e m t = 2

----------------------------------------------------------

------------------------

--

QUADRO R ESU MO

--

----------------------------------------------------------

------------------------

REGRAS:

{11,14,23,35,43,50,56,70,81,98,113,128,132,136,140,142,162

,168,172,176,184,192,196,212,224,232}

EXPRESSÃO DE CRESCIMENTO DE NOS E AR ESTA S

Regras c om Crescimento Linear:

{0,0,23,0,43,50,56,70,81,98,113,128,132,136,140,142,162,16

8,172,176,184,192,196,212,224,232}

Regras c om Crescimento Não Linear: {11,14,35}

127

CICLO DE REPETIÇÃO

Regras c om Ciclo Simples desde t=1 (pura men te linear):

{23,43,113,128,132,136,140,142,162,168,176,184,192,196,212

,224,232}

Regras c om Ciclo Simples após um dado t : {56,98,172}

Regras c om Ciclo Duplo: {11,14,35,50,70}

Regras S EM Ciclo: {81}

Regra: 1 1 Ciclo: {0,2}

Regra: 1 4 Ciclo: {0,2}

Regra: 2 3 Ciclo: {1}

Regra: 3 5 Ciclo: {0,2}

Regra: 4 3 Ciclo: {1}

Regra: 5 0 Ciclo: {0,2}

Regra: 5 6 Ciclo: {0,1}

Regra: 7 0 Ciclo: {0,2}

Regra: 8 1 Ciclo: {0}

Regra: 9 8 Ciclo: {0,1}

Regra: 1 13 Ciclo: {1}

Regra: 1 28 Ciclo: {1}

Regra: 1 32 Ciclo: {1}

Regra: 1 36 Ciclo: {1}

Regra: 1 40 Ciclo: {1}

Regra: 1 42 Ciclo: {1}

Regra: 16 2 Ciclo: {1}

Regra: 1 68 Ciclo: {1}

Regra: 1 72 Ciclo: {0,1}

Regra: 1 76 Ciclo: {1}

Regra: 1 84 Ciclo: {1}

Regra: 1 92 Ciclo: {1}

Regra: 1 96 Ciclo: {1}

Regra: 2 12 Ciclo: {1}

Regra: 2 24 Ciclo: {1}

Regra: 23 2 Ciclo: {1}

128

Referências Bibliográficas

[Berlekamp, Conway e Guy, 1992] E. Berl ekamp, J. Conway e R. Guy.

Winning for your

mathematical pla ys

, 1992

[Burks, 1970] A. W. Burks.

Essays on Cellular Automata.

Urbana-Champai gn, IL:

University of Illinois Pr ess, 1970.

[Cook, 2004] M. Cook. "U niversality in Elementary Cel lular Automata. "

Complex

Systems

15, 1-40, 2004.

[Hanson e Crutchfield, 1992] J.E. Hanson e J.P. Crutchfield. “The attractor-basin portrait

of a cellular automaton”,

Journal of Statistical Physics

, 66:1415-1462, 1992.

[Hanson, 1993] J.E. H anson. “C omputational mechanics of cellular automata”.

University

of California,

Berkeley, 1993.

[Hopcroft, Motwani e Ullm an, 2001] J.E. Hopcroft, R. M otwani e J.D. Ullm an.

Introduction to automata theory, languages, an d computation

, Addison-Wesley,

2001.

[Hurd, 1987] L.P. Hurd. “Formal language characterizations o f cellular autom aton limit

sets”.

Complex Systems

, 1:69-80, 1 987.

[Kari, 2005] J. Kari. “Theory of cell ular automata: A survey”,

Theoretical Comput er

Science

, 334:3-33, 2005.

[Li e Packard,1 990] W. Li e N.Packard. “The Structure of Element ary Cellular Automata

Rule Space”.

Complex Systems

, 4:281-297, 1990

[Mitchell and Crut chfield, 1995] M. Mitchell e J.P . Crutchfield. “Evol ution of emergent

computation ”.

SFI Technical R epo rt

94-03-012, 1995.

[Oliveira, 2003] G. M.B. de Oliveira. “Autômatos Celulares: aspectos dinâmicos e

computacionai s”.

Mini-cursos de intel igência artificial, Anais do XXIII Congresso

da Sociedade Brasil eira da Com putação,

CD-ROM, Campinas, 2003

[Sarkar, 200 0] P. Sarkar. “A b rief h istory of c ellular automata”.

ACM Computing Sur veys

,

32(1):80-107, 2000.

[Sutner, 2003] K. Sutner. “Cellular Automata and FSMs”, Carnegie Mellon University,

2003.

[Sutner, 2006] K. Sutner, “Cellular Automat a Package”, Wo lfram Research

Home-page, http://library.wolfram. com/infocenter.

129

Último acesso em junho de 2006.

[Trafaniuc, 2004] V.V.Trafaniuc, “Caracterização computacional do comportamento

limite de alguns autômatos celulares elementares”,

Dissertação de Mestrado em

Engenharia Elétr ica – Universidade Mackenzie

, 2004.

[von Neumann e Burks, 19 66] J. v. Neumann, A. Burks .

Theory of Self-Reproducing

Automata

. University of Illinois Press, 1966

[Wolfram, 1983a] S. Wolfram. “Cellular Automata”.

Los Alamos Science

, 9:2-21, Fall

1983.

[Wolfram, 1983b] S . Wolfram. “Statistical mechanics of cellular automata.”

Rev. Modern

Physics

, 55:601-644, 1983.

[Wolfram, 1984a] S. Wolfram. “Computation theory of cellular aut omata”.

Communications in Mathematical Physics

, 96:15-57, 198 4. Rep ublicado em: S.

Wolfram (ed.),

Theory and applications of cellular automata

, World Scient ific,

Singapo re, 189-231, 1986.

[Wolfram, 1984b] S. Wolfram. “Universality and Complexity in Cellular Automata”.

Physica D

, 10:1-35, 1984.

[Wolfram, 1988] S. Wolfram . “Complex Systems Theor y: Emergent Syntheses in

Science”.

Founding Workshops of the Santa Fe Institute

. Santa Fe: Santa Fe

[Wolfram, 1994 ] S. Wolfram.

Cellular automata and complexity

, Perseus Publishing,

1994.

[Wolfram, 2002] S. Wolfram.

A New kind of science

, Wolfram Media, 2002.

[Wolfram, 2003] S. Wolfram.

The Mathematica Book

, Wolfram Media, 2003.

Livros Grátis
( http://www.livrosgratis.com.br )
 
Milhares de Livros para Download:
 
Baixar livros de Administração
Baixar livros de Agronomia
Baixar livros de Arquitetura
Baixar livros de Artes
Baixar livros de Astronomia
Baixar livros de Biologia Geral
Baixar livros de Ciência da Computação
Baixar livros de Ciência da Informação
Baixar livros de Ciência Política
Baixar livros de Ciências da Saúde
Baixar livros de Comunicação
Baixar livros do Conselho Nacional de Educação - CNE
Baixar livros de Defesa civil
Baixar livros de Direito
Baixar livros de Direitos humanos
Baixar livros de Economia
Baixar livros de Economia Doméstica
Baixar livros de Educação
Baixar livros de Educação - Trânsito
Baixar livros de Educação Física
Baixar livros de Engenharia Aeroespacial
Baixar livros de Farmácia
Baixar livros de Filosofia
Baixar livros de Física
Baixar livros de Geociências
Baixar livros de Geografia
Baixar livros de História
Baixar livros de Línguas

Baixar livros de Literatura
Baixar livros de Literatura de Cordel
Baixar livros de Literatura Infantil
Baixar livros de Matemática
Baixar livros de Medicina
Baixar livros de Medicina Veterinária
Baixar livros de Meio Ambiente
Baixar livros de Meteorologia
Baixar Monografias e TCC
Baixar livros Multidisciplinar
Baixar livros de Música
Baixar livros de Psicologia
Baixar livros de Química
Baixar livros de Saúde Coletiva
Baixar livros de Serviço Social
Baixar livros de Sociologia
Baixar livros de Teologia
Baixar livros de Trabalho
Baixar livros de Turismo
 
 