以作者查詢圖書館館藏 、以作者查詢臺灣博碩士 、以作者查詢全國書目 、勘誤回報 、線上人數:22 、訪客IP:3.235.251.99
姓名 蔡家豪(Jia-Hao Cai) 查詢紙本館藏 畢業系所 資訊工程學系 論文名稱 教學用靜態時間複雜度分析工具
(A Static Time Complexity Analysis Tool for Education)相關論文 檔案 [Endnote RIS 格式] [Bibtex 格式] [相關文章] [文章引用] [完整記錄] [館藏目錄] 至系統瀏覽論文 (2031-8-1以後開放) 摘要(中) 程式碼的好壞可以從很多面向來分析。學習者可以從這些評分指標中,學習如何撰寫更好的程式碼。評分者也能藉由評分工具來對程式碼進行程式功能正確與否以外的評價。其中,時間複雜度是評價程式碼好壞與否的重要指標。但分析程式碼的時間複雜度並不是簡單的事。
本研究實作一個基於抽象語法樹分析的程式碼時間複雜度靜態分析工具--RecTCC。現有的基於抽象語法樹分析的工具,因為能獲得的資訊不足,對於遞迴函式的支援性不佳。RecTCC利用Value Numbering的概念及符號表來追蹤函式參數,找出參數與引數之間的值的變化,並以此來當作遞迴呼叫的工作量變化。Big-O AST會在AST上記錄各節點的時間複雜度,走訪Big-O AST並計算循序、選擇、重覆結構的時間複雜度,可找出非遞迴呼叫部份的部份時間複雜度。由以上步驟可以得到遞迴關係式,再搭配Master Theorem來分析遞迴函式的時間複雜度。
本研究將Introduction of Algorithms一書中的演算法分成三類:Loop、If-Else、Recursion,並從各類中挑選演算法來實作並進行評估。與其他工具相比,只有RecTCC對這三類演算法皆有支援。摘要(英) There are several aspects to judge the quality of a source code. Students can learn how to write a better code from these evaluation features. Teachers can evaluate the source code besides the correctness of programs. In these evaluation features, the time complexity is an important feature. However, finding the time complexity of a source code is difficult.
In this paper, we implement a static time complexity analysis tool based on AST analysis, called RecTCC. Because of the lack of some information, present analysis tools based on AST analysis are not compatible with recursive functions. RecTCC uses the concept of Value Numbering and symbol tables to chase the function parameters. We take the variations between parameters and arguments as the workload variation of the recursive calls. RecTCC uses Big-O AST to find the time complexities comprised of the non-recursive call parts. Finally, RecTCC can find the time complexities of recursive functions by recurrence relations and the master theorem.
In this paper, we separate algorithms in "Introduction of Algorithms" into three categories: Loop, If-Else, Recursion. We implement some algorithms from these categories, and use them to test analysis tools. RecTCC is the only tool compatible with all algorithms in these three categories.關鍵字(中) ★ 時間複雜度
★ 遞迴函式
★ 靜態程式分析
★ 抽象語法樹分析關鍵字(英) ★ Time complexity
★ Recursive function
★ Static program analysis
★ Abstract syntax tree analysis論文目次 摘要 v
Abstract vi
Contents vii
List of Figures x
List of Tables xi
1 Introduction 1
1.1 Source code evaluation tool...........................................1
1.2 Source code evaluation features......................................1
1.3 Dynamic analysis and static analysis...............................2
1.3.1 Dynamic analysis...............................................3
1.3.2 Static analysis...................................................3
1.4 Learning recursive algorithm.........................................4
1.5 Method of time complexity analysis................................4
1.5.1 Dynamic analysis...............................................5
1.5.2 Intermediate representation and machine code analysis.............5
1.5.3 Control flow graph analysis..................................6
1.5.4 Abstract syntax tree analysis................................6
1.5.5 Machine learning...............................................7
1.6 Our work..................................................................8
2 Motivation 9
2.1 Recursive function example...........................................9
2.2 Difficulty of time complexity analysis tool........................12
2.3 Existing time complexity analysis tools............................12
2.3.1 Python-bigO-calculator.......................................13
2.3.2 DYSTA and Big-O calculator...............................13
2.3.3 Compigorithm...................................................14
2.3.4 Multiclass classification with gradient boosted trees...15
3 RecTCC163.1System structure........................................................16
3.1.1 Parser.............................................................17
3.1.2 Big-O AST Transformer......................................20
3.1.3 Symbol table manager........................................21
3.1.4 Time complexity calculator..................................21
3.2 Recursive function analysis...........................................22
3.2.1 Master theorem.................................................22
3.2.2 Find the workload variation by value numbering.......22
3.2.3 Find the partial time complexity...........................23
3.2.4 Handling scope problem by symbol table manager.....24
3.2.5 Proposal Discussion............................................27
4 Implementation31
4.1 Symbol table manager.................................................31
4.1.1 Enter new scope................................................32
4.1.2 Leave current scope............................................33
4.1.3 Combine If and Else scopes information..................33
4.1.4 Update scope information....................................34
4.1.5 Add information into VN_table............................34
4.2 VN_table.................................................................35
4.2.1 Demonstration..................................................35
5 Result 39
5.1 Evaluation methods.....................................................39
5.1.1 Correctness......................................................39
5.1.2 Functionality....................................................39
5.2 Evaluation result........................................................41
6 Related Work 43
6.1 Time Complexity Analysis of the Genetic Algorithm Clustering Method......43
6.2 O-Charts: Towards an Effective Toolkit for Teaching Time Complexity......44
6.3 A novel method to find time complexity of an algorithm by using control flow graph.......44
7 Conclusion 45
Bibliography 46參考文獻 [1]C. Duncan, T. Bell, and S. Tanimoto, “Should your 8-year-old learn coding?”WiPSCE ’14: Proceedings of the 9th Workshop in Primary and Secondary Computing Education, pp. 60–69, 2014.doi:http://dx.doi.org/10.1145/2670757.2670774.
[2]D. Knuth,The art of Computer Programming, Volume 3, 2nd edition. CA: Addison-Wesley Professional, 1998.
[3]B. Holland, G. R. Santhanam, P. Awadhutkar, and S. Kothari, “Statically-informed dynamic analysis tools to detect algorithmic complexity vulnerabilities,”2016 IEEE 16th International Working Conference on Source Code Analysis and Manipulation(SCAM), 2016.doi:https://doi.org/10.1109/SCAM.2016.23.
[4]A. Khan, S. Abbas, and M. Saleem, “Analysis of space time complexity with pso based synchronous mc-cdma system,”2019 2nd International Conference on Computing, Mathematics and Engineering Technologies (iCoMET), 2019.doi:https://doi.org/10.1109/ICOMET.2019.8673401.
[5]LLVM-Developer-Group. (). “Llvm,” [Online]. Available:https://llvm.org/(visited on 06/01/2021).
[6]T. Wei, J. Mao, W. Zou, and Y. Chen, “A new algorithm for identifying loops in decompilation vulnerabilities,”SAS’07: Proceedings of the 14th international conference on Static Analysis, pp. 170–183, 2007.
[7]T. Deering, S. Kothari, J. Sauceda, and J. Mathews, “Atlas:a new way to explore software, build analysis tools,”ICSE Companion 2014: Companion Proceedings of the 36th International Conference on Software Engineering, 2014.doi:http://dx.doi.org/10.1145/2591062.2591065.
[8]Alfex4936. (). “Python-bigo-calculator,” [Online]. Available:https://github.com/Alfex4936/python-bigO-calculator(visited on 06/01/2021).
[9]C. Pan and Y. Zhuang, “The design and implementation of automated time complexity analysis: To evaluate the power consumption of embedded system at software level,” M.S. thesis, CSIE. Dept., NCU, Taiyan, 2020.
[10]D. He and Y. Zhuang, “Static analysis of time complexity with big-o ast: A case study of algorithmic competitive programming problems,” M.S. thesis, CSIE. Dept., NCU, Taiyan, 2019.
[11]R. Smith and S. Rixner, “Compigorithm: An interactive tool for guided practice of complexity analysis,”ITiCSE ’20: Proceedings of the 2020 ACM Conference on Innovation and Technology in Computer Science Education, pp. 363–369, 2020.doi:https://doi.org/10.1145/3341525.3387390.
[12]D. K. Sharma, S. Vohra, T. Gupta, and V. Goyal, “Predicting the algorithmic time complexity of single parametric algorithms using multiclass classification with gradient boosted trees,”Proceedings of 2018 Eleventh International Conference on Contemporary Computing (IC3), 2018.doi:https://doi.org/10.1109/IC3.2018.8530473.
[13]O. J. Dahl, E. W. Dijkstra, and C. A. R. Hoare,Structured programming. United Kingdom: Academic Press Ltd., 1972.
[14]T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein,Introduction to algorithms, 3rd edition. United States: MIT Press, 2009.
[15]Z. M. NOPIAH, M. I. KHAIRIR, S. ABDULLAH, M. N. BAHARIN, and A. ARIFIN, “Time complexity analysis of the genetic algorithm clustering method,”ISPRA’10: Proceedings of the 9th WSEAS international conference on Signal processing, robotics and automation, pp. 171–176, 2010.
[16]S. Barlowe and A. Scott, “O-charts: Towards an effective toolkit for teaching time complexity,”2015 IEEE Frontiers in Education Conference (FIE), pp. 1–4, 2015. doi:http://dx.doi.org/10.1109/FIE.2015.7344295.
[17]K. S. Kumar and D.Malathi, “A novel method to find time complexity of an algorithm by using control flow graph,”2017 International Conference on Technical Advancements in Computers and Communications (ICTACC), pp. 1–4, 2017.doi:https://doi.org/10.1109/ICTACC.2017.26.指導教授 莊永裕(Yung-Yu Zhuang) 審核日期 2021-7-20 推文 facebook plurk twitter funp google live udn HD myshare reddit netvibes friend youpush delicious baidu 網路書籤 Google bookmarks del.icio.us hemidemi myshare