跳到主要內容

臺灣博碩士論文加值系統

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

詳目顯示

: 
twitterline
研究生:周哲熙
研究生(外文):Chou Che-Hsi
論文名稱:在格雷碼順序下以無迴圈演算法列出k分支樹序列
論文名稱(外文):Loopless Algorithms for Listing k-ary Tree Sequences in Gray-code Order
指導教授:陳恩航陳恩航引用關係
指導教授(外文):Chen An-Hang
學位類別:碩士
校院名稱:國立臺北商業技術學院
系所名稱:資訊與決策科學研究所
學門:電算機學門
學類:電算機應用學類
論文種類:學術論文
論文出版年:2013
畢業學年度:101
語文別:中文
論文頁數:35
中文關鍵詞:無迴圈演算法字典編碼順序格雷碼順序k分支樹
外文關鍵詞:loopless algorithmslexicographic ordergray-code orderk-ary trees
相關次數:
  • 被引用被引用:0
  • 點閱點閱:111
  • 評分評分:
  • 下載下載:5
  • 收藏至我的研究室書目清單書目收藏:0
一個 k分支樹是一個有根樹,亦是一個有順序的樹,且每個內部節點恰有 $k$個子樹 (k>=2)。Zaks 在 1980年建議採用一種最自然的表示法稱之為「x序列」或是「z序列」來描述一個 k分支樹。在採用 z序列表示法之下,van Baronaigien 和 Xiang 等人在 2000年分別設計了無迴圈演算法以產生 k分支樹之格雷碼。在本篇論文中,我們將介紹一個新的無迴圈演算法,它以 z序列表示法來產生 k分支樹之格雷碼。此一新的演算法所需記憶體空間比目前現有的演算法來的精簡,且執行效能更好。此外,將我們的演算法稍加修改後可以同時產生 k分支樹的 x序列,具同樣的精簡度及效能。
A k-ary tree is a rooted and ordered tree such that every internal node has exactly k children (k>=2). A natural representation of k-ary trees is the use of x-sequences or z-sequences introduced by Zaks in 1980. Under such representations, a loopless algorithm that generates z-sequences of k-ary trees in Gray-code order was developed by van Baronaigien and Xiang et al. in 2000, respectively. In this paper, we present a new loopless algorithm to generate z-sequences of k-ary trees in Gray-code order. The development of our algorithm is in need of less memory space and is more efficient than the existing algorithms. Moreover, with a slight modification, our algorithm can generate x-sequences of k-ary trees such that only one pair of positions have different binary codes for two successive sequences.
中文摘要..........................i
英文摘要..........................ii
誌謝................................iii
目錄................................v
表目錄.............................vii
圖目錄.............................viii
一、緒論..........................1
1.1 研究背景....................1
1.2 研究動機與目的...........4
1.3 論文架構....................5
二、文獻探討....................7
三、主要結果....................19
3.1 k分支樹的結構性質......19
3.2 翻轉樹........................21
3.3 無迴圈演算法..............23
四、結論與未來研究方向....31
4.1 結論...........................31
4.2 未來研究方向..............32
參考文獻..........................33
[1] H. Ahrabian, A. Nowzari-Dalini, and E. Salehi. Gray code algorithm for listing k-ary trees. Studies in Information and Control, 13:243–251, 2004.
[2] G. Ehrlich. Loopless algorithms for generating permutations, combinations, and other combinatorial configurations . Journal of the ACM, 20:500–513, 1973.
[3] M.C. Er. A note on generating well-formed parenthesis strings lexicographically. Computer Journal, 26:205–207, 1983.
[4] M.C. Er. Lexicographic listing and ranking t-ary trees. Computer Journal, 30:569–572, 1987.
[5] Frank GRAY. Pulse code communication, March 17 1953. US Patent 2,632,058.
[6] J.F. Korsh. Loopless generation of k-ary tree sequences. Information Processing
Letters, 52:243–247, 1994.
[7] J.F. Korsh and P. LaFollette. Loopless generation of Gray codes for k-ary trees.
Information Processing Letters, 70:7–11, 1999.
[8] J.F. Korsh and P. LaFollette. A loopless Gray code for rooted trees. ACM
Transactions on Algorithms, 2:135–152, 2006.
[9] J.F. Korsh and S. Lipschutz. Shift and loopless generation of k-ary trees. Information Processing Letters, 65:235–240, 1998.
[10] Joan M Lucas. The rotation graph of binary trees is hamiltonian. Journal of Algorithms, 8:503–535, 1987.
[11] J. Pallo. Enumerating, ranking and unranking binary trees. Computer Journal, 29:171–175, 1986.
[12] A. Proskurowski. On the generation of binary trees. Journal of the ACM (JACM), 27:1–2, 1980.
[13] A. Proskurowski and F. Ruskey. Binary tree Gray codes. Journal of Algorithms, 6:225–238, 1985.
[14] F. Ruskey. Generating t-ary trees lexicographically. SIAM Journal on Computing, 7:424–439, 1978.
[15] F. Ruskey and T.C Hu. Generating binary trees lexicographically. SIAM Journal on Computing, 6:745–758, 1977.
[16] C.D. Savage. A survey of combinatorial Gray codes. SIAM Review, 39:605–629, 1997.
[17] Trojanowski and Anthony E. Ranking and listing algorithms for k-ary trees. SIAM Journal on Computing, 7:492–509, 1978.
[18] V. Vajnovszk. Constant time algorithm for generating binary tree Gray codes. Studies in Information and Control, 5:15–21, 1996.
[19] V. Vajnovszk. On the loopless generation of binary tree sequences. Information Processing Letters, 68:113–117, 1998.
[20] V. Vajnovszk. Generating a Gray code for P-sequences. Journal of Mathemat- ical Modelling and Algorithms, 1:31–41, 2002.
[21] D.R. van Baronaigien. A loopless algorithm for generating binary tree sequences. Information Processing Letters, 39:189–194, 1991.
[22] D.R. van Baronaigien. A loopless Gray-code algorithm for listing k-ary trees. Journal of Algorithms, 35:100–107, 2000.
[23] D.R. van Baronaigien and F. Ruskey. Generating t-ary trees in a-order. Information Processing Letters, 27:205–213, 1988.
[24] S.G. Williamson. Combinatorics for Computer Science. Computer Science Press, Rockville, MD, 1985.
[25] R.-Y. Wu, J.-M. Chang, and Y.-L. Wang. Loopless Generation of non-regular trees with a prescribed branching sequence. Computer Journal, 53:661–666, 2010.
[26] L. Xiang, C. Tang, and K. Ushijima. Grammar-oriented enumeration of binary trees. The Computer Journal, 40:278–291, 1997.
[27] L. Xiang and K. Ushijima. Grammar-oriented enumeration of arbitrary trees and arbitrary k-ary trees. IEICE TRANSACTIONS on Information and Systems, 82:1245–1253, 1999.
[28] L. Xiang, K. Ushijima, and C. Tang. Efficient loopless generation of Gray codes for k-ary trees. Information Processing Letters, 76:169–174, 2000.
[29] L. Xiang, K. Ushijima, and C. Tang. On generating k-ary trees in computer representation. Information processing letters, 77:231–238, 2001.
[30] S. Zaks. Lexicographic generation of ordered trees. Theoretical Computer Science, 10:63–82, 1980.
[31] D. Zerling. Generating binary trees using rotations. Journal of the ACM (JACM), 32:694–701, 1985.
連結至畢業學校之論文網頁點我開啟連結
註: 此連結為研究生畢業學校所提供,不一定有電子全文可供下載,若連結有誤,請點選上方之〝勘誤回報〞功能,我們會盡快修正,謝謝!
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top