PENGGUNAAN SPARSE MATRIKS PADA PROSES STOKASTIK DISCRITE TIME MARKOV CHAIN

FATHREZZA FIRMANULL ARIEF, Dr.-Ing. Mhd. Reza M.I Pulungan, S.Si., M.Sc. ;Faizal Makhrus,S.Kom., M.Sc

2021 | Skripsi | S1 ILMU KOMPUTER

Perkembangan teknologi dalam tataran global pada saat ini telah berkembangpesat, dan semakin tinggi pula teknologi perlu lebih andal. Salah satu metode un-tuk mengecek keandalan sebuah teknologi adalah denganmodel checking. Namundengan perkembangan teknologi, maka model checking mengalami permasalahanstate-space explosiondimana komponen kebutuhan berupa state meningkat secaraexponensial. Salah satu metode untuk meningkatkan efisiensi dari state-space ada-lah dengan meningkatkan efisiensi penyimpannan seperti penyimpanan model sparsematriks. Banyak sekali metode untuk melakukan penyimpanan model sparse matriks,salah satu yang model penyimpanan tersebut merupakan Compressed-sparse row.Pada penelitian ini, akan dilakukan eksperimen bagaimana cara kerja penyim-panan sparse matriks model Compressed-sparse row pada salah satu langkah padastokastikmodel checkingyaitu berupa transient-state danstationary-stateprobability.Metodestationary-stateyang akan digunakan merupakan metode dasar berupaPowerMethod. Data yang digunakan pada penelitian ini berupa DTMC denganstate-spaceyang sangat besar.Dari hasil Penelitian, menunjukkan bahwa metodePower methodmempunyaiwaktu kompleksitas linier dalam menjalankan model. Dalam space complexity, stora-ge yang dibutuhkan merupakan konstan O(m+n) di manammerupakan jumlah statedannmerupakan jumlah vektor transisi yang tidak nol pada setiap iterasi. Dilakuk-an juga test mengenasi konvergensi pada steady-state, diantaranya dalam penelitianini dilakukan dua metode konvergensi yaitu Konvergensi absolut dan relatif. Diantarakedua konvergensi, relatif melakukan proses running time lebih cepat dibanding Kon-vergensi Absolut tetapi mempunyai kemungkinan untuk gagal mencari konvergensi.

The development of technology globally over the recent decade has grownrapidly and with it, more demand of the technology to be more reliable. One methodto check the reliability of a technology is the use of model checking. However, withthe development of technology it comes at cost which the model checking experi-enced an explosive state-space problem where the required component in the form ofa state increased exponentially.One of the method to increase the efficiency of state-space is by storing the states using sparse matrix model. There are many methods forstoring the sparse matrix model, one of which is the Compressed-sparse row.In this study, an experiment will be carried out on how the sparse matrix stor-age of the Compressed-sparse row model works in one of the methods in the stochas-tic model examination, namely in the form of transient-state and stationary-state prob-ability. The established method to be used for this experiment is the basic method inthe form of the Power Method. The data used in this study is DTMC with a very largestate space.From the experiment results, it shows that the Power method has a linear timecomplexity in running the model. In space complexity, the required storage is a con-stant O (m + n) where m is the amount of states on DTMC and N is the non-zeronumber of transition vectors in each iteration. A test of convergence at steady-statewas also carried out, in this study we include two convergence methods, namely ab-solute and relative convergence. Between the two convergences, the running timeprocess is relatively faster than Absolute Convergence but has a chance to fail to getthe convergence.

Kata Kunci : Discrete-time Markov Chain, Sparse matriks, Proses Stokastik,Model Checking, Power Method, stationary-state