Abstract
目前大多數的管線式超級電腦(pipelined Supercomprters)均被利用於解決數值計算上的問題，身為計算機科學的研究者，我們嘗試利用這一類管線式超級電腦來解一些被稱之為NP-hard 的問題。在以往的研究領域中，并沒有找到徹底而有效的策略能夠解決所愛類的問題。而在此時, 具有暴力意味的列舉式演算法(Enumeration Algorithm) 往往成為最直接而有效的做法。本篇論文作者嘗試以向量式演算法的角度，來探討管線式超級電腦上列舉行為的效率。針對(NP_hard問題，主要有兩類列舉演算法；第一類是組合物件(combination Objects) 的列舉。對此我們提出一個向量式演算法(Vector algorithm)，根據逆定序(Unranking) 的觀念，來產生所( ) 個組合物件，而其時間復雜度是O(n ) 向量運算(Vector Operations) 。然後由此向量式演算法衍生出兩個變形,是針對向量長度及字組長度的增長,提供一些取巧的做法以增強效率,使時間復雜度降至O(n)向量運算。第二類則是排列物件(Permutation Objcts)列舉。同樣地，由逆定序的觀念，我們提出一個O(nm) 的向量式演算法來產生所有Ｐ 個排列物件。由我們研究的結果發現，秉持逆定序的觀念，似乎很難得到一個最佳的向量式演算法。於是我們提出一個新的觀念，稱之為向量蒐值法(Vector Gathering)。採用此法所得之時間復雜度是O(m)向量運算，由此可宣稱已得到了一個最佳的(Optimal) 向量式演算法，來產生所有P 個排列物件。對此做法，有實驗數據來證明它的實用性。在論文中，也對未來利用管線式超級電腦來處理非數值方面的問題，做了一些建議及預測。對未來這方面的研究，應該有導此的作用。