====== Modelování diskrétních systémů ====== (procesy, události, celulární automaty) ---- Z větší části převzato z [[isz:principy_modelovani_a_simulace_systemu]] 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 ===== 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 ===== 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. ==== Přepínání kontextu ==== 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í automaty (diskrétní) ===== 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ů. ==== Okolí buňky ==== 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í. ==== Okrajové podmínky ==== 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: - konstantní podmínky: hraniční buňky mají přiřazen jeden ze stavů, jehož mohou buňky systému nabývat - 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.) - adiabatické podmínky: nulový gradient, okolí má stejnou hodnotu jako okrajové buňky automatu - reflektivní podmínky: hodnota buňky z druhé strany okrajové (okrajová buňka o jedno vzdálená od okraje) ==== Třídy automatů ==== Jsou 4 základní třídy dle chování a složitosti systému: - still lifes - systém se dostane do nějakého stavu a pak už se nemění - oscilátory - systém periodicky opakuje sekvenci stavů - chaos - systém netvoří žádné struktury, chová se chaoticky - komplexní vzory (ne nutně oscilující stav celého systému) ==== Použití ==== 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**. === Diskretizace diferenciálních rovnic === FIXME 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.