Naslov
Računski zasnovano modeliranje dinamičkih sustava
(Computationally Based Modeling of Dynamical Systems)

Autori
Logožar, Robert

Vrsta, podvrsta i kategorija rada
Ocjenski radovi, doktorska disertacija

Fakultet
Fakultet elektrotehnike i računarstva

Mjesto
Zagreb

Datum
05.07

Godina
2012

Stranica
340

Mentor
Budin, Leo

Ključne riječi
modeliranje; (nelinearni) dinamički sustavi; binarni vremenski niz; teorija ε-strojeva; stohastički konačni automati; mjere složenosti sustava; FM i TFM algoritmi; prostorno-vremenska kompleksnost algoritama; DSA program; logističko preslikavanje
(modeling; (nonlinear) dynamical systems; time series; theory of ε-machines; stochastic finite automata; complexity measures; algorithms; data structures; algorithm space-time complexity; DSA program; logistic map)

Sažetak
U ovom multidisciplinarnom radu opisano je, implementirano i primijenjeno modeliranje jednodimenzionalnih dinamičkih sustava u kojem se isključivo na temelju primljenog binarnog vremenskog niza gradi računski model s pridodanim stohastičkim svojstvima. U teorijskom uvodu pokazana je korektnost takvog pristupa. Simbolička dinamika povezana je s kodiranjem u mjerno-modelirajućem kanalu i aproksimirana podnizovima konačne duljine. Između nekoliko računarskih metodologija Crutchfieldova teorija ε-strojeva odabrana je kao najprikladnija za modeliranje iz vremenskog niza. U njoj je temeljni ε-stroj predstavljen stohastičkim konačnim automatom (SFA), koji je ovdje izveden iz konačnih automata (FA). Ilustrirana je podudarnost stohastičkih nedeterminističkih konačnih automata (SNFA) sa skrivenim Markovljevim modelima temeljenim na granama grafa (EOHMM). Dan je i pregled složenijih automata koji su kandidati za ε-strojeve viših razina. Uvedene su operativne inačice osnovnih pojmova teorije ε-strojeva: (L, δ)-ekvivalentna uzročna stanja i njihov praktični ekvivalent --- (L, δ)-morfovi (nadalje, morfovi), te pripadni razredi ekvivalencije. Poznata stanja i njihove vjerojatnosti prijelaza određuju prijelazni tenzor te ε-stroj i SFA. Uvedeni su broj morfovima koreliranih simbola i duljina tako istražene korelacije te duljina korelacije SFA-modela i njegova rekurentnog ciklusa. Opisan je hijerarhijski proces gradbe ε-strojeva. Iz vremenskog niza kreira se raščlambeno stablo visine D, u kojem se morfovi nalaze kao (L, δ)-jedinstvena podstabla. Ta (pod)stabla---s listovima na konstantnoj razini (L) D ---teorijski su razrađena i nazvana ε-(pod)stabla. Njihova se statistika temelji na prosječnom broju b_{; ; l}; ; djece iz čvora na l-toj razini. Glavni računarski doprinos ovog rada izvorni su FM i TFM algoritmi. Oni nalaze morfove (stanja) i njihove međusobne prijelaze i vjerojatnosti, te time definiraju SFA-model sustava. Uz parametre modela L i δ FM algoritam nalazi najdublji morf na razini l_{; ; DM}; ; i općenito staje prije provjere svih podstabla. Stoga kažemo da je on potencijalno površan. Uvjet regularnosti dobivenog SFA jest: l_{; ; DM}; ; + L + 1 ≤ D. Uveden je koncept sveobuhvatnog modeliranja u kojem se varijacijom parametara L i δ---uz odabranu minimalnu rezoluciju potonjeg---na zadanom glavnom stablu istražuje cijeli prostor rješenja FM algoritma. Temeljiti (punoprolazni), TFM algoritam provjerava sva podstabla raščlambenog stabla, a potom uklanja ona koja su (L, δ)-ekvivalentna nekom ranijem podstablu (morfu). On načelno potvrđuje korektnost rezultata FM algoritma. Oba algoritma garantiraju minimalnost i determinističnost svojih regularnih SFA-modela, što im je glavna prednost pred drugim algoritmima iste namjene. Iznijeta je cjelovita informacijsko-teorijska analiza primljenog vremenskog niza i SFA-modela. Definirane su njihove stope entropija i različite složenosti, uključujući i statističku složenost. Na izvoran je način ekspliciran rastav ukupne entropije SFA-modela na sumu statističke složenosti i stope entropije modela. Dokazano je da se stopa entropije modela dalje rastavlja na sumu stope entropije niza odaslanog iz modela i nedeterminiranosti prijelaza, ili na sumu stope entropije Markovljevog izvora i novouvedene stope entropije simbola po prijelazu. Definirani teorijsko-informacijski pokazatelji izračunani su za raznovrsne sustave, a za periodične su i dokazani. Modeliranje do razine SFA ostvareno je u našem programskom alatu DSA. Opisana je implementacija podatkovnih struktura i algoritama korištenih u njegova tri glavna programska modula: za simulaciju dinamičkih sustava, za hranidbu binarnog raščlambenog (glavnog) stabla i za nalaženje SFA. Pregledavanje vremenskog niza, glavnog stabla, morfova i dobivenih modela omogućeno je u grafičkim sučeljima. Za ostvarenje statistički relevantnog glavnog stabla, vremensko-prostorna složenost procesa hranidbe eksponencijalna je u njegovoj visini D. Dokazana je korektnost izvornih algoritama za nerekurzivni prolazak kroz stabla te napravljena njihova usporedba s rekurzivnim algoritmima. FM algoritam unaprijeđen je u odnosu na prvobitnu inačicu. Za njega je implementacija pomno obrazložena, a za vrlo opsežan TFM algoritam u bitnim crtama. Napravljena je iscrpna analiza vremenske složenosti FM algoritma za slučajeve različitih glavnih stabala i različitih načina njegova rada. Općenito je ta složenost eksponencijalna u raznim linearnim kombinacijama parametara L i D, a u najgorem slučaju u njihovoj razlici 2D - L. DSA program primijenjen je za modeliranje brojnih sustava. Za njihova su raščlambena ε-stabla utvrđene krajnje razine statističke konzistentnosti, odnosno maksimalne visine korektnih glavnih stabala u kojima će se nalaziti morfovi. Te su razine teorijski povezane s točnosti numeričkog izračuna i s Lyapunovljevim eksponentom sustava. Za periodične i sustave zadane pravilom te za potpuno kvazistohastičke sustave dobivaju se točni SFA-modeli i uz uporabu FM i TFM algoritama. To vrijedi i za logističko preslikavanje u nastupu kaosa na kraju puta udvostručavanjem perioda, za koje porastom duljine L morfa broj stanja SFA divergira. Tu su dobiveni SFA-modeli plauzibilniji od prethodno poznatih, a na višoj je razini potvrđen konačan registarski stroj. Logistička preslikavanja u kaosu na mahove, za Misiurewiczev parametar i nadomak potpunog kaosa pokazuju strukturu izmiješanu s kvazistohastičnosti. Sveobuhvatno modeliranje ovih sustava za zadani L i sve manji δ daje niz sve preciznijih SFA-modela, sa sve većim brojem stanja. Na temelju njihovih grafova i izračunanih informacijsko-teorijskih pokazatelja odabrani su oni najreprezentativniji. Neki su od njih potvrđeni i TFM algoritmom. Takav složen postupak modeliranja učinkovito obavlja humani modelar s pomoću DSA programa. Time je ustanovljena funkcionalna modelirajuća platforma, pogodna za daljnju nadogradnju i poopćenja.

Izvorni jezik
Hrvatski

Znanstvena područja
Računarstvo

Napomena
Abstract in English is available at the beginning of the enclosed full text in Croatian.

POVEZANOST RADA