Versiunea pentru imprimarea aici (zip doc - 229кб)
Scopul misiunii
Implementați un automat celular
Descrierea postului
Teoria generală
Celulele automate sunt sisteme dinamice discrete, ale căror comportament este complet determinat în termenii interdependențelor locale ale statelor lor. Un automat celular este o grilă uniformă n-dimensional (finit sau infinit), fiecare celulă (celulă) care poate primi starea unui anumit set de condiții; timpul trece prin etape discrete, iar legile de dezvoltare (modificări ale celulelor de stat) sunt exprimate într-un singur set de reguli, cum ar fi un mic tabel de date, în care fiecare celulă la fiecare pas calculează noua stare a statului de vecinii săi apropiați. Dacă este dat un set adecvat de reguli, atunci un astfel de mecanism simplu de operare este suficient pentru a menține o întreagă ierarhie a structurilor și a fenomenelor. Aparatele automate oferă modele utile pentru numeroase studii în științele naturii. Acestea formează o paradigmă generală a calculelor paralele, așa cum procedează mașinile Turing pentru calcule secvențiale.
Un bun exemplu pentru familiarizarea cu principiile automatizării celulare este "Viața" lui John Horton Conway.
Soiuri de automate celulare
Celulele automate diferă, în special, de numărul de stări celulare, de dimensiunea grilei și de regula de schimbare a stărilor celulare. Considerăm câteva soiuri de automate cu o grilă bidimensională.
La mașinile bidimensionale celulele învecinate sunt în general considerate a 5 celule - celula în sine și 4 vecinii săi diagonală nu imediat (cartier von Neumann) și nouă celule - celula în sine și opt vecinii săi imediați, inclusiv celule diagonale (cartier Moore).
Starea automatului celular poate fi descrisă printr-o matrice, de exemplu:
Aici, stările celulare sunt înregistrate în celulele corespunzătoare ale matricei.
Dar este mult mai interesant să ne imaginăm o stare sub forma unei imagini, în care fiecare pixel corespunde unei celule, iar culoarea actuală a pixelului este determinată de starea celulei.
Exemple specifice de automate celulare
Automate cu mai mult de două state.
Regulile pentru schimbarea stării unei celule sunt scrise după cum urmează
în cazul în care:
S - un set de cifre de la 0 la 8, determină numărul de vecini "vii", în care celula rămâne "în viață"
B - un set de cifre de la 0 la 8, determină numărul de vecini "vii" la care celula "mort" devine "live"
Numărul C, determină numărul de celule care "moare"
Aceasta înseamnă că celula trăiește dacă are 2 sau 3 vecini, că cu exact trei vecini se naște o nouă celulă și că celula moare în paisprezece rotații.
În cazul în care numărul de vecini „vii“ ale celulei nu este egal cu oricare dintre numerele de la setul de S, celula începe să „moară“ și starea ei crește cu fiecare rândul său, până când ajunge la C, după care celula este pierdut. O celulă "pe moarte" nu participă la numărarea numărului de vecini "vii" atunci când calculează următorul pas. La naștere, celula primește prima stare ("celula este în viață").
"Sparks"
02/02/25
Figura arată configurațiile 0, 16, 32, 48, 64 și 80:
"Bug"
23/2/8
Figura arată configurațiile 0, 16, 32, 48, 64 și 80
"Flame"
235678/3468/9
Figura arată configurațiile 0, 16, 32, 48, 64 și 80
Un alt exemplu de automatizare celulară, descoperit de David Griffith de la Universitatea din Wisconsin, în Madison. Plecând de la o stare inițială aleasă arbitrar, mașina demonstrează patru faze diferite, terminate de formațiuni cristaline bizare, care seamănă puternic cu formele primitive de viață.
Regula de conduită mașinii este de a enumera posibile stări de la 0 la n - 1, și să presupunem că, dacă o celulă este la această măsură în k de stat, apoi pe următorul ciclu de care are nevoie pentru a „mânca“ toate celulele vecine în stare k - 1 . mâncat arătat că mâncat de către celula vecină merge de la k - 1 la starea k; O celulă în stare 0 poate mânca celule vecine în starea n-1.
Figura prezintă un exemplu de implementare a unui astfel de automat (câmp 80x80, n = 17). Fiecare fragment pentru 12 iterații diferă de cel precedent.
Tjurmit este o sinteză a automatului celular și a mașinii Turing. Din mașină tyurmit de celule este caracterizată prin aceea că, la momentul inițial este goală, iar unele singură celulă este considerat a fi inițial (tyurmit ocupă poziția de pornire, se află în starea inițială, direcția inițială, de exemplu, la est). Apoi se aplică o regulă a formularului pentru fiecare ciclu de ceas:
Statele sunt de obicei marcate cu litere latine; culoare - numerele de la 0 la 15 (paleta 16 culori), culoarea inițială este negru (aceasta nu este o limită greu, în cazul în care culorile dorite pot fi îmbogățite și să vină cu simbolurile lor); Direcția de deplasare se schimbă în ceea ce privește cursul actual al tiurmitului, este desemnată prin numerele -1 (virați la stânga), 1 (virați dreapta), 0 (drept).
De exemplu, în mod tipic 15 0 A 0 înseamnă că, dacă tyurmit este în stare A și se află într-o cușcă negru, el ar trebui să-l vopsea albă, să se miște un pătrat în direcția curentului și du-te în B. stat
Astfel, dacă A este starea inițială a tiurmitului, 0 este culoarea inițială, atunci setul de reguli tiurmit trebuie să conțină regula A 0 _ _ _.
"Cactus"
(figura arată una dintre configurațiile posibile)
A 0 2 1 A
A 2 10 -1 B
A 10 0 -1 B
B 0 2 1 A
B 2 2 -1 A
B 10 2 -1 A
înregistrare
Designul nu diferă de obicei.
ZIP-fișier cu codul sursă și fișierele executabile, numit conform schemei GZV_nnnnnnnn.zip (unde G - ultima cifră a numerelor de grup, Z - numărul de locuri de muncă, V - stabilirea numărului versiunii, nnnnnnnn - student la numărul de identificare) pentru a trimite [email protected]. msu.su
De exemplu, un student de 206 grupe cu număr de student ID-ul 06529042, care oferă versiune actualizată (a doua) din prima sarcină a programului ar trebui să trimită un fișier cu numele 612_06529042.zip.
Nu uitați să puneți fișierul readme.txt în arhivă. În fișier, descrieți interfața programului (algoritmul de lucru cu programul, elementele de meniu, cheile de control) și specificați următoarele subtascuri:
Realizarea mașinii: [a se indica automat (ele) realizat (e)]
Abilitatea de a edita starea inițială a aparatului: [+/-]
Lucrul cu programul: [algoritmul de lucru cu programul]
Rezultatele muncii
notițe
- Sarcina este strict individuală. Pentru lucrul în comun sau pentru schimbul de coduri, sunt atribuite puncte zero tuturor participanților, în cazul în care lucrul în echipă nu a fost specificat în textul readme.txt al sarcinilor.
- Se recomandă să scrieți un program pentru familia Windows. Scrierea pentru alte sisteme de operare este nedorită și poate cauza întârzieri în verificarea acestor lucrări.
Întrebări frecvente prin sarcină
Unde pot găsi informații detaliate despre programarea pentru Windows?
În sarcina din secțiunea "Generație" se spune că, cu un anumit număr de vecini, celula moartă devine vie. Celula moartă este vie (nu numără numărul de persoane vii)?
Nu, o celulă moartă nu este considerată moartă, deci nu poate să trăiască.
Ce inseamna "TYURYMITH se intoarce stanga / dreapta"?
Să spunem că tiurmitul se îndreaptă spre est.
In imagine cu o culoare gri închis indică unde tyurmit a fost în ciclul anterior, roșu - pentru turmite poziția curentă și gri deschis - în cazul în care el va fi la cursa următoare atunci când se deplasează spre stânga (opțiunea sus), spre dreapta (opțiunea jos) sau la dreapta (varianta medie ).
Cele „generații“ la ce punct ne referim de celule „moarte“: o dată am simțit o nouă stare a automatului (in trecut ea a fost pe moarte), sau imediat, de îndată ce ne-am simțit că numărul de vecini din ei este că ea are deja să mori?
Imediat, de îndată ce celula are un număr neaprobat de vecini, începe să moară. Nu ar trebui să existe nici o stare a mașinii, în care numărul de vecini într-o celulă viu nu coincide cu nici unul dintre seturile S.