Modelování diskrétních systémů

(procesy, události, celulární automaty)

Z větší části převzato z Principy modelování a simulace systémů

Diskrétní systém: systém, jehož chování je charakteristické skokovými změnami stavu v určitých časových okamžicích.

Proces je posloupnost událostí. Proces může být například zákazník v obchodu a jeho posloupnost událostí je: vstup do obchodu, výběr položek k nákupu, zaplacení na pokladně, odchod z obchodu.

Pro vývoj simulace stačí kvaziparalelismus: v jednom časovém okamžiku se sériově projdou všechny aktivity plánované na tento čas a pak se teprve čas posouvá.

Události určují vývoj modelu v čase. Každá událost je spjatá s časovým okamžikem, ve kterém má být spuštěna. Pokud proces v rámci některé ze svých událostí čeká, je tato událost s časem provedení vložena do kalendáře v řízení simulace, proces je pozastaven a řízení je předáno simulátoru. V momentě, kdy simulátor dorazí do tohoto naplánovaného momentu, je proces odpauzován.

Implementační záležitost. Při pozastavení procesu (čekání na posunutí v čase) je nutné předat řízení simulátoru a opět proces obnovit. Toto se dá řešit např. pomocí vláken a jejich uspávání. Některé knihovny nebo jazyky s vyšší abstrakcí umožňují použití konceptů jako aktuální pokračování (continuation). Dají se využít i věci jako Actor model (komunikace procesů pomocí zpráv).

Celulární automat sestává z topologicky uspořádaných buněk v n-rozměrném (n většinou 2 nebo 3) prostoru. V každém kroku simulace je vypočítán nový stav buněk a následně jsou všechny buňky synchronně překlopeny do nových stavů.

Buňka při výpočtu svého nového stavu může uvažovat svůj vnitřní stav a také stav buňek v nějakém svém okolí. V 2D automatech je se pracuje např. s čtyřokolím (kříž) nebo osmiokolím (všechny buňky kolem). Buňky nemusí nutně být v čtvercové mřížce, může jít třeba i o hexagonální mřížku s použitím šestiokolí.

Protože celulární automat má v praxi konečný počet buněk (nekonečné množství se nedá moc reálně implementovat), je nutné zavést okrajové podmínky pro buňky ležící za hranicemi modelovaného prostoru. Tyto okrajové podmínky jsou pomyslné hraniční buňky a mohou být řešeny např. jako:

1. konstantní podmínky: hraniční buňky mají přiřazen jeden ze stavů, jehož mohou buňky systému nabývat
2. cyklické podmínky: hraniční buňka je ztotožněna s druhou stranou prostoru (nejlevější buňka má jako levého souseda nejpravější atd.)
3. adiabatické podmínky: nulový gradient, okolí má stejnou hodnotu jako okrajové buňky automatu
4. reflektivní podmínky: hodnota buňky z druhé strany okrajové (okrajová buňka o jedno vzdálená od okraje)

Jsou 4 základní třídy dle chování a složitosti systému:

1. still lifes - systém se dostane do nějakého stavu a pak už se nemění
2. oscilátory - systém periodicky opakuje sekvenci stavů
3. chaos - systém netvoří žádné struktury, chová se chaoticky
4. komplexní vzory (ne nutně oscilující stav celého systému)

Použití automatů je vhodné například při fyzikálních simulacích, kdy je možné nějaký fyzikální proces, popsaný obvykle diferenciálními rovnicemi, ve kterých figuruje prostor a čas. Tyto diferenciální rovnice jsou pomocí nějaké metody prostorově i časově diskretizovany a výsledné rovnice jsou přímo implementovány jako vnitřní přechodová funkce buňek. Příklad: jednoduché vedení tepla v materiálech. Další aplikace jsou třeba v simulaci dopravy.

tohle sem asi nepatri, ale mozna by se hodilo to vedet (bylo to soucasti SNT, no)

Smells Like Teen Spirit celulárních automatů: Game of Life.