12 lő dá 12. előadás
Automaták egyszerű eszközök tulajdonságok: tulajdonságok: véges számú állapota van átmenet egyik állapotból a másikba érzékeli a környezetet esetleg megváltoztatja a környezetet új állapotba megy át
kóla automata bemenet: pénz, kiválasztó gombok stb. állapot: standby, pénz van behelyezve stb. kimenet: cola, sprite, visszajáró
Sejtautomaták geometriailag elhelyezett automaták az összes automata azonos automata azonos az automaták egyszerre (párhuzamosan) váltják állapotaikat
bemenet a szomszédok és önmaga állapota kimenet az új állapot
Történet • Neumann Neumann János János, á , Stanislas Stanislas i l Ulam l ‐ 1950 önreprodukáló gépek
• John Conway J h C John Conway ‐ ‐ 1970 Game of Life Martin Gardner népszerűsítette a Scientifc Martin Gardner népszerűsítette a Scientifc American‐ban American ban
• Stephen Wolfram ‐ Stephen Wolfram ‐ 2002 A new kind of science A new kind of science “When I made my first discoveries about cellular automata in the yf early 1980s I suspected that I had seen the beginning of something important. But I had no idea just how important it would all ultimately turn out to be. And indeed over the past twenty years I lti t l t tt b A di d d th tt t I have made more discoveries than I ever thought possible. And a new kind of science that I have spent so much effort building has new kind of science that I have spent so much effort building has seemed an ever more central and critical direction for future intellectual development.”
1D sejtautomaták
két állapot: 1 p és 0
Boolean sejtautomaták Boolean sejtautomaták j
két szomszéd szomszédok + önmaga lehetséges állapota: 2 x 2 x 2 = 8 28 = 256 = 256 lehetséges lehetséges szabály
4 lehetséges viselkedéstípus: határpont viselkedés határciklus viselkedés kaotikus viselkedés komplex viselkedés
254‐es szabály
90‐es szabály
30‐as szabály
2D sejtautomaták Game of life J h C John Conway, 1970 1970 élő és halott cellák szabályok: ÉLŐ cella + 0 vagy gy 1 ÉLŐ szomszéd = HALOTT ((izoláció)) ÉLŐ cella + 4...8 ÉLŐ szomszéd = HALOTT (túlnépesedés) HALOTT cella + 3 ÉLŐ szomszéd = ÉLŐ (születés) a többi esetben a cella változatlan marad
Game of life
Game of life – statisztikus szemmel
hogyan függ a végállapot sűrűsége a kezdeti sűrűségtől?
relaxációs idő
hatványfüggvény, önszerveződő kritikusság
Erdőtűz modell stochasztikus 3 állapotú 3 állapotú sejtautomata d dimenziós rácson ÉLŐ fa ÉGŐ fa ÜRES
SZABÁLYOK: ÜRES cella
p valószínűséggel új ÉLŐ fa É Ő születik
ÉLŐ fa + nincs ÉGŐ szomszéd
f valószínűséggel meggyúl, ÉGŐ fa lesz belőle
ÉLŐ fa + ÉGŐ szomszéd
1‐g valószínűséggel meggyúl, ÉGŐ fa lesz belőle (g – immunitás)
ÉGŐ fa
ÜRES cella
Erdőtűz modell
60%
45%
80%
http://schuelaw.whitman.edu/JavaApplets/ForestFireApplet/
Erdőtűz modell (f = 1, g = 0)
egyetlen gy paraméter a p, az p p újj fa születésének a valószínűsége g korrelációs hossz:
ha ha
a tűz kialszik a tűz
2D‐ben
idő
alatt
ellenkező esetben a tűz fennmarad a rendszerben
Gerjeszthető közeg (excitable media) járványterjedés
oszcilláló reakciók
spirál galaxisok
3 állapotú cellák: 1. nyugodt d 2. gerjesztett 3. makacs a gerjesztés terjed a cellákon, ha azok nyugodtak gerjesztődés után egy makacs időszak következik, a nyugodt állapot eléréséig
Egyéb alkalmazások
Ütközés
Aggregáció
Mintázatok generálása
Vízfolyás
Tűz animációja
Agyag szimulációja
http://madeira.cc.hokudai.ac.jp/RD/takai/automa.html
Perkolációs folyamatok z
kritikus lyukszám
z
KLASZTEREK
perkolációs jelenség
Példák • • •
járványterjedés, szociális já á t j dé iáli hálózatok háló t k kompozit anyagok elektromos és mechanikai tulajdonságai diluált ferromágneses rácsok
Elméleti szempont z
geometriai fázisátalakulás
z
fázisátalakulások tanulmányozása számítógépes szimulációkkal
Algoritmus •
definiáljuk a rácsot (NxN) és a p aktiválási kti álá i valószínűséget ló í ű é t
•
végigjárjuk a rácsot és minden pontját p valószínűséggel aktiváljuk
•
megszerkesztjük a klasztereket és mindegyiket egyedi számmal látjuk el
•
megvizsgáljuk, létezik‐e perkoláló klaszter
•
adott p‐re többször megismételjük a szimulációt, ebből meghatározzuk a perkoláció P(p) valószínűségét
•
különböző különbö ő p értékekre megismételjük a szimulációt
