AUTOMI CELLULARI
Definizione e proprietà
AUTOMI CELLULARI
Un automa cellulare è un sistema dinamico discreto
formato da un numero finito di unità che
interagiscono tra loro.
Tempo
Tempo
Spazio
Stato del sistema
Discreto
AUTOMI CELLULARI
Un automa cellulare può essere visto come una rete
finita di piccoli e identici automi finiti
Automa elementare
Variabile
Spazio Euclideo
d-dimensionale
d=2
d=1
d = 1, 2, 3
AUTOMI CELLULARI
L’evoluzione del sistema è dovuta alla funzione di
transizione
 : Sn  S
N° vicini della cella
Insieme degli stati
interni
Si ,t 1   ( Si,t )
CARATTERISTICHE DEI AC

Caratteristiche essenziali:
 Spazio,
tempo e stati sono discreti
 Le
leggi sono uniformi: uguali per tutte le celle
 Le
leggi sono locali: dipendono solo dalle celle vicine
 Il
tempo avanza simultaneamente per ogni cella
PROPRIETA’ DEGLI AC

Geometria della matrice delle celle:
PROPRIETA’ DEGLI AC

Vicinato di ogni cella:
Von Neumann
Moore
Generico
PROPRIETA’ DEGLI AC

Numero di stati per cella:
 Binario
due stati per cella
 Codificabile con un byte
28=256 stati per cella
 Complessità notevole

Varietà di regole di transizione:
 N°
di regole necessarie per stabilire il prossimo stato di
una cella cresce esponenzialmente rispetto al n° dei
possibili stati della cella.
Esempio
65.536 (216)
Von Neumann (n=4)
k
Automa binario
Moore (n=8)
kn
Possibili regole
1077
Simulazione di fenomeni complessi
Campi di applicazione
Simulazione di fenomeni complessi


Gli automi cellulari è uno strumento utile ed efficiente
per studiare e simulare molti problemi perché
sostituiscono sistemi di equazioni differenziali
I campi di applicazioni sono:
 Fisica,
chimica: fluidodinamica, reazioni chimiche
 Biomedicina: AIDS, cancro
 Geologia: lave, frane, terremoti, incendi boschivi
 Pianificazione territoriale: sviluppo urbano, traffico
 Economia: simulazione dei mercati
 Ecologia: inquinamento, biorisanemento dei suoli
 Altro….