Autòmat cel·lular: diferència entre les revisions
Contingut suprimit Contingut afegit
mCap resum de modificació |
Expansió del contingut a partir de les versions en castellà i anglès |
||
Línia 3:
Un '''autòmat cel·lular''' (A.C.) és un [[model matemàtic]] per a un [[sistema dinàmic]] que evoluciona en passos discrets. És adequat per modelar sistemes naturals que puguin ser descrits com una col·lecció massiva d'objectes simples que [[Interaccions fonamentals|interaccionin]] localment uns amb els altres.
Són sistemes descoberts dins de l'àmbit del camp de la [[física computacional]] per [[John von Neumann]]
== Descripció ==
No hi ha una definició formal i matemàtica acceptada
* Una ''[[Reticle (ordre)|reixeta]]'' o ''quadriculat'' de nombres enters (conjunt <math>\mathbb{Z}</math>) infinitament estesa, i amb ''dimensió'' <math>d \in \mathbb{Z}^+</math>. Cada cel·la de la quadrícula rep el nom de ''cèl·lula''.
* Cada cèl·lula pot prendre un valor en <math>\mathbb{Z}</math> a partir d'un ''conjunt finit d'estats'' <math>k</math>.
* Cada cèl·lula, a més, es caracteritza pel seu ''[[Veïnat (matemàtiques)|veïnatge]]'', un conjunt finit de cèl·lules als seus voltants.
* D'acord amb això, s'aplica a totes les cèl·lules de la quadrícula una ''funció de transició'' ( <math>f</math> ) que pren com arguments els valors de la cèl·lula en qüestió i els valors de les cel·les veïnes, i torna el nou valor que la cèl·lula tindrà en la següent etapa de temps. Aquesta funció <math>f</math> s'aplica de forma homogènia a totes les cèl·lules per cada pas discret de temps.
=== Condicions de frontera ===
Per definició, un autòmat cel·lular consisteix en una [[Reticle (ordre)|retícula]] infinita d'enters. Tot i això, per qüestions pràctiques (com en models de sistemes físics duts a terme en ordinadors de memòria finita), es requereix prendre certes consideracions a l'hora d'implementar un autòmat. Per aquest motiu, la definició original es modifica per donar cabuda a retícules finites en les que les cèl·lules de l'autòmat interactuïn. Això comporta la consideració extra del que ha de succeir en aquelles cèl·lules que es trobin als marges de la retícula, el que es coneix com '''condició de frontera'''.
Es poden implementar diverses condicions de frontera, en funció d'allò que el problema real requereixi pel seu modelat. Per exemple:
* '''Frontera oberta.''' Fora de la graella hi resideixen cèl·lules, totes amb un valor fix. En el cas particular del [[joc de la vida]] i altres autòmats similars amb dos estats al seu conjunt <math>k</math>, una frontera s'anomena "freda" si les cèl·lules fora de la graella es consideren mortes, i "calenta" si es consideren vives.
* '''Frontera periòdica.''' Es considera que la graella té una propietat [[Toroide|toroidal]], com si els seus extrems es toquessin. Per tant, si una cèl·lula surt de la graella, reapareix pel costat oposat.
* '''Frontera reflectora.''' Les cèl·lules de fora la graella reflecteixen els valors de les de les de dins. Així, una cèl·lula que toqués la frontera per fora agafaria com a valor el de la cèl·lula que toca la frontera per dins.
* '''Sense frontera.''' Fent ús d'implementacions que facin créixer dinàmicament l'ús de memòria de la graella implementada, es pot assumir que cada vegada que les cèl·lules han d'interactuar amb les de fora de la graella, aquesta es fa més gran per dur a terme aquestes interaccions. Tot i tendir a infinit, degut a que la frontera inicial és finita no és equivalent a la definició general de l'autòmat cel·lular, perquè en aquest cas no pots activar qualsevol cèl·lula de la graella des del principi.
=== Variacions ===
Alguns autòmats cel·lulars tenen graella triangular o hexagonal enlloc de rectangular. També existeixen versions tridimensionals o amb moltes més dimensions, com en el cas dels [[Autòmat cel·lular quàntic|autòmats cel·lulars quàntics]]. Altres possibles variacions són augmentar el nombre d'estats <math>k</math> que cada cèl·lula pot tenir (com en el cas dels [[Autòmat cel·lular totalista|autòmats cel·lulars totalistes]]), la funció de transició <math>f</math> de manera que ja no sigui homogènia, utilitzar [[Estocàstic|elements estocàstics]] (aleatorietat) en <math>f</math> (el que es coneix com [[autòmat cel·lular probabilístic]]) o variar els veïnatges de cada cèl·lula.
== Aplicacions ==
Linha 23 ⟶ 38:
* Modelat de processos de [[percolació]].
== Exemples d'autòmats cel·lulars ==
=== Autòmat cel·lular unidimensional ===
[[Fitxer:One-d-cellular-automate-rule-30.gif|miniatura|Animació que mostra la manera com les normes d'un autòmat cel·lular unidimensional deteminen la següent generació.]]
L'exemple més bàsic d'autòmat cel·lular no trivial és la versió [[unidimensional]]. Es defineix una seqüència de cèl·lules que només poden tenir dos estats, i es llegeixen ordenadament aplicant canvis segons l'estat de la cèl·lula i les seves veïnes (cèl·lula anterior i posterior). El resultat es sol mostrar com una nova línia a sota de l'actual que serà la llegida a continuació, i aquest procés es va repetint. El conjunt de normes que defineix el valor de la nova cèl·lula segons els estats de les cèl·lules comprovades s'anomena ''Rule Set'', i hi ha 256 casos diferents.
Per comprovar l'efecte al llarg del temps d'un determinat ''Rule Set'', s'aplica a una seqüència senar de cèl·lules on totes estan desactivades excepte la del mig. A partir d'aquesta configuració inicial, els ''Rule Sets'' es poden classificar en [[Quiralitat (geometria)|amfiquirals]] o no amfiquirals segons si el patró format és simètric. A més, els patrons obtinguts es poden classificar en:
* '''Uniformes.''' Es genera un patró pla, on totes les cel·les acaben tenint el mateix estat. Exemple: ''Rule 222''.
* '''Oscil·lants.''' Es tendeix a un patró regular, per exemple [A, A, B, A, A, B ...] en el cas de ''Rule 190''.
* '''Atzarosos.''' S'obté un patró de pseudo-aleatorietat. Exemple: ''Rule 30''.
* '''Complexes.''' S'obtenen patrons regulars complexes, per exemple el ''Rule 110''. Un altre exemple intessant és el ''Rule 90'', on s'obté un patró similar al [[Triangle de Sierpinski]].
{{AP|Joc de la vida}}
El '''joc de la vida''' és un autòmat [[ortogonal]] [[bidimensional]] bàsic, creat per [[John Horton Conway]] el 1970. A cada unitat de temps, es donen les següents transicions:
# Tota cel·la viva amb menys de dos veïns vius mor (de ''solitud'').
# Tota cel·la viva amb més de tres veïns vius mor (de ''sobreconcentració'').
# Tota cel·la viva amb dos o tres veïns vius, segueix viva per a la següent generació.
# Tota cel·la morta amb exactament tres veïns vius torna a la vida.
{{AP|Formiga de Langton}}
La '''formiga de Langton''' és un autòmat ortogonal bidimensional creat per [[Chris Langton]]. En aquest cas es defineix una cel·la especial que actua de formiga que es va desplaçant, i al fer-ho modifica els estats de les altres cel·les (al trepitjar una cel·la activada la desactiva, i al revés). La direcció de la formiga depèn de l'estat de la cel·la actual a la que es troba, si està activada fa un gir a dreta, si està desactivada fa un gir a l'esquerra.
Tot això és recreable com un autòmat normal definint més estats <math>k</math> possibles per cada cèl·lula, segons si s'hi troba la formiga, segons la direcció d'aquesta i segons si la casella a la que es troba està activada o desactivada.
{{AP|Model Nagel-Schreckenberg}}
El '''model Nagel-Schreckenberg''' és un [[autòmat cel·lular probabilístic]] unidimensional creat per [[Kai Nagel]] i [[Michael Schreckenberg]] que serveix de model simple de [[trànsit vehicular]]. En aquest cas el que varia segons els vehicles veïns és la velocitat del vehicle, i a més hi ha una certa probabilitat de que el vehicle freni sense un motiu aparent.
{{AP|Autòmat d'Ulam–Warburton}}
L''''autòmat d'Ulam–Warburton''' (''UWCA'') és un autòmat ortogonal bidimensional que té la particularitat de que les cel·les activades no es poden tornar a desactivar. A cada iteració s'activen les cel·les inactivades en què només un dels costats és adjacent ortogonalment a una d'activada.
== Referències ==
▲* [[Joc de la vida]]
{{referències}}
▲* [[Model Nagel-Schreckenberg]]
▲* [[Formiga de Langton]]
▲* [[Autòmat d'Ulam–Warburton]]
== Vegeu també ==
Linha 43 ⟶ 89:
* [https://web.archive.org/web/20080907225701/http://yupana.autonoma.edu.co/publicaciones/yupana/005/autocelular/Automatas.html Una Introducción a los Autómatas Celulares], arxivat de l'[http://yupana.autonoma.edu.co/publicaciones/yupana/005/autocelular/Automatas.html original] {{es}}
* [http://delta.cs.cinvestav.mx/~mcintosh/oldweb/s1996/ponse/reporte.html Autómata Celular] {{es}}
* [https://mathworld.wolfram.com/ElementaryCellularAutomaton.html MathWorld - Elementary Cellular Automaton] - Llista de tots els ''Rule Sets'' en la versió unidireccional {{en}}
{{Autoritat}}
| |||