(3.236.228.250) 您好！臺灣時間：2021/04/17 13:16

### 詳目顯示:::

:

• 被引用:1
• 點閱:114
• 評分:
• 下載:8
• 書目收藏:0
 列舉組合物件在組合數學中一直都是重要的研究項目，而我們稱隨機產生組合物件的演算法為取樣。取樣在電腦科學中有很多的應用，像是程式正確性的測試等等，而且數學家也可以利用取樣的結果去驗證一些數學性質。我們利用蒙地卡羅馬可夫鍊的方法設計出k 連通圖形的取樣方法，而我們可以證明出此方法可以近似均勻分布的產生k連通圖形，並且我們也證明了這演算法是快速收斂的。
 Enumerating combinatorial objects is an important research topic in combinatorics. Algorithms for random generating combinatorial objects are called sampling. Sampling has many applications in computer science, for example program testing. Mathematicianscan use sampling to verify combinatorial property.We developed a simple algorithm to sample k-connected graphs based on Markov Chain Monte Carlo method. This algorithm generates graphs at approximately uniform distribution, and we prove it is rapidly mixing
 AbstractPrefaceAcknowledgementsGlossary of NotationTable of Contents1 Introduction 11.1 Combinatorial Generation1.2 Markov Chain Monte Carlo Method1.3 Previous Work1.4 Contribution1.5 Organization2 Preliminaries2.1 Graph Theory2.2 Markov Chain2.3 Markov Chain Monte Carlo Method2.4 Mixing-time and Rapidly Mixing2.5 Techniques for Analyzing Mixing-time3 Algorithm4 Mixing Time5 Future WorkEpilogueAppendix A Bibliography
 [1] Be’la Bolloba’s. Random Graphs. Cambridge University Press, second edition, September 2001.[2] R. Bubley and M. Dyer. Path coupling: A technique for proving rapid mixing in markov chains. In FOCS ’97: Proceedings of the 38th Annual Symposium on Foundations of Computer Science (FOCS ’97), page 223, Washington, DC, USA, 1997. IEEE Computer Society.[3] M R Jerrum, L G Valiant, and V V Vazirani. Random generation of combinatorial structures from a uniform. Theoretical Computer Science, 43(2-3):169–188, 1986.[4] Ravi Kannan, Prasad Tetali, and Santosh Vempala. Simple markov-chain algorithms for generating bipartite graphs and tournaments. In SODA ’97: Proceedings of the eighth annual ACM-SIAM symposium on Discrete algorithms, pages 193–200, Philadelphia, PA, USA, 1997. Society for Industrial and Applied Mathematics.[5] J. H. Kim and V. H. Vu. Generating random regular graphs. Combinatorica, 26(6):683–708, 2006.[6] Colin McDiarmid, Angelika Steger, and Dominic J. A. Welsh. Random planar graphs. Journal of Combinatorial Theory, Series B, 93(2):187–205, 2005.[7] Guy Melancon and Fabrice Philippe. Generating connected acyclic digraphs uniformly at random. Information Processing Letters, 90(4):209–213, 2004.[8] Michael Mitzenmacher and Eli Upfal. Probability and Computing: Randomized Algorithms and Probabilistic Analysis. Cambridge University Press, January 2005.[9] Dana Randall. Mixing. In FOCS ’03: Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science, page 4, Washington, DC, USA, 2003. IEEE Computer Society.[10] Alistair Sinclair. Algorithms for random generation and counting: a Markov chain approach. Springer, February 1993.[11] Alistair Sinclair and Mark Jerrum. Approximate counting, uniform generation and rapidly mixing markov chains. Information and Computation, 82(1):93–133, 1989.[12] Richard P. Stanley. Enumerative Combinatorics, volume 1. Cambridge University Press, second edition, May 2000.[13] Richard P. Stanley. Combinatorial generation. October 2003.[14] Douglas B. West. Introduction to Graph Theory. Prentice Hall, second edition, Auguest 2000.
 電子全文
 國圖紙本論文
 推文當script無法執行時可按︰推文 網路書籤當script無法執行時可按︰網路書籤 推薦當script無法執行時可按︰推薦 評分當script無法執行時可按︰評分 引用網址當script無法執行時可按︰引用網址 轉寄當script無法執行時可按︰轉寄

 1 採用系統模擬技術探討車輛環保問題

 1 1. 丁文琴、謝伸裕，水中秤重、生物電阻和皮脂厚測量法對體脂肪百分比之評估比較，體育學報，19，157-168，1995。

 1 應用客戶端JavaScript於改善視障者專用搜尋引擎之介面 2 網際網路上支援多媒體串流之封包排程與頻寬保留之研究 3 圖形上的均勻著色 4 移轉投票者之初探研究-以2004-2008年總統選舉為例 5 ModelingtheDynamicsofIntracellularSignalTransductionNetworksbyGeneticAlgorithm-basedBooleanDelayModel 6 指數壽命分佈串聯系統之隱蔽區間資料加速壽命試驗之可靠度分析 7 視窗系統上建置顯示有機分子的圖形化使用者介面程式 8 DOBALI:以結構區塊為基準的多重序列比對工具 9 中草藥資料庫之建置與應用 10 FRESCO:Frequency-basedRE-SequencingtoolbasedonCO-clusteringsegmentationforshortreads-acasestudyofmicro-RNAs 11 廣播支配問題之研究 12 使用關聯法則預測與分析台灣樂透彩 13 GeneticEvolutionandPathologicalAnalysisofEnterovirus71 14 可萃取基因調控模組之多階式群聚法 15 ASystematicalApproachforDiscoveringGeneRegulatoryBindingMotifsinSilico

 簡易查詢 | 進階查詢 | 熱門排行 | 我的研究室