跳到主要內容

臺灣博碩士論文加值系統

(35.173.42.124) 您好!臺灣時間:2021/07/26 11:30
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

: 
twitterline
研究生:張家榮
研究生(外文):Chia-Jung Chang
論文名稱:一個尋找漢米頓迴圈之平行演算法的設計與實做
論文名稱(外文):A study on a parallel algorithm for finding Hamiltonian cycles and its implementation
指導教授:蔡英德蔡英德引用關係李冠憬
指導教授(外文):yin-te tsaikuan-ching li
學位類別:碩士
校院名稱:靜宜大學
系所名稱:資訊工程學系碩士班
學門:電算機學門
學類:電算機一般學類
論文種類:學術論文
論文出版年:2010
畢業學年度:98
語文別:中文
論文頁數:40
中文關鍵詞:Hadoop分散式系統MapReduce圖形理論漢米頓迴圈k-ordered Hamiltonian Graph
外文關鍵詞:MapReduceGraph TheoryHadoopHamiltonian Cyclek-ordered Hamiltonian GraphDistributed System
相關次數:
  • 被引用被引用:1
  • 點閱點閱:508
  • 評分評分:
  • 下載下載:73
  • 收藏至我的研究室書目清單書目收藏:0
在這個資訊豐富的時代中,電腦硬體不斷快速的演進,價格也不斷的降低,以往不斷的升級一台機器硬體的迷思似乎也逐漸的破除了。軟體在架構上應該需要適時的改進,否則沒有辦法很好的利用硬體的資源。隨著平行程式的普及化和雲端架構的提倡,並行軟體的發展已經是不能避免的。本論文提出一個基於MapReduce架構之分散式環境的圖形計算系統,並透過它來解決一些在我們以往在單機環境中需要很長時間才能解決的圖形理論問題,希望能為圖形理論研究做出一些貢獻,並且開放此系統為一個開放原始碼的專案,為並行軟體的發展和進步做出一點點貢獻。
In this information-rich era, computer hardware is revolution quickly, and its’ price are decrease at same time, too. People do not upgrade their computer constantly. Because building a multi-core CPUs or distributed system very easy now, concurrency software is more important when we use all of our own hardware resource.
With the popularity of parallel programming and cloud computing, the revolution of concurrency software is inevitable. The purpose of this paper is building a distributed graph computing system base on MapReduce programming model. With this system, we can solve some hard problem in graph theory that needs much time at single computer environment.
目錄
中文
摘 要 iii
ABSTRACT: iv
第 1 章 緒論 1
1 - 1 背景介紹 1
1 - 2 研究動機與目的 2
1 - 3 研究流程 4
1 - 4 論文架構 5
第 2 章 相關研究與文獻探討 6
2 - 1 圖形理論問題相關研究 6
2 - 1 - 1 Hypercube Graph 6
2 - 1 - 2 漢米頓迴圈(Hamiltonian Cycle) 7
2 - 1 - 3 在Qn所有漢米頓迴圈的數量 8
2 - 1 - 4 K-ordered 漢米頓圖形 (K-ordered Hamiltonian Graph) 9
2 - 2 MapReduce程式模型 9
2 - 2 - 1 介紹 9
2 - 2 - 2 執行概觀 10
2 - 2 - 3 使用MapReduce程式模型之相關研究與應用 14
第 3 章 基於MapReduce模型之演算法設計 17
第 4 章 研究結果 26
第 5 章 結論 30
參考文獻 31
參考文獻
1.Cardona, Kelvin, Jimmy Secretan, Michael Georgiopoulos, and Georgios Anagnostopoulos. "A Grid Based System for Data Mining Using MapReduce." 2007. http://cygnus.fit.edu/amalthea/pubs/Cardona_Secretan_TR-2007-02_AMALTHEA.pdf.
2.Catanzaro, Bryan, Narayanan Sundaram, and Kurt Keutzer. "A MapReduce Framework for Programming Graphics Processors." Workshop on Software Tool for MultiCore Systems. 2008.
3.Chebiryak, Yury, and Kroening Daniel. "Towards a Classification of Hamiltonian Cycles in the 6-Cube." Journal on Satisfiability, Boolean Modeling and Computation, 2008: 57-74.
4.Chu, Cheng-Tao, et al. "Map-Reduce for Machine Learning on Multicore." In Proceedings of NIPS, 2007: 281--288.
5.D. Hand, H. Mannila, P. Smyth. Principles of Data Mining. Cambridge, MA: MIT Press, (2001).
6.Dean, Jeffrey, and Sanjay Ghemawat. "MapReduce: Simplified Data Processing on Large Clusters." 6th Symposium on Operating System Design and Implementation (OSDI 2004). San Francisco, California, USA, 2004.
7.Ejov, Vladimir, and Giang T. Nguyen. "Consistent behavior of certain perturbed determinants induced by graphs." Linear Algebra and its Applications, August 1, 2009: 543-552.
8.Elsayed, Tamer, Jimmy Lin, and Douglas W. Oard. "Pairwise Document Similarity in Large Collections with MapReduce." Association for Computational Linguistics with the Human Language Technology Conference (ACL ''08: HLT). Columbus,Ohio,USA, 2008.
9.Guo, Lei, Xingwei Wang, Juan Du, and Tengfei Wu. "A new heuristic routing algorithm with Hamiltonian Cycle Protection in survivable networks." Computer Communications, June 8, 2008: 1672-1678.
10.He, Bingsheng, Wenbin Fang, Qiong Luo, Naga K. Govindaraju, and Tuyong Wang. "Mars: A MapReduce Framework on Graphics Processors." PACT ''08. Toronto, Ontario, Canada, 2008.
11.Helsgaun, Keld. "An effective implementation of the Lin–Kernighan traveling salesman heuristic." European Journal of Operational Research, October 1, 2000: 106-130.
12.Janez Aleš, Bojan Mohar, Tomaž Pisanski. "Heuristic search for Hamilton cycles in cubic graphs." Discrete Mathematics,, February 6, 2007: 303-309.
13.JohnJ.Bartholdi, III, and Paul Goldsman. "The vertex-adjacency dual of a triangulated irregular network has a Hamiltonian cycle." Operations Research Letters, July 2004: 304-308.
14.Laclavík, Michal, Martin Šeleng, and Ladislav Hluchý. "Towards Large Scale Semantic Annotation Built on MapReduce Architecture." In Proceedings of ICCS 2008, 2008: 331-338.
15.Liu, Xian, and Gunther F. Schrack. "A heuristic approach for constructing symmetric Gray codes." Applied Mathematics and Computation, 2004: 55–63.
16.Matsunaga, Andréa, Maurício Tsugawa, and José Fortes. "CloudBlast: Combining MapReduce and Virtualization on Distributed Resoureces for Bioinfomatics Applications." Fourth IEEE International Conference on eScience. 2008.
17.NetCraft. June 2010 Web Server Survey. http://news.netcraft.com/archives/2010/06/16/june-2010-web-server-survey.html#more-2249 (accessed 6 22, 2010).
18.Sadasivam, G. Sudha, and G. Baktavatchalam. "A novel approach to multiple sequence alignment using Hadoop data grids." International workshop on massive data analytics over the cloud (MDAC 2010). 2010.
19.Sárközy, Gábor N. "A fast parallel algorithm for finding Hamiltonian cycles in dense graphs." Discrete Mathematics, April 6, 2009: 1611-1622.
20.SchatzC.Michael. “CloudBurst: highly sensitive read mapping with MapReduce.” Bioinformatics, 2009: 1363-1369.
21.Wang, Nen-Chung, Cheng-Pang Yen, and Chih-Ping Chu. "Multicast communication in wormhole-routed symmetric networks with hamiltonian cycle model." Journal of Systems Architecture, March 2005: 165-183.
22.West, D. B. Introduction to Graph Theory, 2nd ed. Englewood Cliffs, NJ: Prentice-Hall, 2000.
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top
無相關期刊