臺灣博碩士論文加值系統

本篇論文針對兩個線上問題，研究其演算法的設計與分析，並以競爭式分析來衡量演算法的效能。
第一個主題是線上字典問題，我設計一種樹狀資料結構實作線上字典，並設計動態更新的演算法。以競爭式分析的觀點來衡量這種實作線上字典與動態更新演算法，發現效能近似最佳化。就最壞狀況分析、平均狀況分析和競爭式分析等方法，與其他線上字典比較，我設計的二項式樹字典都有明顯的效能改進。
第二個主題是線上磁碟排程問題，有三種磁碟排程演算法是最常被使用的，分別是先到先做、最近先做與來回掃描。以競爭式分析的觀點來比較這三種磁碟排程演算法，發現在高承載的磁碟系統中，來回掃描演算法會在效能上勝過先到先做與最近先做兩種磁碟排程演算法，這與其他實作、模擬和理論分析等相關結果相符合。

In this thesis, we study two on-line problems. The first one is the on-line dictionary problem. An implementation of dynamic dictionaries based on binomial trees is provided. The move-to-front heuristic is proven to
be 3-competitive for the tree update problem on our
implementation. We also prove that the lower bound for on-line algorithms on this implementation is (2k+2)/(k+2), where k is the order of the tree. By the comparison of dictionaries on the list, the splay tree, and the our model, a dictionary based on the
binomial tree should be much more efficient than one based on the linear list. In addition, the correspondence between the binary-digit represented keys and the structure of binomial trees perfectly supports highly convenient and efficient searching operations. These facts strongly suggest our adoption of binomial
tree as the dictionary structure.
In the second topic of the thesis, the on-line disk scheduling problem is discussed. We consider the following three on-line disk scheduling algorithms: FCFS, SSTF, and LOOK. We prove that the lower bounds of the competitive ratios of FCFS, SSTF, and LOOK. We also give a competitive ratio of LOOK that matches its lower bound. As our results show, the performance of LOOK, in competitive sense, is better than those of FCFS and SSTF.

Abstract
Chapter 1: Introduction
Chapter 2: Related Works
Chapter 3: Competitive Analysis of Dynamic Dictionary on Binomial Trees
Chapter 4: Competitive Analysis of On-Line Disk Scheduling
Chapter 5: Conclusions and Future Works
Reference

[1] F. d''more, A. Marchetii-Spaccamela, and U. Nanni, "The weighted list update problem and the lazy adversary," Theoretical Computer Science, 108, pp 371-384, 1993.
[2] S. Irani, "Two results on the list update problem," Technical reports, U. C. Berkerly, 1990.
[3] D. Sleator and R. Tarjan, "Amortized efficiency of the list update and paging rules," Communication of ACM, 28(20), pp 652-686, 1985.
[4] T. Chen, W. Yang, and R. Lee, "Amortized analysis of some disk scheduling algorithms: SSTF, SCAN, and n-step SCAN," BIT, 32, pp 546-558, 1992.