UNIVERSITATEA POLITEHNICA BUCURESTI

Facultatea de Electronica si Telecomunicatii

sectia Ingineria Sistemelor de Calcul

Automate celulare, structuri, concepte fundamentale, aplicatii

Burgui Florin

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 de celule 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 observat ca 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

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 celule hexagonale 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

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.

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:

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.

Florin Burgui Automate celulare, structuri, concepte fundamentale, aplicatii

7

Cuprins

1. Prezentare generala .............................................................................................................................................2 2. Structuri ..............................................................................................................................................................2 3. Elemente .............................................................................................................................................................4

3.1. Vecinatati .....................................................................................................................................................4 3.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