Tez No	İndirme	Tez Künye	Durumu
112578	Bu tezin, veri tabanı üzerinden yayınlanma izni bulunmamaktadır. Yayınlanma izni olmayan tezlerin basılı kopyalarına Üniversite kütüphaneniz aracılığıyla (TÜBESS üzerinden) erişebilirsiniz.	Analysis of large Markov chains using stochastic automata networks / Büyük Markov zincirlerinin rassal özdevinimli ağ kullanılarak çözümlemesi Yazar:OLEG GUSAK Danışman: DOÇ. DR. TUĞRUL DAYAR Yer Bilgisi: İhsan Doğramacı Bilkent Üniversitesi / Mühendislik ve Fen Bilimleri Enstitüsü / Bilgisayar Mühendisliği Ana Bilim Dalı Konu:Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol = Computer Engineering and Computer Science and Control Dizin:Birleştirilebilirlik = Compatibility ; Markov zinciri = Markov chain ; Rastgele özdevinir ağlar = Stochastic automata networks	Onaylandı Doktora İngilizce 2001 134 s.
VI ÖZET Oleg Gusak Bilgisayar Mühendisliği, Doktora Tez Yöneticisi: Doç. Dr. Tuğrul Dayar Temmuz, 2001 Bu çalışma, rassal özdevinimli ağ olarak modellenen sonlu Markov zincirlerinin çözümlemesi alanında var olan araştırmaya katkıda bulunmaktadır, ilk olarak, bu tez Markov zincirlerinin neredeyse tamamen bölünebilirlik kavramını rassal özdevinimli ağlara genişleterek, alttaki Markov zincirinin çözülmesinde aslında var olan zorluğun kestirilmesini ve bu kavrama dayalı çözüm tekniklerinin araştırılmasını mümkün kılmaktadır. Bir rassal özdevinimli ağın altındaki Markov zincirinin neredeyse tamamen bölünebilir bloklara ayrışmış halini bul manın basit yolu, sisteme karşı gelen matrisin sıfırdan farklı elemanlarının hesap edilmesini gerektirir. Bu, çok büyük sistemler için bellek ve uygu lama zamanı sınırlamalarından dolayı seyrek matris gösterimiyle dahi mümkün değildir. Bu tezde, bu problem için, verilen bir rassal özdevinimli ağın herbir bileşenini çözümlemeye dayalı, bir etkili ayrıştırmalı çözüm algoritması sunul maktadır. Sayısal sonuçlar, verilen algoritmanın basit yöntemden çok daha iyi randıman verdiğini göstermektedir. ikinci olarak, bu çalışma bir rassal özdevinimli ağa karşı gelen matris için kontrol edilmesi kolay birleştirilebilirlik koşulları vermektedir. Sisteme karşı gelen matrisin tensör gösteriminin neden olduğu birleştirilebilir bir bölünme var olduğunda, rassal özdevinimli ağ modelinin altındaki Markov zincirinin değişmez durum dağılımının etkili bir dolaylı birleştirme-ayrıştırma algorit ması kullanılarak bulunabileceği gösterilmektedir. Sürekli-zamanlı ve kesintili- zamanlı rassal özdevinimli ağ modelleri üzerinde yapılan deneylerin sonuçları, önerilen algoritmanın son derece çetin bir rakip olan blok Gauss-Seidel'den hem ardışık tekrar sayısında hem de çözüme yakınsama için geçen süre yönünden daha iyi randıman verdiğini göstermektedir.vıı Son olarak, dolaylı birleştirme-ayrıştırma algoritmasının başarımı, birleştiri lebilir bölünmelerde nispi olarak büyük bloklara sahip sürekli-zamanlı rassal özdevinimli ağlar üzerinde araştırılmaktadır. Dolaylı birleştirme-ayrıştırma algoritmasının herbir ardışık tekrarında, büyük blokları çözmede karşılaşılan güçlükleri aşmak için rassal özdevinimli ağlar için blok Gauss-Seidel'm özyinele meli uygulaması kullanılmaktadır. Dolaylı birleştirme-ayrıştırma algoritmasının başarımı blok Gauss-Seidel'inki ile karşılaştırılmaktadır. Deney sonuçları, dolaylı birleştirme-ayrıştırmayı blok Gauss-Seidel'i geçecek şekilde ayarlamanın müm kün olduğunu göstermektedir. Anahtar kelimeler: Markov zinciri, rassal özdevinimli ağlar, neredeyse tama men bölünebilirlik, birleştirilebilirlik, dolaylı birleştirme-ayrıştırma.
IV ABSTRACT ANALYSIS OF LARGE MARKOV CHAINS USING STOCHASTIC AUTOMATA NETWORKS Oleg Gusak Ph.D. in Computer Engineering Advisor: Assoc. Prof. Tuğrul Dayar July, 2001 This work contributes to the existing research in the area of analysis of fi nite Markov chains (MCs) modeled as stochastic automata networks (SANs). First, this thesis extends the near complete decomposability concept of Markov chains to SANs so that the inherent difficulty associated with solving the un derlying MC can be forecasted and solution techniques based on this concept can be investigated. A straightforward approach to finding a nearly completely decomposable (NCD) partitioning of the MC underlying a SAN requires the computation of the nonzero elements of its global generator. This is not feasi ble for very large systems even in sparse matrix representation due to memory and execution time constraints. In this thesis, an efficient decompositional so lution algorithm to this problem that is based on analyzing the NCD structure of each component of a given SAN is introduced. Numerical results show that the given algorithm performs much better than the straightforward approach. Second, this work specifies easy to check lumpability conditions for the generator of a SAN. When there exists a lumpable partitioning induced by the tensor representation of the generator, it is shown that an efficient iterative aggregation-disaggregation algorithm (IAD) may be employed to compute the steady state distribution of the MC underlying the SAN model. The results of experiments with continuous-time and discrete-time SAN models show that the proposed algorithm performs better than the highly competitive block Gauss- Seidel (BGS) in terms of both the number of iterations and the time to converge to the solution. Finally, the performance of the IAD algorithm on continuous-time SANsV having relatively large blocks in lumpable partitionings is investigated. To overcome difficulties associated with solving large diagonal blocks at each iter ation of the IAD algorithm, the recursive implementation of BGS for SANs is employed. The performance of IAD is compared with that of BGS. The results of experiments show that it is possible to tune IAD so that it outperforms BGS. Key words: Markov chain, Stochastic automata network, Near complete de- composability, lumpability, iterative aggregation-disaggregation.