Automate Celulare

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


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


3/7


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


4/7


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.


5/7


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:


6/7


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.


7/7


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

Automate Celulare

Documents

Transcript of Automate Celulare