Automata Celular

Universidad De Oriente
Núcleo De Anzoátegui
Escuela de Ingeniería y Ciencias Aplicadas
Departamento de Computación y Sistemas
Teoría de la Información y de la Codificación

Profesor: Bachiller:

José Luis Bastardo Jesús Tenías C.I: 20.360.475


Barcelona, 06 de Agosto del 2012
1. Investigación Teórica

1.1 Autómatas celulares:
Para empezar podemos definir al autómatacelular como:

“Un sistema dinámico donde el espacio y el tiempo son discretos. Describe la evolución de un sistema espacialmente explícito en función de un conjunto de reglas de evolución de estado, que determinan el cambio de estado de cada celda que constituye el espacio, en función de su propio estado y el estado de un conjunto de celdas vecinas“
Los autómatas celulares pueden ser usadospara modelar numerosos sistemas físicos que se caractericen por un gran número de componentes homogéneos y que interactúen localmente entre sí. Algunos ejemplos de áreas en donde se utilizan los autómatas celulares son:
* Modelado del flujo de tráfico y de peatones.
* Modelado de fluidos (gases o líquidos).
* Modelado de la evolución de células o virus como el VIH.

2. Planteamientodel problema:
2.1 Planteamiento abstracto y general del problema: Los autómatas celulares son utilizados para modelar sistemas, como interacciones entre partículas, formación de galaxias, cinética de sistemas moleculares y crecimiento de cristales, así como diversos sistemas biológicos a nivel celular, multicelular y poblacional. El modelado de la configuración del sistema y el proceso de cambiodel mismo se caracteriza por:

1. Un espacio formado por un conjunto finito de celdas distribuidas en una rejilla regular n-dimensional, comúnmente una matriz. Si el autómata es unidimensional las celdas se distribuyen a lo largo de una línea, si es bidimensional las celdas se pueden distribuir a través de una rejilla plana que puede ser triangular, rectangular, cuadrada, hexagonal, etc.2. Cada celda puede estar en un único estado en determinado instante de tiempo. Este estado debe estar definido en un conjunto de estado asociado al espacio del autómata.

3. El estado de las celdas cambia de un instante a otro de acuerdo a un conjunto de reglas de evolución comunes a todas las celdas.

4. Estas reglas son especificadas en una tabla de reglas (también conocida comofunción de transición), con una entrada para todas las posibles configuraciones del vecindario.

5. El vecindario de una celda esta formado por las celdas adyacentes y se define igual para todas las celdas del autómata.

2.1 Planteamiento Concreto del problema: El problema concreto planteado en clases es el siguiente (algunos aspectos, como por ejemplo el tamaño de la matriz, fueron dejados acriterio del estudiante):

Dadas una matriz de 104x104 elementos binarios cuya configuración inicial es fija (caracterizada por tener una entropía igual a 1), y un conjunto de 3 reglas de evolución, que serán aplicadas en orden, donde cada regla se aplicara primero bajo la consideración “matriz par” y luego “matriz impar”, y a su vez dicho conjunto de reglas es “reversible” (se puede calcular laregla inversa y obtener la matriz original); se debe permitir al usuario (profesor) escoger el conjunto de reglas, y la cantidad de veces que serán aplicadas, luego realizar este proceso y visualizar la matriz resultante, a la cual se le cambiara el valor de un bit con un click del mouse, y luego se aplicaran las reglas inversas, para apreciar que tan distorsionada queda la imagen inicial, y paradeterminar si la variación tiene alguna relación con el bit que se escoja.

3. Descripción de la solución:
Para conseguir la solución al problema propuesto, se implemento un algoritmo autómata celular con las siguientes características:

* La codificación de la regla usada es una cadena de 16 caracteres hexadecimales.
* El conjunto de reglas está formado por 3 reglas, cada una con su...