Un automat celular (CA) - un set de celule care formează niște zăbrele periodice cu reguli de tranziție date care determină starea de celule data viitoare prin starea celulelor situate la o distanță de ea nu mai este sigur, la momentul actual. De regulă, automatele sunt considerate, unde statul este determinat de celula în sine și de cei mai apropiați vecini. Lattica este de obicei considerata o retea cubica. Unul dintre cele mai interesante exemple ale automatului celular este jocul "Viața".
definiție
Un automat celular constă dintr-un set de obiecte (celule), formând de obicei o latură obișnuită. Starea unui obiect i (sau celular) individual la momentul n este caracterizată de o anumită variabilă, care poate fi un număr întreg, real sau complex sau un set de mai multe numere. Stările considerate de celule se schimbă sincron, prin intervale de timp discrete, în conformitate cu regulile de probabilitate locale, care pot depinde de starea variabilelor la nodurile cele mai apropiate. Aceste reguli nu se schimbă în timp.
Un automat celular este un sistem dinamic discret, al cărui comportament este complet determinat din punctul de vedere al dependențelor locale. Noi numim spațiu discret un spațiu peste un set discret de elemente. O instanță a unui spațiu din această clasă va fi numită zgârietul automatului celular și fiecare dintre elementele sale se numește celulă. Fiecare celulă este caracterizată de o anumită valoare dintr-un anumit set. Se spune că o celulă conține sau are o valoare corespunzătoare, sau este sau este într-o stare codificată de valoarea dată ain dată. Poate fi un număr boolean, un număr întreg, un număr de punct floating, un set sau un alt obiect, în funcție de nevoile sarcinii. Setul de stări ale tuturor celulelor lattice se numește starea rețelei. Statul lattic se modifică în conformitate cu o anumită lege, care se numește regulile automatului celular. Fiecare schimbare a stării rețelei se numește iterație. Timpul din modelul examinat este discret și fiecare iterație corespunde unei anumite momente de timp. Normele stabilesc ce valoare trebuie să conțină în celulă la următoarea dată, în funcție de valorile din unele alte celule la ora curentă și, eventual, de valoarea pe care o conține în momentul curent. Dacă noua stare a celulei depinde de starea sa actuală, atunci automatul celular corespunzător se spune a fi un automat cu celule cu memorie, altfel - un automat cu celule fără memorie. Setul de celule care influențează valoarea acestui lucru, cu excepția lui însăși, se numește vecinătatea celulei. Este mai convenabil să definim vecinătatea unei celule dacă introducem o metrică pe latură, prin urmare, pentru comoditate, să vorbim despre o latură ca un spațiu metric discret. Una dintre principalele diferențe dintre sistemul de celule de la toate celelalte sisteme de computere este faptul că toate celelalte sisteme, există două părți fundamental diferite: arhitectură, care este fixat și este activ (de exemplu, efectuează anumite operațiuni) și datele care sunt variabile și pasive (de exemplu, ele însele pe cont propriu nu pot face nimic). În automatele celulare, ambele părți constau din izomorfe fundamentale, care nu pot fi deosebite de elementele celeilalte. Astfel, sistemul de calcul poate opera cu partea sa materială, să se modifice, să se extindă și să construiască altele similare [1]. Deși sistemele din această clasă au fost inventate de John von Neumann, această arhitectură paralelă a fost numită "non-von Neumann", deoarece a creat o arhitectură consistentă mai devreme. Dacă vom compara automate celulare și ecuații diferențiale ordinare (ODE), una dintre principalele diferențe față de prima secundă este o regulă locală prin care descrie dinamica sistemului. În cazul utilizării ODE, vom folosi câteva reguli pentru modificarea valorilor medii în sistem - mijloacele (de exemplu, concentrațiile). În același timp, se presupune inițial existența unor astfel de reguli. În cazul SC, nu este necesară existența unor astfel de reguli generalizate. Este suficient să cunoaștem legile dezvoltării sistemului la micro- sau meso-nivel în micile regiuni spațiale (celule) din care constă macrosistemele. Este important doar ca aceste reguli locale să fie identice pentru toate celulele. O altă diferență a navei spațiale de la ecuațiile diferențiale (DU) este folosirea nu numai a variabilelor discrete, ci, de regulă, întregi. Discretitudinea variabilelor ne permite să luăm în considerare o clasă mare de funcții discontinente nediferențiate. Trebuie remarcat faptul că proprietățile discrete ale SC sunt reduse semnificativ atunci când lucrează cu valori mari ale variabilelor, dar ele nu dispar niciodată. Există întotdeauna un pas minim de schimbare a variabilei. În cazul unei soluții numerice a ODE sau a DU în derivați parțiali, se poate reduce scara discretivității la valori arbitrare de mici dimensiuni.
Observăm principalele proprietăți ale modelului clasic de automate celulare.
• Localitatea regulilor. Celulele pot fi afectate numai de elementele din vecinătatea ei și, poate, de la sine;
• Uniformitatea sistemului. Nici o zonă a rețelei nu se poate deosebi de cealaltă prin unele particularități ale regulilor etc. Cu toate acestea, în practică, rețeaua se dovedește a fi un set finit de celule (la urma urmei, nu este posibilă alocarea unei cantități nelimitate de date). Ca urmare, pot apărea efecte de margine. celulele situate la limita zăbrelelor vor fi diferite de celelalte în numărul de vecini. Pentru a evita acest lucru, putem introduce condiții limită periodice
• Setul de stări de celule posibile este finit. Această condiție este necesară pentru a obține un număr finit de operații pentru a obține o stare nouă a celulei. Rețineți că nu interferează cu utilizarea celulelor pentru a stoca numere în virgulă mobilă atunci când rezolvați problemele aplicate.
• Valorile din toate celulele se modifică la un moment dat, la sfârșitul iterației, și nu la fel ca la calcularea calculului. În caz contrar, ordinea de sortare a celulelor rețelei, în iterație, ar avea un efect semnificativ asupra rezultatului. Trebuie remarcat faptul că, în practică, atunci când se rezolvă anumite probleme, este necesar să se renunțe la ultimele trei proprietăți.
Direcția principală a investigării automatelor celulare este solvabilitatea algoritmică a anumitor probleme. Considerăm, de asemenea, construirea stărilor inițiale, în care automatul celular va rezolva o problemă dată.
Clasificarea automatelor celulare
Navele spațiale pot fi împărțite în deterministe și probabilistice. mobilă și nemișcată. omogene și eterogene. simplă abstractă și complexă, descriind cu exactitate sistemele reale.
Mijloacele de deplasare și fixe
Vehiculele cu spațiu mobil sunt caracterizate de posibilitatea schimbării poziției celulei în rețea în timpul evoluției sistemului. În cazul fixării SC, poziția celulei rămâne constantă în timpul evoluției.
Deterministic și probabilist SC
Nave spatiale deterministe
În navele spațiale deterministe, starea celulei ain + 1 într-o clipă de timp ulterioară este determinată în mod unic de starea acestei celule și a vecinilor săi apropiați în momentul precedent. În acest caz, starea acestui element la momentul n + 1 este o funcție unică a F din două variabile - starea acestui element și suma stărilor vecinilor săi apropiați la momentul precedent de timp n. Cu această definiție, automatul celular nu are memorie. Aparatele automate cu memorie pot fi obținute presupunând că funcția F depinde, de exemplu, și de starea elementului într-o perioadă chiar mai devreme.
Probabilistă SC
SC în care stadiile celulare la un moment dat ulterior sunt determinate pe baza unor probabilități sunt numite SC probabilistic (BCA). În CSA clasice, regulile de tranziție sunt de natură abstractă și nu sunt legate în mod unic de procesele reale care apar în sistemul simulat. În astfel de automate, atunci când modelăm procesul pentru fiecare celulă, un generator de numere aleatoare generează un număr aleatoriu Q (0 Pentru a rezolva cele mai dificile probleme ale „reacție - difuzie - convecție“ tip metoda, luând în considerare fluctuațiile automatului celular probabilistică a fost dezvoltat folosind procedura Monte Carlo (AVK-MK sau VKA). Un automat celular este o rețea regulată constând din celule elementare N2 = N0. Forma de zăbrele nu poate fi doar pătrată, ci și dreptunghiulară cu celule puternic alungite. Fiecare celulă se caracterizează printr-un set de numere întregi: număr varietate de molecule într-o celulă dată corespunzătoare (de exemplu, nA, Nb, nC, în cazul a trei tipuri de molecule A, B și C) și coordonatele sale întregi (de exemplu, i și j). Celulei i se atribuie un anumit volum Vm și o dimensiune liniară l = (Vm) 1/3. Volumul Vm este utilizat atunci când se specifică probabilitatea reacțiilor chimice în celule. Toate celulele sunt considerate omogene. Uneori sunt folosite reguli scrise sub forma unor ecuații diferențiale obișnuite (clasa KA-ODE). În acest caz, stările celulare sunt date de un set de variabile ale căror valori sunt capabile să ia orice număr real. Pentru astfel de automate, ecuațiile diferențiale sunt rezolvate pentru fiecare celulă separat în timpul unui interval de timp fix, fiecare dintre celule având condiții inițiale diferite. Această clasă de SC este foarte apropiată de DU în derivate parțiale. Modelele tip KA-ODE ocupă o stare intermediară între nave spațiale și nave spațiale, precum și între nave spațiale simple și telecomandă în derivate parțiale. Ideea de bază a KA-ODE este împărțirea regiunii modelate în celule de dimensiuni egale și soluția sistemului ODE în mod independent în fiecare celulă cu condiții inițiale diferite. În unele modele, dispunerea spațială a celulelor nu este esențială, iar în altele numărul de celule învecinate și dimensiunea spațiului joacă un rol crucial (cazuri de propagare a undelor și formarea de structuri spațiale staționare într-un mediu non-agitat). În modelele KA-ODE se presupune că celula conține un număr foarte mare de particule, ceea ce face posibilă utilizarea ODE și a funcțiilor continue. Această circumstanță lasă doar o singură modalitate de a simula difuzia, și anume simpla medie a concentrației în celulele vecine. 2. CKA este adesea folosit pentru a modela procesele fizico-chimice în sistemele nanometrice, care este asociat cu complexitatea utilizării metodelor clasice bazate pe soluția DU
Articole similare