請用此 Handle URI 來引用此文件:
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/34271
完整後設資料紀錄
DC 欄位 | 值 | 語言 |
---|---|---|
dc.contributor.advisor | 趙坤茂(Kun-Mao Chao) | |
dc.contributor.author | Chih-Huai Cheng | en |
dc.contributor.author | 鄭智懷 | zh_TW |
dc.date.accessioned | 2021-06-13T06:00:47Z | - |
dc.date.available | 2006-06-27 | |
dc.date.copyright | 2006-06-27 | |
dc.date.issued | 2006 | |
dc.date.submitted | 2006-06-23 | |
dc.identifier.citation | [1] Bae, S.E. and Takaoka, T.: Algorithms for the problem of k maximum sums and a VLSI algorithm for the k maximum subarrays problem, Proceedings of the 7th International Symposium on Parallel Architectures, Algorithms and Networks, 247–253, 2004.
[2] S.E. Bae and T. Takaoka, Improved Algorithms for the K-Maximum Subarray Problem for Small K, Proceedings of the 11th Annual International Computing and Combinatorics Conference, 621-631, 2005. [3] Bengtsson F. and Chen J.: Efficient Algorithms for k Maximum Sums, Proceedings of International Symposium on Algorithms And Computation, LNCS 3341, 137–148, 2004. [4] Bengtsson F. and Chen J.: A Note on Ranking k Maximum Sums, 2005. [5] Bentley, J.: Programming Pearls: Algorithm Design Techniques, Communications of the ACM, 865–871, 1984. [6] Bentley, J.: Programming Pearls: Perspective On Performance, Communications of the ACM, 1087–1092, 1984. [7] Chen, K.Y. and Chao, K.M.: On the Range Maximum-Sum Segment Query Problem, Proceedings of International Symposium on Algorithms And Computation, LNCS 3341, 294–305, 2004. [8] Cormen T.H., Leiserson C.E., Rivest R.L. and Stein C.:Introduction to Algorithms, the MIT Press: 2nd Edition, 185–196, 1999. [9] T.-H. Fan, S. Lee, H.-I Lu, T.-S. Tsou, T.-C. Wang, and A. Yao. An Optimal Algorithm for Maximum-Sum Segment and Its Application in Bioinformatics. CIAA, LNCS 2759, 251–257, 2003. [10] Fukuda, T., Morimoto, Y., Morishita, S. and Tokuyama, T.: Data mining using two-dimensional optimized association rules: Scheme, algorithms, and visualization, Proceedings of the 1996 ACM SIGMOD International Conference on Management of Data, 13–23,1996. [11] Grenander, U.: Pattern Analysis, Springer-Verlag, New York, 1978. [12] X. Huang. An Algorithm for Identifying Regions of a DNA Sequence that Satisfy a Content Requirement. CABIOS, 10: 219–225, 1994. [13] Y.-L. Lin, X. Huang, T. Jiang, and K.-M. Chao, MAVG: Locating Non-Overlapping Maximum Average Segments in a Given Sequence, Bioinformatics, 19:151-152, 2003. [14] Y.-L. Lin, T. Jiang, and K.-M. Chao. Efficient Algorithms for Locating the Lengthconstrained Heaviest Segments with Applications to Biomolecular Sequence Analysis. Journal of Computer and System Sciences, 65: 570–586, 2002. [15] Ruzzo, W.L. and Tompa M.: A Linear Time Algorithm for Finding All Maximal Scoring Subsequences, Proceedings of the 7th International Conference on Intelligent Systems for Molecular Biology, 234–241, 1999. [16] Takaoka, T.: Efficient Algorithms for the Maximum Subarray Problem by Distance Matrix Multiplication, Electronic Notes in Theoretical Computer Science, 61, 1–10, 2002. [17] Tamaki, T. and Tokuyama, T.: Algorithms for the maximum subarray problem based on matrix multiplication, Proceedings of the Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 446–452, 1998. | |
dc.identifier.uri | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/34271 | - |
dc.description.abstract | 找尋最大總和區間是個既基礎且重要的數列分析問題。給定一個實數數列A,我們找區間A(i,j)使得該區間的總和為最大。這類問題在生物序列上有找重複區段、富含C,G的區域以及設計低時間複雜度的篩選器等應用。本篇碩士論文探討兩種最大總和區間的變型問題,並提出解決的快速演算法。
我們研究前k大總和區間問題並且提出時間複雜度為O(n+klogk)的演算法。當我們要求答案要按照總和由大到小排列,我們是第一個提出k < n情況下的最佳解。考慮前k大總和區間問題在d維以及每維長度為n的情形下,我們的演算法時間複雜度是O(n^{2d-1}+klogk)。此外,我們也提出最大總和區間符合平均值下限或上限的線性演算法。 | zh_TW |
dc.description.provenance | Made available in DSpace on 2021-06-13T06:00:47Z (GMT). No. of bitstreams: 1 ntu-95-R93922013-1.pdf: 653751 bytes, checksum: 6aa86abc08438bd41202c1f23e87e829 (MD5) Previous issue date: 2006 | en |
dc.description.tableofcontents | Contents
Title ii Tabel of Contents ii Acknowledgements iii Abstract in Chinese iv Abstract v 1 Introduction 1 2 The k Maximum-Sum Segment Problem 3 2.1 An Iterative Partial-Table Building Approach . . . . . . . . . . . . . . . 4 2.2 Improving on the Time Complexity in the k < n Case . . . . . . . . . . . 9 2.3 The Problem of k Maximum-Sum Segments in Order . . . . . . . . . . . 10 2.4 The k Maximum-Sum Subarray Problem . . . . . . . . . . . . . . . . . . 12 3 The Problem of the Maximum-Sum Segment Satisfying an Average Constraint 15 3.1 A Linear-time Algorithm for Finding the Maximum-Sum Segment Satisfying an Average Lower Bound . . . . . . . . . . . . . . . . . . . . . . . 15 3.2 A Linear-time Algorithm for Finding the Maximum-Sum Segment Satisfying an Average Upper Bound . . . . . . . . . . . . . . . . . . . . . . . 21 4 Future Works 24 4.1 Concluding Remarks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 | |
dc.language.iso | en | |
dc.title | 最大總和區間相關變型題的快速演算法 | zh_TW |
dc.title | Efficient Algorithms for Some Variants of the Maximum-Sum Segment Problem | en |
dc.type | Thesis | |
dc.date.schoolyear | 94-2 | |
dc.description.degree | 碩士 | |
dc.contributor.oralexamcommittee | 姜濤(Tao Jiang),張雅惠(Ya-Hui Chang) | |
dc.subject.keyword | 最大總和區間, | zh_TW |
dc.subject.keyword | maximum-sum segment, | en |
dc.relation.page | 26 | |
dc.rights.note | 有償授權 | |
dc.date.accepted | 2006-06-23 | |
dc.contributor.author-college | 電機資訊學院 | zh_TW |
dc.contributor.author-dept | 資訊工程學研究所 | zh_TW |
顯示於系所單位: | 資訊工程學系 |
文件中的檔案:
檔案 | 大小 | 格式 | |
---|---|---|---|
ntu-95-1.pdf 目前未授權公開取用 | 638.43 kB | Adobe PDF |
系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。