Publicação: Algoritmo de Lempel-Ziv aplicado à classificação quantitativa de
autômatos celulares
Carregando...
Tipo do documento
Data
Direito de acesso
Coleções
Área do conhecimento
CNPQ::CIENCIAS EXATAS E DA TERRA::FISICA
Título da Revista
ISSN da Revista
Título de Volume
Autores
Orientador
Coorientador
Rams, Ernesto Estévez
Resumo
O trabalho apresenta os chamados Autômatos Celulares Elementares de acordo
com os princípios do algoritmo de Lempel-Ziv (LZ76) aplicado a sequências binárias.
Tal descrição visa a organização quantitativa desses autômatos de acordo com a
complexidade de atualização dos estados, relacionando os arranjos com a Classificação
de Wolfram em função de valores numéricos sugeridos. É possível, dessa forma,
discriminar tais máquinas em Classes de Complexidade. Ainda, serão discorridas as
chamadas Sequências de Máxima Complexidade MLZs e suas propriedades; estas
serão úteis na caracterização de emissões ergódicas verdadeiramente randômicas, e,
portanto, na compreensão do grau de aleatoriedade das regras aplicadas aos autômatos.
Esta teoria será apresentada como fundamentação para um novo tratamento de
problemas de defeitos em sólidos cristalograficamente complexos (ordem atômica
intermediária entre a cristalinidade ideal de longo alcance e a amorficidade), utilizando
métodos da Teoria da Informação.
Abstract
This work presents the so-called elementary Cellular Automata according to the
principles of the Lempel-Ziv (LZ76) algorithm applied to binary sequences. We aim at
organizing them quantitatively in agreement with the complexity of updating the states,
and by relating the data arrangements to the Wolfram s Classification. In this way,
Complexity Classes can classify such machines. Further, sequences with maximum LZ
complexity - MLZs - and their properties will be presented and discussed. The latter
will be useful to characterize the truly random ergodic emissions, thus to understand the
degree of randomness of the rules governing automata. The above treatment will be
extended to problems of crystal defects in crystallographically challenging solids (with
intermediate atomic order between the ideal long-range crystallinity and amorphicity),
by using tools from information theory.
Palavras-chave
Autômatos celulares, Complexidade de Lempel-Ziv, Fonte
ergódica, Teoria da informação, Entropia algorítmica, Sólidos complexos, Cristalografia, Dimensão fractal, Fatorização, Aleatoriedade, Cadeias de dados, Cellular automata, Lempel-Ziv complexity, Ergodic source, Information theory, Algorithmic entropy, Crystallography, Crystallographically challenging solids, Fractal dimension, Factorization, Randomness, Strings
Citação
NUNES, Ciro Alves Justino. Algoritmo de Lempel-Ziv aplicado à classificação quantitativa de
autômatos celulares. 2014. 127 f. Dissertação (Mestrado em Ciências Exatas e da Terra) - Universidade Federal de Uberlândia, Uberlândia, 2014. DOI https://doi.org/10.14393/ufu.di.2014.528