8/14/2019 Automate Celulare
1/7
UNIVERSITATEA POLITEHNICA BUCURESTI
Facultatea de Electronica si Telecomunicatii
sectia Ingineria Sistemelor de Calcul
Automate celulare, structuri,
concepte fundamentale, aplicatii
Burgui Florin
8/14/2019 Automate Celulare
2/7
Florin Burgui Automate celulare, structuri, concepte fundamentale, aplicatii
2
1. Prezentare generala
Automatul celular este o constructie abstracta cu proprietati complexe si greu
accesibile. Este o aplicatie a calculatorului, un algoritm numeric realizat dintr-o retea decelule ale caror stari pot lua valori definite de o anumita lege. El a stat la baza aparitiei
calculatorului neuronal, a algoritmilor genetici si a vietii artificiale.
Automatele celulare au fost introduse (ca notiune) de Von Neumann si Ulam, initial
sub numele de spatii celulare , ca fiind cele mai bune modele pentru sistemele biologice si
auto-reproducerea biologica.
Stanislas Ulam era interesat in evolutia constructiilor grafice generate de reguli
simple. Baza acestor constructii era un spatiu bi-dimensional divizat in celule, un fel de grila.
Oricare din aceste celule putea avea doua stari: ON si OFF. Pornind de la acest tipar,
generatia urmatoare a primit si reguli legate de vecinatati. De exemplu, daca o celula era in
contact cu doua care erau pe ON, trecea si ea pe ON. Altfel, trecea in OFF. Ulam a observatca acest mecanism permite generarea unor figuri complexe, care, in anumite circumstante pot
deveni auto-reproductive. Intrebarea care se nastea era: poate acest mecanism sa explice
complexitatea realului? Aceasta complexitate este aparenta, regulile fundamentale fiind si ele
la randul lor foarte simple?
Pe aceeasi linie, Von Neumann era si el interesat de teoria automatelor auto-
reproductive, de a face o masina numita kinematon care sa se auto-reproduca. Ulam i-a
sugerat acestuia sa foloseasca spatiile celulare pentru o asemenea constructie.
Un fel de definitie formala (matematizata) o poate constitui tuplul (L, S, N, f), unde L
este aria ce cuprinde celulele, S este un set finit de stari ale celulelor, N vecinatatea si f
functia de tranzitie.
Pentru proiectarea unul automat celular este necesar sa cunoastem cateva
caracteristici. Dimensiunea este una dintre acestea. Din acest punct de vedere, cele mai
simple sunt cele uni-dimensionale. O alta etapa in proiectare este alegerea legi locale,
corespunzator careia o celula trece intr-o anumita stare. Un exemplu de lege este suma .
Adica starea la momentul k+1 este suma starilor la momentul k a vecinilor aflati la distanta r.
Conditiile initiale si conditiile pentru frontiere sunt, de asemenea, necesare proiectarii unui
automat celular.
2. Structuri
Din punctul de vedere al dimensiunii deosebim automate uni-dimensionale, bi-
dimensionale si tri-dimensionale.
In cazul uni-dimensional, fiecare celula are doi vecini, iar ansamblul poate sau nu
forma un inel (in acest caz celula N are vecini celula N-1 si celula 1). Exista pentru acest
model o singura reprezentare: un vector de celule.
In cazul bi-dimensional intervine si importanta formei celulelor. Aceasta poate fi
triunghiulara, patratica sau hexagonala. Avantajul celulelor triunghiulare este numarul redus
de vecini, iar dezavantajul il reprezinta dificultatea reprezentarii si vizualizarii. In cazul
formei patratice reprezentarea si vizualizarea reprezinta avantajul, in timp ce dezavantaj ar
putea fi in anumite cazuri insuficienta izotropie. Celula hexagonala prezinta cel mai mic grad
8/14/2019 Automate Celulare
3/7
Florin Burgui Automate celulare, structuri, concepte fundamentale, aplicatii
3
de anizotropie dintre toate reprezentarile bi-dimensionale. Dezavantajul il reprezinta
vizualizarea si reprezentarea greoaie (numar mare de vecini si incadrarea intr-o arie
patratica).
Pentru a putea fi usor de prelucrat se foloseste convertirea ansamblului de celulehexagonale in ansamblu de celule patratice.
adica
sau, un alt mod de a realiza aceasta operatie:
adica
Amandoua maparile au avantaje si dezavantaje. Prima (denumita shear mapping )
are avantajul ca vecinatatile raman aceleasi, dar conditiile de frontiera sunt mai greu de
implementat. In plus transformarea trebuie facuta si invers pentru vizualizare.
Cea de-a doua, numita shift mapping , are avantajul ca sunt simplu de implementat
conditiile de frontiera, dar vecinatatile se schimba un pic.
Maparea din celule triunghiulare in patratice este asemanatoare cu shear mapping
din cazul celulelor hexagonale.
adica
8/14/2019 Automate Celulare
4/7
Florin Burgui Automate celulare, structuri, concepte fundamentale, aplicatii
4
O altfel de mapare este trecerea de la celule triunghiulare la patratice, dar o celula
patratica va contine doua celule triunghiulare. Adica:
3. Elemente
3.1. Vecinatati
Vecinatatea este data de celulele cu care interactioneaza celula de lucru in cadrul unei
operatii.Vecinatatea de tip Von Neumann este alcatuita din celulele aflate sus, jos, in stanga si
in dreapta fata de celula de lucru.
Vecinatatea de tip Moore este alcatuita din toate celulele care inconjoara celula de
lucru.
Mai exista si cazul vecinatate arbitrara. Adica una definita de noi, dupa o lege
oarecare.
3.2. Conditiile de frontiera
In definitia automatului celular, nu exista frontiere. Insa pentru ca spatiile de lucru
sunt finite, este necesar sa definim frontiere. Un alt motiv pentru care se realizeaza acest
lucru este ca mai toate aplicatiile au frontiere naturale.Sunt trei tipuri de valori pentru frontiera: fixe, periodice si reflexive.
Frontierele periodice sunt realizate prin repetarea ariei de lucru. In cazul uni-
dimensional se obtine practic un inel, iar bi-dimensional un tor.
Frontierele reflexive sunt in cazul in care doua arii alaturate sunt reprezentarile unei
arii in realitate si a imaginii ei in oglinda.
3.3 Conditiile initiale
Stabilirea conditiilor initiale este un element foarte important, evolutia ulterioara a
automatului fiind influentata major de acest lucru.
8/14/2019 Automate Celulare
5/7
Florin Burgui Automate celulare, structuri, concepte fundamentale, aplicatii
5
Pentru exemplificare folosim cazul in care celulele pot lua doar starile 0, 1 sau 2. Este
normal ca daca in starea initiala avem 5% celule in starea 2 si restul in starea 0, evolutia sa fie
diferita fata de cazul in care avem in starea initiala 5% celule in starea 2, 5% celule in starea 1
si restul in starea 0.
3.4. Setul de stari
In concordanta cu definitia automatului celular, fiecare celula este un automat finit si
de aceea are si un set finit de stari pe care le poate lua. De obicei, acest set de stari este foarte
mic. Motive pentru acest fapt sunt destule.
In primul rand numarul de stari ale automatului in cazul in care numarul de stari ale
celulelor este s iar numarul de celule este n este de s la puterea sn. Acest numar creste foarte
rapid cand s sau n cresc.
Alt motiv este ca doar avand cateva stari este posibil sa definim o lege explicitand-o si
stocand-o intr-un tabel (marimea tabelului este de sn)
Insa si folosirea unui numar mare de stari are avantaje. Acestea se refera la o mai
buna aproximare discreta a unui sistem continuu.
3.5. Reguli de tranzitie
Cea care influenteaza cel mai mult evolutia automatului celular este legea de tranzitie.
E adevarat ca aceasta lege depinde de marimea ariei, de vecinatatea aleasa si de setul de stari
ale celulei. Chiar daca functia determina in mod direct evolutia, in multe cazuri nu putem
prevedea evolutia automatului fara a o simula explicit.
Legea de evolutie poate fi descrisa explicit, in sensul ca fiecare caz este tratat separat
(fiecarei stari a unei celule ii este indicata starea in care se poate trece). Adica:
Aceasta este forma explicita. Exista pentru acest caz si forma restransa:
8/14/2019 Automate Celulare
6/7
Florin Burgui Automate celulare, structuri, concepte fundamentale, aplicatii
6
O clasa importanta a regulilor de tranzitie o constituie regulile probabilistice. In acest
caz, functia care da tranzitia nu intoarce un rezultat fix, ci unul dintr-un set de rezultate,
fiecare dintre ele avand o anumita probabilitate si fiind independente intre ele. Evident ca
suma probabilitatilor dintr-un set de rezultate trebuie sa fie egala cu 1.
Importanta acestor reguli de tranzitie este deosebita, pentru ca sistemele naturale sunt
pline de zgomote. In cele mai multe cazuri, este suficient sa introducem conditii initiale
random, dar in multe cazuri regulile probabilistice au avantaje.
4. Aplicatii
Aplicatiile automatelor celulare sunt numeroase si diverse.
1. Simularea comportarii gazelor. Un gaz este compus din molecule al caror comportament
depinde de starea meoleculelor vecine.2. Studiul feromagnetismului in conformitate cu modelul Ising: acest model reprezinta
materialul ca fiind o retea in care fiecare nod este intr-o stare magnetica. Aceasta stare
una din cele doua orientari ale spinului electronului este in functie de starea vecinilor.
3. Simularea procesului de infiltrare.
4. Simularea propagarii focului intr-o padure.
5. Conceperea unor calculatoare masive.
6. Simularea si studiul dezvoltarii urbane.
7. Simularea procesului de cristalizare.
8. In multe cazuri este folosit ca generator grafic, dar in cele mai multe cazuri este cunoscut
ca fiind utilizat in domeniul vietii artificiale.
8/14/2019 Automate Celulare
7/7
Florin Burgui Automate celulare, structuri, concepte fundamentale, aplicatii
7
Cuprins
1. Prezentare generala ..................................................... ............................................................. ...........................22. Structuri ............................................................ ............................................................. .....................................2
3. Elemente ........................................................... ............................................................. .....................................4
3.1. Vecinatati ............................................................. ............................................................. ...........................43.2. Conditiile de frontiera .................................................... ............................................................. .................4
3.3 Conditiile initiale...........................................................................................................................................4
3.4. Setul de stari.................................................................................................................................................5
3.5. Reguli de tranzitie .......................................................... ............................................................. .................5
4. Aplicatii ............................................................ ............................................................. .....................................6