跳到主要內容

臺灣博碩士論文加值系統

(35.175.191.36) 您好!臺灣時間:2021/08/02 13:04
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

我願授權國圖
: 
twitterline
研究生:林宜靜
研究生(外文):Yi Ching Lin
論文名稱:k分支樹序列在格雷碼順下之定序演算法
論文名稱(外文):Ranking algorithms for k-ary trees in Gray-code order
指導教授:張肇明張肇明引用關係
指導教授(外文):Jou-Ming Chang
學位類別:碩士
校院名稱:國立臺北商業技術學院
系所名稱:資訊與決策科學研究所
學門:電算機學門
學類:電算機應用學類
論文種類:學術論文
論文出版年:2013
畢業學年度:101
語文別:中文
論文頁數:21
中文關鍵詞:定序演算法反定序演算法格雷碼順序k分支樹
外文關鍵詞:ranking algorithmsunranking algorithmsGray-code orderk-ary trees
相關次數:
  • 被引用被引用:0
  • 點閱點閱:81
  • 評分評分:
  • 下載下載:0
  • 收藏至我的研究室書目清單書目收藏:0
一個k分支樹是一個有根樹、有順序的樹,且每一個內部節點均正好有k個子節點。為了描述一個k分支樹,Zaks這位學者提供了一種很好的表示法稱之為「z序列」。在這種表示法之下,van Baronaigien (2000)和Xiang等人(2000)分別設計了產生k分支樹格雷碼的演算法。基於此一格雷碼順序,Ahmadi-Adl等人(2011) 最近提出其定序及反定序演算法。若將這兩個演算法套用於n個節點的k分支樹,則其所需之時間複雜度為 O(kn^2 ) 。

在本篇論文中,我們將介紹更有效率的定序演算法。我們的改良演算法其時間複雜度及空間需求分別是 O(max{n^2,kn} ) 和 O(kn)。
A k-ary tree is a rooted and ordered tree such that every internal node has exactly k children. A well-formed representation of k-ary trees is the useing of z-sequences introduced by Zaks. Under such representations, generation of z-sequences for k-ary trees in Gray-code order was developed by van Baronaigien (2000) and Xiang et al. (2000), respectively. Based on such a Gray-code order, Ahmadi-Adl et al. (2011) recently presented ranking and unranking algorithms, and the time complexity of both algorithms for k-ary trees with n internal nodes is O(kn^2 ).

In this paper, we propose one more efficient ranking algorithm. The time complexity and space requirement in our algorithm are O(max{n^2,kn} ) and O(kn), respectively.

中文摘要 i
英文摘要 ii
致謝 iii
目錄 v
表目錄 vi
圖目錄 vii
第一章 研究背景 1
第二章 文獻探討 3
第一節 k 分支樹 3
第二節 z 序列 4
第三章 翻轉樹設計概述 6
第一節 翻轉樹 6
第二節 定序演算法 10
第四章 模擬演算法 16
第五章 結論與未來研究方向 21
參考文獻 22

[1] H. Ahrabian and A. Nowzari-Dalini (2003) Generation of t-ary trees with ballot-sequences. Int. J. Comput. Math., 80, 1243–1249.
[2] A. Ahmadi-Adl, A. Nowzari-Dalini and H. Ahrabian (2011) Ranking and unranking algorithms for loopless generation of t-ary trees. Logic J. IGPL, 19, 33–43.
[3] M.C. Er (1983) A note on generating well-formed parenthesis strings lexicographically. Comput. J.,26, 205–207.
[4] M.C. Er (1987) Lexicographic listing and ranking t-ary trees. Comput. J., 30, 569–572.
[5] J.F. Korsh (1994) Loopless generation of k-ary tree sequences. Inform. Process. Lett., 52, 243–247.
[6] J.F. Korsh and P. LaFollette (1999) Loopless generation of Gray codes for k-ary trees. Inform. Process. Lett., 70, 7–11.
[7] J.F. Korsh and P. LaFollette (2006) A loopless Gray code for rooted trees. ACM Trans. Algorithms,2, 135–152.
[8] J.F. Korsh and S. Lipschutz (1998) Shift and loopless generation of k-ary trees. Inform. Process. Lett.,65, 235–240.
[9] A. Proskurowski and F. Ruskey (1985) Binary tree Gray codes. J. Algorithms, 6, 225–238.
[10] D. Roelants van Baronaigien (2000) A loopless Gray-code algorithm for listing k-ary trees. J. Algorithms,35, 100–107.
[11] D. Roelants van Baronaigien and F. Ruskey (1988) Generating t-ary trees in A-order. Inform. Process.Lett., 27, 205–213.
[12] F. Ruskey (1978) Generating t-ary trees lexicographically. SIAM J. Comput., 7, 424–439.
[13] C.D. Savage (1997) A survey of combinatorial Gray codes. SIAM Review, 39, 605–629.
[14] A.E. Trojanowaki (1978) Ranking and listing algorithms for k-ary trees. SIAM J. Comput., 7, 492–509.
[15] V. Vajnovszki (2002) Generating a Gray code for P-sequences. J. Math. Model. Algorithms, 1, 31–41.
[16] R.-Y. Wu, J.-M. Chang and C.-H. Chang (2011) Ranking and unranking of non-regular trees with a prescribed branching sequence. Math. Comput. Model., 53, 1331–1335.
[17] R.-Y. Wu, J.-M. Chang and Y.-L. Wang (2010) Loopless Generation of non-regular trees with a prescribed branching sequence. Comput. J., 53, 661–666.
[18] R.-Y. Wu, J.-M. Chang and Y.-L. Wang (2011) Ranking and unranking of t-ary trees using RDsequences. IEICE Trans. Inform. Sys., E94-D, 226–232.
[19] R.-Y. Wu, J.-M. Chang, A.-H. Chen and C.-L. Liu, Open source for “Ranking and unranking t-ary trees in a Gray-code order”, http://ms.ntcb.edu.tw/_spade/ranking-unranking (Sep. 2012).
[20] L. Xiang, K. Ushijima and C. Tang (2000) Efficient loopless generation of Gray codes for k-ary trees. Inform. Process. Lett., 76, 169–174.
[21] S. Zaks (1980) Lexicographic generation of ordered trees. Theore. Comput. Sci., 10, 63–82.
[22] S. Zaks (1982) Generation and ranking of k-ary trees. Inform. Process. Lett., 14, 44–48.

連結至畢業學校之論文網頁點我開啟連結
註: 此連結為研究生畢業學校所提供,不一定有電子全文可供下載,若連結有誤,請點選上方之〝勘誤回報〞功能,我們會盡快修正,謝謝!
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top
1. 蔡明富(1995)。書法治療對過動兒童注意力、衝動與過動輔導效果之質性分析。國教學報,7卷,111-146頁。
2. 蔡明富(1995)。書法治療對過動兒童注意力、衝動與過動輔導效果之質性分析。國教學報,7卷,111-146頁。
3. 蔡明富(1995)。書法治療對過動兒童注意力、衝動與過動輔導效果之質性分析。國教學報,7卷,111-146頁。
4. 劉淑燕(2004)。瑜珈與高爾夫球。大專高爾夫學刊,2卷,157-165頁。
5. 劉淑燕(2004)。瑜珈與高爾夫球。大專高爾夫學刊,2卷,157-165頁。
6. 劉淑燕(2004)。瑜珈與高爾夫球。大專高爾夫學刊,2卷,157-165頁。
7. 劉美珠(1990)。瑜珈----身心合一的科學。中華體育,13卷,45-50頁。
8. 劉美珠(1990)。瑜珈----身心合一的科學。中華體育,13卷,45-50頁。
9. 劉美珠(1990)。瑜珈----身心合一的科學。中華體育,13卷,45-50頁。
10. 楊幸真(1992)。注意力與學習之相關探討。教師之友,33卷4期,28-30頁。
11. 楊幸真(1992)。注意力與學習之相關探討。教師之友,33卷4期,28-30頁。
12. 楊幸真(1992)。注意力與學習之相關探討。教師之友,33卷4期,28-30頁。
13. 陳金鼓、甘光熙(2000)。瑜珈對大學生基本體能之影響。體育與運動,104卷,49-55頁。
14. 陳金鼓、甘光熙(2000)。瑜珈對大學生基本體能之影響。體育與運動,104卷,49-55頁。
15. 陳金鼓、甘光熙(2000)。瑜珈對大學生基本體能之影響。體育與運動,104卷,49-55頁。