Teoría computación, celular autómata

PAUTA Control No. 1:
Teor´ de Computaci´n
ıa
o
Profesor: John Atkinson
Universidad de Concepci´n
o
Jueves 28 de Agosto del 2014

Preguntas
En general, los problemas de lasrespuestas en el control se deben principalmente a los siguientes aspectos:
1. Respuestas MUY gen´ricas que no dicen nada (y tampoco permiten
e
evaluar la comprensi´n del tema).
o2. Respuestas con mucho ’chamullo’ (sin comentarios!).
3. Respuestas no son auto-contenidas: se ’lanzan’ conceptos o frases sin
explicar y m´s encima contradictorias.
a
Espec´ıficamente, se debe considerar lo siguiente:
1. Describa DOS caracter´
ısticas propias de un Aut´mata Celular (CA)?
o
Un CA es una m´quina formada por ’celdas’ que se interconectan y
acuyas conductas individuales se basan en ’reglas’ que dependen de los
vecinos de estas, y que le permite a un CA ’evolucionar’ con el tiempo
dependiendo de las conexiones que tengansus unidades m´s simples
a
en un momento dado (y estas pueden cambiar!!). Se puede focalizar
en algunas de las propiedades importantes, tales como: localidad (reglas simples que seaplican a cada celda en funci´n de sus vecinos,
o
y que permite conductas m´s complejas), simplicidad en t´rminos de
a
e
reglas simples y conexi´n de celdas para generar patronesdin´micos
o
a
complejos, y paralelismo, que permite la realizaci´n (y aplicaci´n) sio
o
mult´nea de reglas que modifican el comportamiento de cada celda de
a
la m´quina (CA).
a2. ¿Cu´l es la diferencia entre un aut´mata finito y un CA?
a
o
Una de las diferencias posibles: En un FA, la salida de la m´quina en
a
cada instante depende de la entrada yestado actual. En cambio, para
un CA, la ’salida’ de cada unidad (celda) depende del estado actual
de sus celdas vecinas, lo que posibilita comportamiento din´mico.
a

2