Naslov Modeliranje dinamičkih sustava s pomoću stohastičkih konačnih automata
Autor Robert Logožar
Mentor Leo Budin (mentor)
Član povjerenstva Siniša Srbljić (predsjednik povjerenstva)
Član povjerenstva Leo Budin (član povjerenstva)
Član povjerenstva Nikola Bogunović (član povjerenstva)
Ustanova koja je dodijelila akademski / stručni stupanj Sveučilište u Zagrebu Fakultet elektrotehnike i računarstva (Zavod za elektroniku, mikroelektroniku, računalne i inteligentne sustave) Zagreb
Datum i država obrane 1999-07-14, Hrvatska
Znanstveno / umjetničko područje, polje i grana TEHNIČKE ZNANOSTI Računarstvo
Univerzalna decimalna klasifikacija (UDC ) 004 - Računalna znanost i tehnologija. Računalstvo. Obrada podataka
Sažetak Predstavljen je novi pristup u izučavanju dinamičkih sustava, temeljen na teoriji є-strojeva J. P. Crutchfielda. Zadatak je iznaći model procesa zaključivanjem isključivo na temelju vremenskog niza. Zaokružena je formalna veza između simboličke dinamike i raščlambe vremenskog niza, te razrađena geneza stohastičkih konačnih automata (SFA) iz razreda konačnih automata (FA). Opisan je općeniti algoritam konstrukcije є-strojeva i izvršena njegova specijalizacija za rekonstrukciju SFA. Uveden je pojam statističke složenosti kao kvalitativno nove mjere za strukturnu složenost realnih sustava. Prema načelima objektnog programiranja razvijena je programska podrška koja implementira algoritam gradbe SFA. Prilikom analize vremenskog niza, kao prva razina modela javlja se raščlambeno stablo definirano kao posebna vrsta binarnog stabla. Konstruirani su izvorni algoritmi za prijeredni, poslijeredni i međuredni nerekurzivni prolaz kroz stablo. Algoritam za usporedbu (pod)stabala provjerava njihovu morfološku i vjerojatnosnu strukturu, te predstavlja okosnicu algoritma za pronalaženje jedinstvenih morfova. Jedinstveni morfovi predstavljaju stanja SFA, a uvjetne vjerojatnosti prijelaza definiraju njegova stohastička svojstva. Program je testiran i prezentiran na nizu primjera sustava zadanih pravilnim izrazima. Prikazani su dobiveni modeli SFA i izračunati statistički parametri. Izvršeno je preliminarno istraživanje nelinearnog sustava opisanog logističkom jednadžbom za više parametara te posebno za Misiurewiczev, i kritični parametar početka puta prema kaosu udvostručenjem perioda. Dobiveni rezultati su konzistentni s onima dobivenim od autora teorije. Zbog ostvarene preglednosti prikaza binarnog stabla i dodatnih informacija koje podastire algoritam nalaženja morfova, olakšano je minimiziranje modela, tj. optimiziranje njegove veličine s obzirom na vrijednost vjerojatnosnog parametra.
Sažetak (engleski) A new approach to the study of dynamical systems, based on J. P. Crutchfields’s theory of є-machines, is presented. The goal is to find a model by inferring solely from a time series. A formal connection between symbolic dynamic and the parsing of the time series is made, and stochastic finite automata (SFA) are derived from the class of finite automata (FA). The general algorithm for construction of є-machines is explained, with emphasize on its specialization to reconstruction of SFA. A notion of statistical complexity is introduced as a qualitatively new measure for structural complexity or realistic systems. Guided by the principles of object-oriented programming, a software platform for the reconstruction of SFA is implemented. A parse tree, defined as a special kind of binary tree, arises as the first level of reconstruction process. Original algorithms implementing preorder, postorder and inorder traverse through the tree structure are devised. An algorithm for comparison of (sub)trees checks their morphological and probabilistic structure, and makes a key role in the process of finding of unique morphs. The latter presents the states of SFA, and the conditional transitional probabilities provide their stochastic properties. The program was tested and presented on a number of example systems. Resulting SFA-based models and corresponding statistical parameters are given. A preliminary investigation of nonlinear system governed by Logistic map is made for several values of its parameter, especially for Misiurewicz and the critical parameter at the first period-doubling onset of chaos. The results obtained are consistent with those of the author of the theory. The clarity of the binary tree interface helps to control the results of the modeling. Additional in-formation obtained from the morph-finding algorithm enables the minimization of the model, i.e. the optimization of its size regarding the probability difference parameter.
Ključne riječi
Dinamički sustavi
simbolička dinamika
konačni automati
stohastički konačni automati (SFA)
teorija є-strojeva
deterministička složenost
statistička složenost
rekonstrukcija SFA
objektno orijentirana programska podrška
klase stabala
klasa morfova
algoritmi
sustav logističke jednadžbe
izranjanje strukture
kaos
Ključne riječi (engleski)
Dynamical systems
symbolic dynamics
finite automata
stochastic finite automata (SFA)
theory of є-machines
deterministic complexity
statistical complexity
reconstruction of SFA
object-oriented program application
tree classes
morph class
algorithms
logistic equation system
emergence of structure
chaos
Jezik hrvatski
URN:NBN urn:nbn:hr:168:491463
Studijski program Naziv: Računarstvo Vrsta studija: sveučilišni Stupanj studija: poslijediplomski znanstveni (magistarski) Akademski / stručni naziv: magistar inženjer računarstva (mag. ing. comp.)
Vrsta resursa Tekst
Način izrade datoteke Izvorno digitalna
Prava pristupa Zatvoreni pristup
Uvjeti korištenja
Datum i vrijeme pohrane 2019-03-29 14:22:37