25 - Princípy modelovania a simulácie systémov

• Pseudokódy

• systém - súbor elementárnych častí (prvkov systému), ktoré majú medzi sebou určité väzby
• model - napodobnenina systému iným systémom
• modelovanie - vytváranie modelov systému
• simulácia - metóda získavania nových znalostí o systéme experimentovaním s jeho modelom

• vytvorenie abstraktného modelu - formovanie zjednodušeného popisu systému
• vytvorenie simulačného modelu - zápis abstraktného modelu formou programu
• simulácia - experimentovanie s reprezentáciou simulačného modelu
• analýza a interpretácia výsledkov, overovanie správnosti modelu

• výhody - cena, rýchlosť, bezpečnosť, niekedy jediný možný spôsob
• nevýhody - problém validity modelu, vysoká náročnosť vytvárania modelov, náročnosť na výkon počítačov, konkrétne numerické výsledky (zmena parametra vyžaduje celú simuláciu opakovať), nepresnosť numerického riešenia, nestabilita numerických metód

• systém S = (U, R)
• U - univerzum, konečná množina prvkov systému U = {u1, u2,… uN}
• prvok systému u = (X, Y)
  • X - množina všetkých vstupných premenných
  • Y - množina všetkých výstupných premenných
• R - množina všetkých prepojení

• väzby medzi prvkami systému - sériová, paralelná, spätná

• čas
  • reálny - čas v ktorom prebieha skutočný dej v reálnom systéme
  • modelový - časová os modelu (môže byť reálny, zrýchlený, spomalený)
  • strojový - čas CPU potrebný na výpočet programu
• časová množina - množina všetkých časových okamihov, v ktorých sú definované hodnoty vstupných, stavových a výstupných premenných systému S (diskrétny systém - nesúvisí s diskrétnym časom ale s tým ako sú definované zmeny)
  • diskrétna - stav systému je definovaný len v diskrétnych bodoch
  • spojitá - stav systému je definovaný spojito
• chovanie systému
  • každému časovému priebehu vstupnej veličiny priraďuje časový priebeh výstupných veličín
  • môžme definovať ako zobrazenie X: [σI(u)]^T → [σO(u)]^T
    • [A]^T je množina všetkých zobrazení T na A
    • σI(S) je vstupným priestorom systému S - množina všetkých možných vstupných stavov, v ktorých sa systém môže nachádzať
    • σO(S) je výstupným priestorom systému S - množina všetkých možných výstupných stavov, v ktorých sa systém môže nachádzať

• ekvivalencia chovania systémov - systémy považujeme za systémy s rovnakým chovaním ak vyvolajú v oboch systémoch rovnaké reakcie

• izomorfné systémy - prvky univerza U1 možno vzájomne jednoznačne priradiť (1:1)

• homomorfné systémy - prvkom univerza U1 možno jednoznačne priradiť prvky univerza U2, opačne to nemusí platiť (N:1)

• okolie systému - všetko čo má vplyv na chovanie systému a nie je jeho súčasťou
  • uzavretý systém - nekomunikuje s okolím
  • otvorený systém - komunikuje s okolím
• klasifikácia prvkov systému
  • prvky so spojitým chovaním - napr. prvky v elektrickom obvode
  • prvky s diskrétnym chovaním - zmena prebieha skokovo (napr. zákazník pribudne do fronty)

• prvky s deterministickým chovaním - jednému vstupu zodpovedá jeden výstup
• prvky s nedeterministickým chovaním - jednému vstupu zodpovedá viac výstupov (napr. hod kockou)

• klasifikácia systémov
  • spojité - všetky prvky majú spojité chovanie
  • diskrétne - všetky prvky majú diskrétne chovanie
  • kombinované - spojité aj diskrétne prvky
  • deterministické - všetky prvky sú deterministické
  • nedeterministické - aspoň jeden prvok s nedeterministickým chovaním

• cieľ simulácie - analýza chovania systému v závislosti na vstupných veličinách a na hodnotách parametrov (opakované riešenie modelu)
• typy simulácie
  • spojitá/diskrétna/kombinovaná
  • kvalitatívna/kvantitatívna
  • na analógovom/číslicovom počítači, fyzikálna
  • real-time - synchronizujeme modelový čas s reálnym časom
  • paralelná - výpočty na viacerých procesoroch, ale nemusia byť vo viacerých počítačoch
  • distribuovaná - výpočet distribuovaný medzi viacero počítačov
  • vnorená - napr. simulujeme podnik a v ňom si riaditeľ simuluje rýchlosť výroby
  • reality in the loop - pripojenie reálnych systémov k simulačnému systému a skúmanie tejto kombinácie (trenažéry)
  • interaktívna simulácia - zasahujeme do nej, niečo ako debugovanie, sledovanie za behu
  • virtuálna realita - prepojenie človeka a počítača tak, aby to vyzeralo realisticky
• verifikácia modelu - overenie, či simulačný model zodpovedá abstraktnému modelu
• validácia modelu - overenie, či simulačný model zodpovedá reálnemu systému, ktorý simulujeme

• abstraktné
  • konečný automat, Petriho sieť, turingov stroj, algebraické rovnice, diferenciálne rovnice, diferenčné rovnice, markovské procesy…
  • formulácia zjednodušeného popisu systému abstrahujúceho od všetkých nedôležitých skutočností vzhľadom k cieľu a účelu modelu - nedokážeme postihnúť celý reálny svet, zaujímame sa len o ohraničené oblasti
  • predpokladáme homomorfný vzťah medzi modelovaným systémom a abstraktným modelom
• simulačný model
  • abstraktný model zapísaný formou programu
  • izomorfný vzťah medzi abstraktným modelom a simulačným modelom

• klasifikácia podľa Fishwicka

• konceptuálny - komponenty nie sú presne popísané v zmysle teórie systémov

• deklaratívny - definovaný stavmi a udalosťami, ktoré spôsobia prechod z jedného stavu do druhého

• funkcionálny - grafy zobrazujúce funkcie a premenné

• popísaný rovnicami (constraint) - algebraické, diferenciálne, diferenčné rovnice, alebo orientované grafy
• priestorový (spatial) - rozdeľujú systém na priestorovo menšie ohraničené podsystémy (napr. hra Life)
• multimodely - zložené z iných modelov (napr. diskrétny + spojitý)

• formy popisu diskrétnych systémov - program, Petriho siete, DEVS, automaty, siete automatov, procesné algebry, pi-calculus, CHAM, PRAM…
• proces - postupnosť udalostí, ktoré súvisia s jedným objektom (napr. zákazníkom)
  • paralelné procesy - súčasne vykonávané procesy
  • kváziparalelizmus - vykonávanie „paralelných“ procesov na jednoprocesorovom počítači

• Σ = (P, T, F, W, C, M0)
  • P - množina miest
  • T - množina prechodov P prienik T = {}
  • F ⊆ (P*T)∪(T*P) - incidenčné relácie
  • W - váhová funkcia
  • C - kapacity miest
  • M0 - počiatočné značenie (M - značenie Petriho siete)
• graf
  • miesta - kružnice
  • prechody - obdĺžniky
  • incidenčné relácie - šípky (orientované hrany) - podstatné - nikdy nemôžme spojiť 2 miesta ani 2 prechody
  • váhová funkcia - ohodnotenie hrán
  • prioritné prechody - ak je možných naraz viac prechodov, môžme im dať priority (vyššie číslo, vyššia priorita)
  • inhibičné hrany - vyžadujú aby bolo vstupné miesto prázdne
  • pravdepodobnosť vykonania prechodu
  • časované prechody - pridanie modelového času - môžu byť s konštantným časom alebo náhodnou dobou, ak je prechod realizovateľný, spustí sa odpočet času, ale značka zostáva vo vstupnom mieste až kým čas neubehne - okamžitý prechod má vždy vyššiu prioritu ako časovaný
  • kapacita prechodu - koľko procesov môže na prechode čakať súčasne
  • KAŽDÝ PRECHOD MÁ MAXIMÁLNE 1 PARAMETER (nemôže mať prioritu aj pravdepodobnosť)
• realizovateľnosť prechodu - prechod je možné uskutočniť pri značení M, ak vo vstupných miestach čaká dostatok procesov a súčasne výstupné miesta majú dostatocnú voľnú kapacitu

• systémy obsahujúce zariadenia, ktoré obsluhujú transakcie
• typicky obsahujú - transakcie (procesy), obslužné linky, fronty
• sledujeme - informácie o časovom priebehu transakcie, doby čakania vo frontách, zaťaženie liniek
• fronty
  • frontové rady - FIFO, LIFO, SIRO (service in random order)
  • nulová fronta - požiadavka nemôže ísť do fronty ⇒ systém so stratami
  • fronta konečná - obmedzená kapacita fronty
  • fronta s netrpezlivými požiadavkami - ak prekročí doba čakania limit, opúšťa požiadavka systém
  • prioritné fronty, priorita obsluhy
    • slabá priorita - započatá obsluha sa normálne ukončí
    • silná priorita - obsluha sa preruší a začne sa obsluha požiadavky s vyššou prioritou
• obslužná sieť - vzniká spojením niekoľkých obslužných liniek
  • otvorená - výmena požiadaviek s okolím
  • uzavretá - nedochádza k výmene požiadaviek s okolím
  • zmiešaná - pre niektoré typy požiadaviek je otvorená, pre iné uzavretá
  • statické vlastnosti - počet a charakteristika oblužných liniek, topológia siete
  • dynamické vlastnosti - charakteristika procesu príchodu požiadaviek, charakteristika procesu obsluhy požiadaviek, charakteristika procesu prechodu požiadaviek medzi obslužnými linkami, stratégia obsluhy požiadaviek v obslužných linkách
• Kendallova klasifikácia - X/Y/c
  • X - typ stochastického procesu popisujúceho príchod požiadaviek k obsluhe (M - Poissonov proces príchodov - exponenciálne rozloženie, D - pravidelné deterministické príchody)
  • Y - zákon rozloženia dĺžky obsluhy (M - exponenciálne rozloženie obsluhy, D - konštantná doba obsluhy)
  • c - počet dostupných obslužných liniek
• typy obslužných liniek
  • kapacita = 1, zariadenie (Facility)
  • kapacita = 2, sklad (Store)

• Process - báza pre modelovanie procesov
• Event - báza pre modely udalostí
• Facility - obslužná linka - výlučný prístup
• Store - obslužná linka s kapacitou
• Queue - fronta
• Statistiky - triedy na uchovanie štatistík
• kalendár udalostí - usporiadaná dátová štruktúra uchovávajúca aktivačné záznamy udalostí [(acttime, priority, event), …]

• aplikácie - elektrické obvody, riadenie (automatizácia), fyzika, chémia, astronómia, biológia, ekológia…
• popis spojitých systémov
  • sústavy obyč. diferenciálnych rovníc - hovoria aká bude zmena hodnoty v čase (konkrétnu hodnotu určujú počiatočné podmienky)
  • sústavy algebraických rovníc - napr. na popísanie funkcie sčítačky
  • blokové schémy
  • elektrické schémy - prvky nemajú vstup a výstup - obe strany môžu byť vstup aj výstup
  • grafy signálnych tokov
  • kompartmentové systémy
  • systémová dynamika
  • Bond-graphs

• prevod rovníc vyššieho rádu -rovnice vyššieho rádu musíme previesť na sústavu rovníc prvého rádu, pre ktoré máme vhodné numerické metódy
• znižovanie rádu derivácie
• postupná integrácia
• iné špeciálne metódy

• osamostatniť najvyšší rád derivácie
• sekvencie integrátorov
• bloková schéma
• pozor na počiatočné podmienky

• vhodná pre rovnice s deriváciami vstupov na pravej strane
• osamostatniť najvyšší rád derivácie
• postupná integrácia rovnice a zavádzanie nových stavových premenných
• výpočet nových počiatočných podmienok

• jednokrokové - vychádzajú z aktuálneho stavu
  • Eulerova metóda - viď matematika (odkaz pridám)
• vícekrokové - používajú históriu stavov
  • Metódy Runge-Kutta
  • Adams-Bashforth
  • Adams-Bashforth-Moulton

• problém kombinácie udalostí a numerickej integrácie
• stavové podmienky
  • v istom stave treba skokovú udalosť (napr. relé sa prepne)
  • problém nedetekovania stavovej udalosti spôsobený
    • nepresnosťou výpočtu
    • príliš dlhým krokom

• príklad - detekcia dopadu loptičky na zem - hľadáme riešenie rovnice f(t) = 0
  • metódy - rozpolenie intervalu, Regula falsi, Newtonova …

Skripta IMS + slajdy + Příklady