臺灣博碩士論文加值系統

在這篇論文中，我們完成了一個利用假設檢定來判斷雙母體之間是否存在顯著差異的演算法效能評估系統。給定一個要測試的集合與兩個要比較的演算法，我們可以藉由抽樣的方式來推論兩個母體的平均執行時間。主要的理論基礎是利用常態分佈的特性並採用z檢定來測試兩個演算法之間的差異。如果我們可以容忍系統執行完畢後所計算出來的錯誤機率，那麼我們就不需要去對集合中的每一個例子都進行測試。我們同時測試了三個處理二維凸多邊形問題的演算法，利用這個演算法效能評估系統得到了一些實驗結果。

In this thesis, we have completed a benchmark system with hypothesis test of two populations. Giving an instance set as the population and two algorithms, we can infer the average executing-time on computers of two algorithms by sampling. The test method used is the z test in statistics and the main analysis is based on the normal distribution. We need not to test each instance in the set if we can tolerate the risk calculated from this benchmark system. We consider three algorithms for computing the 2D convex hull for a set of points in the plane as case study and have obtained some experimental results using the OpenCPS benchmark system.

口試委員會審定書……………………………………………………………… i
誌謝……………………………………………………………………………… ii
中文摘要………………………………………………………………………… iii
英文摘要………………………………………………………………………… iv
Chapter 1. Introduction………………………………………………………….... 1

Chapter 2. Hypothesis Test……………………………………………………… 7
2.1 Introduction……………………………………………………………… 7
2.2 Sampling Methods……………………………………………………… 8
2.3 Normal Probability Distribution………………………………………… 9
2.4 Linear Combination of Random Variables and Sampling Distributions of Means…………………………………………………………………… 14
2.5 Steps of a Hypothesis Test……………………………………………… 16
2.6 Implement on a Benchmark System……………………………………… 23

Chapter 3. Environment of Benchmark System………………………………… 25
3.1 OpenCPS Benchmark Architecture……………………………………… 25
3.2 Design of the Benchmark System with Hypothesis Test………………… 26
3.3 The Workflow of Executing a Benchmark Task………………………… 27

Chapter 4. Case Study…………………………………………………………… 31
4.1 Introduction………………………………………………………………. 31
4.2 Definition of Convex Hull Problem……………………………………… 31
4.3 Algorithms to Solve Convex Hull Problem……………………………… 32
4.4 Description of Experiment……………………………………………… 37
4.5 Experimental Results…………………………………………………… 41
4.6 Summary………………………………………………………………… 49

Chapter 5. Conclusion…………………………………………………………… 52

References………………………………………………………………………… 53

Appendix A……………………………………………………………………… 54
Appendix B……………………………………………………………………… 55
Appendix C……………………………………………………………………… 57

References
[1]M. Y. Chen, Jyh-Da Wei, J. H. Huang and D. T. Lee, “Design and Applications of an Algorithm Benchmark System in a Computational Problem Solving Environment”, in Proc. 11th Annual Conference on Innovation and Technology in Computer Science Education, Bologna, Italy, pp. 123-127, 2006.
[2]宋俊昇,“演算法效能評估系統之設計”,臺灣大學資訊工程研究所碩士論文, 2003.
[3]Laura Vyšniauskaitė ,Vydūnas Šaltenis, “A PRIORI FILTRATION OF POINTS FOR FINDING CONVEX HULL”, ÛKIO TECHNOLOGINIS IR EKONOMINIS VYSTYMAS TECHNOLOGICAL AND ECONOMIC DEVELOPMENT OF ECONOMY, pp. 341-346, 2006.
[4]Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest,“Introduction to algorithms”, 2ed, McGraw-Hill, 2001.
[5]Udi Manber,“Introduction to algorithms :a creative approach”, Addison-Wesley, 1989.
[6]Vijay V. Vazirani,“Approximation Algorithms”, Springer-Verlag Berlin Heidelber, 2001.
[7]Clifford A. Shaffer , “A practical introduction to data structures and algorithm analysis”, Prentice Hall International, 1997.
[8]Rober D. Mason, Douglas A. Lind, William G. Marchal, “STATICAL TECHNIQUES IN BUSINESS AND ECONOMICS”, 10ed, McGraw-Hill, 1999.
[9]Mark L. Berenson, David M. Levine, Timothy C. Krehbiel, “Basic Business Statistics: concepts and applications”, 8ed, Prentice Hall, 2002.
[10]Douglas C. Montgomery, Georege C. Runger, “Applied Statistics and Probability for Engineers”, John Wiley & Sons, 1994.
[11]John A. Rice, “Mathematical Statistics and Data Analysis”, Wadsworth & Books/Cole Advanced Books & Software Pacific Grove, 1988.
[12]Saeed Ghahramani,“Fundamentals of probability with stochastic processes”, Pearson/Prentice Hall, 2005.
[13]Opencps web: http://www.opencps.org