臺灣博碩士論文加值系統

波動序列在生活中很常見，舉凡金融、天氣與醫療，因此Chen與Yang於2020年提出最長波動子序列(LWS)問題，且Chang與Yang於2021年提出最長共同波動子序列(LCWS)問題。然而LWS和LCWS都不允許波動序列有誤差，但現實的波動序列存在些微誤差，故我們一般化LCWS問題成最長共同近乎波動子序列(LCaWS)問題。
LCaWS問題有兩個子問題，分別為LCaWSt問題與LCaWSr問題。給定兩條數字序列A、B、一條趨勢序列T、段數r與公差c，LCaWSt問題要找出A與B的最長共同波動子序列，其趨勢與T的前綴一致，且由近乎遞增與遞減段交替組成；LCaWSr問題則要找出A與B的最長共同波動子序列，其序列最多由r段近乎遞增與遞減段交替組成。最後我們花O(mnc)時間與O(nc)空間解決LCaWSt問題，且花O(rmnc)時間與O(rnc)空間解決LCaWSr問題，其m和n分別為A和B的長度。

Wave sequences are common in life, such as finance, weather, and medicine. Chen and Yang first defined the longest wave subsequence (LWS) problem in 2020, and then Chang and Yang defined the longest common wave subsequence (LCWS) problem in 2021. However, both the LWS and LCWS do not allow any errors in wave sequences. However, slight errors usually occur in real wave sequences, so we define the longest common almost wave subsequence (LCaWS) problem, a generalized variant of the LCWS problem.
The LCaWS problem has two subproblems, the LCaWSt problem and the LCaWSr problem. Given two numeric sequences A and B, a tolerance (error) constant c, a trend sequence T and the number r of segments, the LCaWSt problem aims to find the longest common subsequence of A and B, consisting of the almost increasing and decreasing segments alternatively, whose trend sequence follows the prefix of T . The LCaWSr problem aims to find the longest common subsequence of A and B, consisting of at most r segments, where the almost increasing segments alternate with the almost decreasing segments. We propose an algorithm for solving the LCaWSt problem in O(mnc) time and O(nc) space, and an algorithm for solving the LCaWSr problem in O(rmnc) time and O(rnc) space, where m and n denote the lengths of A and B, respectively, m ≥ n.

THESIS VERIFICATION FORM . . . . . . . . . . . . . . . . . . . . . . i
ACKNOWLEDGMENTS . . . . . . . . . . . . . . . . . . . . . . . . . . . iii
CHINESE ABSTRACT . . . . . . . . . . . . . . . . . . . . . . . . . . . . iv
ABSTRACT . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . v
LIST OF FIGURES . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ix
LIST OF TABLES . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xi
LIST OF SYMBOLS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xvii
Chapter 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
Chapter 2. Preliminaries . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
2.1 The Longest Common Almost Increasing Subsequence . . . . . . . . . 9
2.2 The Longest Almost Wave Subsequence . . . . . . . . . . . . . . . . . 12
2.2.1 The Longest Almost Wave Subsequence with Trend . . . . . . 15
2.2.2 The Longest Almost Wave Subsequence within r Segments . . 15
2.3 The Longest Common Wave Subsequence . . . . . . . . . . . . . . . . 17
2.3.1 The Longest Common Wave Subsequence with Trend . . . . . 17
2.3.2 The Longest Common Wave Subsequence within r Segments . 22
Chapter 3. Our Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . 25
3.1 The Longest Common Almost Wave Subsequence Problem with Trend 25
3.1.1 The Algorithm for the LCaWSt Problem . . . . . . . . . . . . 26
3.1.2 The Correctness and Complexity . . . . . . . . . . . . . . . . 36
3.2 The Longest Common Almost Wave Subsequence Problem within r
Segments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
3.2.1 The Algorithm for the LCaWSr Problem . . . . . . . . . . . . 39
3.2.2 The Correctness and Complexity . . . . . . . . . . . . . . . . 54
Chapter 4. Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57
BIBLIOGRAPHY . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59
Appendixes
A. Appendixes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61
A.1 The Examples of the Longest Common Almost Wave Subsequence
Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61

[1] M. R. Alam and M. S. Rahman, "A divide and conquer approach and a work-optimal parallel algorithm for the lis problem," Information Processing Letters, Vol. 113, No. 13, pp. 470-476, 2013.
[2] S. Bespamyatnikh and M. Segal, "Enumerating longest increasing subsequences and patience sorting," Information Processing Letters, Vol. 76, No. 1-2, pp. 7-11, 2000.
[3] M. T. H. Bhuiyan, M. R. Alam, and M. S. Rahman, "Computing the longest common almost-increasing subsequence," Theoretical Computer Science, Vol. 930, pp. 157-178, 2022.
[4] Y.-C. Chang and C.-B. Yang, "The longest common wave subsequence problem," The 38th Workshop on Combinatorial Mathematics and Computation Theory, Taipei, Taiwan, pp. 9-17, 2021.
[5] G.-Z. Chen and C.-B. Yang, "The longest wave subsequence problem: Generalizations of the longest increasing subsequence problem," The 37th Workshop on Combinatorial Mathematics and Computation Theory, Kaohsiung, Taiwan, pp. 28-33, 2020.
[6] M. Crochemore and E. Porat, "Fast computation of a longest increasing subsequence and application," Information and Computation, Vol. 208, No. 9, pp. 1054-1059, 2010.
[7] A. L. Delcher, S. Kasif, R. D. Fleischmann, J. Peterson, O. White, and S. L. Salzberg, "Alignment of whole genomes," Nucleic Acids Research, Vol. 27, No. 11, pp. 2369-2376, 1999.
[8] A. Elmasry, "The longest almost-increasing subsequence," Information Processing Letters, Vol. 110, No. 16, pp. 655-658, 2010.
[9] J. W. Hunt and T. G. Szymanski, "A fast algorithm for computing longest common subsequences," Communications of the ACM, Vol. 20, pp. 350-353, 1977.
[10] A. Khelassi1, S.-N. Yelles-Chaouche, and F. Benais, "Multi-arrhythmias detection with an XML rule-based system from 12-Lead Electrocardiogram," Electronic Physician, Vol. 9, pp. 4357-4363, 2017.
[11] S.-C. Lin, "The longest almost wave subsequence problem," Master''s Thesis, Department of Computer Science and Engineering, National Sun Yat-sen University, Kaohsiung, Taiwan, 2022.
[12] S.-F. Lo, K.-T. Tseng, C.-B. Yang, and K.-S. Huang, "A diagonal-based algorithm for the longest common increasing subsequence problem," Theoretical Computer Science, Vol. 815, pp. 69-78, 2020.
[13] J. M. Moosa, M. S. Rahman, and F. T. Zohora, "Computing a longest common subsequence that is almost increasing on sequences having no repeated elements," Journal of Discrete Algorithms, Vol. 20, pp. 12-20, 2013.
[14] C. Schensted, "Longest increasing and decreasing subsequences," Canadian Journal of Mathematics, Vol. 13, pp. 179-191, 1961.
[15] T. T. Ta, Y.-K. Shieh, and C. L. Lu, "Computing a longest common almost-increasing subsequence of two sequences," Theoretical Computer Science, Vol. 854, pp. 44-51, 2021.
[16] P. van Emde Boas, R. Kaas, and E. Zijlstra, "Design and implementation of an efficient priority queue," Mathematical Systems Theory, Vol. 10, No. 1, pp. 99-127, 1976.
[17] I.-H. Yang, C.-P. Huang, and K.-M. Chao, "A fast algorithm for computing a longest common increasing subsequence," Information Processing Letters, Vol. 93, No. 5, pp. 249-253, 2005.