Sejtautomaták - egy
Egy sejtautomata (Kalifornia) - egy sor képző sejtek néhány időszakos rácsban adott átmeneti szabályok, amelyek meghatározzák sejtállapotra a következő alkalommal az államon keresztül a sejtek távolságra helyezkedik el belőle már nem biztos, hogy a jelenlegi időben. Általános szabály, hogy úgy véljük, automata, ahol az állam határozza meg a sejt és a hozzá legközelebbi szomszédok. Mivel a rács általában úgy köbös rács. Az egyik legérdekesebb példa a celluláris automaták - játék „Life”.
meghatározás
Egy sejtautomata áll egy sor tárgyak (sejtek), általában képező szabályos rács. Állapota egy i-edik tárgyat (vagy sejtek) az n időpontban jellemzi egy változó, amely lehet egész szám, valós vagy komplex szám, vagy jelentésük egy sor több számot. A megfontolt sejtállapotra változás szinkron módon diszkrét időpontokban a helyi valószínűségi szabályokat, amelyek állapotától függ változók a legközelebbi szomszédos csomópontok. Ezek a szabályok nem változnak az idővel.
Egy sejtautomata diszkrét dinamikus rendszer, amely viselkedés teljesen definiáljuk helyi függőségek. Hívjuk diszkrét térben helyet, mint egy diszkrét elemekre. Egy példa ennek az osztálynak lesz az úgynevezett térrácshéj sejtautomaták, és annak egyes elemei - a sejt. Minden cella jellemzi egy adott érték egy bizonyos beállított. Mintegy sejt azt mondja, hogy tartalmaz vagy ennek megfelelő értékű vagy az, vagy olyan állapotban kódolt adat értéke ain. Ez lehet logikai, egész szám, lebegőpontos szám, vagy számos más tárgyat, attól függően, hogy az alkalmazás igényeinek. Az állapotok halmaza a rács cella nevezzük az állam a rács. Állapota a rács megfelelően változik egy bizonyos törvény, amely az úgynevezett sejtautomata szabályait. Minden állapot változás a rács nevezzük iteráció. Idő a modell diszkrét és minden iteráció megfelel egy bizonyos időpontban. Szabályzat határozza meg, milyen értéket kell tartani egy ketrecben a következő pillanatban az idő függvényében az értékek más sejtek a jelenlegi pillanatban, és talán még a foglalt értékeken magát abban a pillanatban. Ha az új állam egy sejt függ a jelenlegi állapot, akkor a megfelelő sejtautomata mondani, hogy egy automata memória sejtek, különben - automatikusan nem emlékszik sejteket. Sok sejtek, amelyek befolyásolják az értékét, kivéve a saját, úgynevezett szomszédságában sejteket. Neighborhood sejtek könnyebb kérni, ha a rács, hogy vezessenek be egy mutatót, így tovább, a kényelem, fogunk beszélni a rács diszkrét metrikus tér. Az egyik fő különbség a cella rendszer az összes többi számítógépes rendszerek is, hogy az összes többi rendszer, két alapvetően különböző részből áll: építészeti, ami fix, és aktív (azaz végez bizonyos műveleteket), valamint az adatok, amelyek a változó és passzív (azaz maguk mint ilyen, nem tudnak semmit). A sejtautomaták, és ő és a többi rész pedig izomorf elvileg megkülönböztethetetlen egymástól elemekkel. Így egy számítógépes rendszer működhet az anyagi része, módosítani, bővíteni magukat, és építeni a saját fajtája. [1] Bár ebbe az osztályba tartozó rendszerek által feltalált Neumann János, ez a párhuzamos architektúra az úgynevezett „non-Neumann”, mint egy egységes építészeti ő teremtett előtt. Ha összehasonlítjuk a sejtautomaták és közönséges differenciálegyenletek (ODE), az egyik fő különbség az első második egy helyi szabály szerint, amely leírja a rendszer dinamikáját. Abban az esetben, a TAC, használjuk néhány szabály változások átlaga a teljes értékű rendszer - közepes (pl koncentráció). Ebben az esetben először úgy gondolták, hogy ezek a szabályok léteznek. Abban az esetben, SC ilyen jellegű általános szabályok nem kötelező. Elég tudni, hogy a jogszabályok rendszerének fejlesztése a mikro- vagy mezo-szinten, kis térbeli területen (sejtek) teszik ki a macrosystem. Csak az a fontos, hogy ezek a helyi szabályok azonosak az összes sejteket. Egy másik jellemzője a SC a differenciálegyenletek (DE) a használata nem csak a digitális, hanem hajlamosak egész változók. diszkrétség változókat lehet tekinteni egy nagy osztálya folytonos nem differenciálható függvény. Meg kell jegyezni, hogy a különálló tulajdonságai űrhajó jelentősen csökken, ha dolgozik, nagy a változók értékeit, de soha nem tűnik el. Mindig van egy minimális diszkrét fokozatos változást a változó. Abban az esetben, a numerikus megoldása ODE vagy részleges kontroll csökkentheti a diszkrét lépés tetszőlegesen alacsony értékeket.
Megjegyzés alapvető tulajdonságait a klasszikus modell sejtautomaták.
• a helyi szabályoknak. Egy új státus csak elemeit környéke befolyásolhatja sejtek és talán ő maga;
• A homogenitás rendszer. Nincs ilyen terület a rács nem lehet megkülönböztetni egymástól az egyes funkciók a szabályokat, és így tovább. N. A gyakorlatban azonban, egy véges halmaza rácscella- (valójában ez nem lehetséges kiosztani korlátlan mennyiségű adat). Ennek következtében előfordulhat, hogy él hatásokat. ketrec szélén álló rács különbözni fog a többitől a szomszédok száma. Ennek elkerülése érdekében, akkor adjuk meg a periodikus peremfeltételek
• A lehetséges állapotok a sejtek - természetesen. Ez az állapot eléréséhez szükséges új állam a szükséges sejtek véges számú műveletet. Megjegyzendő, hogy ez nem zavarja a sejtek tárolására használt lebegőpontos számok alkalmazások megoldásánál.
• Az értékek az összes sejtben megváltozik ugyanabban az időben, a végén az iteráció, de nem a számítástechnika. Ellenkező esetben az eljárás a felsorolás a rács sejtek ha így iteráció, jelentősen befolyásolja az eredményt. Meg kell jegyezni, hogy a gyakorlatban, bizonyos problémák megoldásában, szükség van, hogy feladja az utolsó három tulajdonságait.
A fő iránya a kutatás sejtautomaták - algoritmikus megoldhatóságának bizonyos problémákat. Kérdések az építés a kezdeti állapotok is tekinthető, amelyben a sejtautomata megoldja az adott probléma.
Osztályozása sejtautomaták
SC osztható determinisztikus és valószínűségi. mobil és mozdulatlan. homogén és heterogén. egyszerű absztrakt és komplex, pontosan írja le a valós rendszer.
Mozgatható és rögzített műholdak
Mozgatható SC sejteket jellemzi, a képesség, hogy a pozíció változtatásához a kristály az evolúció során a rendszer. A rögzített helyzetben az SC sejtek evolúció során állandó marad.
Determinisztikus és valószínűségi CA
determinisztikus SC
A determinisztikus állapotban SC sejt Ain + 1 egy későbbi időpontban egyértelműen meghatározzák az állam a sejt és a legközelebbi szomszédok az előző alkalommal. Ebben az esetben az állam az elem időpontban n + 1 egyetlen értékű függvény F két változó - az állapot az elem és az összegeket az államok legközelebbi szomszédai az előző pillanatban n. Ezzel meghatározása sejtautomata nincs memóriája. Sejtautomaták memória érhető el, feltéve, hogy az F függvény függ, például, szintén a feltétele a tételt egy korábbi időben.
valószínűségi CA
SC, ahol az állam a sejtek egy későbbi időpontban alapján határozzuk meg bizonyos valószínűséggel, az úgynevezett valószínűségi CA (PCA). A klasszikus PCA átmeneti szabályok elvont, és nem kapcsolódik egyértelműen a valós folyamatok játszódnak le az szimulált rendszer. Az ilyen gépek a szimulációs folyamat minden egyes cella érzékelő generált véletlen számok véletlen számot Q (0 Annak érdekében, hogy megoldják a legnehezebb probléma a típusú „reakció - diffúzió - konvekciós” módszerrel, figyelembe véve ingadozások a valószínűségi sejtautomata felhasználásával fejlesztették Monte Carlo eljárás (VKA-MK vagy VKA). Egy sejtautomata rendszeres tömb, ami N2 = N0 elemi cellák. rács alakú lehet, nem csak a négyzet, hanem téglalap alakú egy erősen hosszúkás alakú sejtek. Minden egyes cella jellemzi egy sor egészek: számának megfelelő számú különböző molekulák egy adott cellában (például Na, Nb, nC esetén háromféle molekula A, B és C), és annak egész koordinátákkal (például, i és j). Cell is tulajdonítható egy bizonyos térfogatú Vm, és a lineáris mérete L = (Vm) 1/3. A térfogat Vm használjuk beállításakor a valószínűségek kémiai reakciók a sejtekben. Minden sejtet tekinthető homogénnek. Néha használt szabályok írott formában a közönséges differenciálegyenletek (osztály SC-TAC). Ebben az esetben az állam a sejtek által meghatározott változókat is igénybe vehet bármely valós számokat. Az ilyen gépek, differenciálegyenletek megoldani külön-külön minden egyes cella számára egy meghatározott időintervallum, minden cella lehet különböző kezdeti feltételek. Ez az osztály az űrhajók nagyon szoros ellenőrzésére részleges. Modellek, mint a SC-TAC egy köztes állapot között űrjármű és a CPA, valamint a között, űrhajók és ellenőrzik egyszerű részleges. A fő ötlet az SC-TAC az, hogy felosztjuk a területet egyenlő szimulált cellába, és az oldatot a ODE rendszer egymástól függetlenül minden egyes cellában a különböző kezdeti feltételeket. Egyes modellek, térbeli elrendezése a sejtek nem lényeges, és a többi száma a szomszédos sejtek és a dimenzió a tér meghatározó szerepet játszik (az esetekben a hullámterjedés és kialakulása álló térbeli szerkezetek, nem kevert környezetben). A KA-TAC modellek azt feltételezik, hogy a sejt tartalmaz egy nagyon nagy számú részecskét, amely lehetővé teszi, hogy alkalmazza a TAC és folytonos függvények. Ez a tény hagy csak egyféleképpen a diffúziós szimuláció, nevezetesen egy egyszerű átlagos koncentrációja a szomszédos sejteket. 2. PCA gyakran alkalmazzák, hogy szimulálja a fizikai és kémiai folyamatok a nanoméretű rendszerek, bonyolultsága miatt az alkalmazás klascicheskih alapuló módszerek az oldat kontroll
Kapcsolódó cikkek