臺灣博碩士論文加值系統

在本研究中，我們將提出一些平行演算法以產生下列之組成個體：排列、
子集合和集合分割，我們提出之平行演算法有下列之優點：首先，他們是
有效率的和擁有較低之計算花費，其次，他們能在簡單規律的陣列上被執
行，因此特別適合在超大型積體電路上製作，另外，我們所提出之平行演
算法能以某些特別之次序來產生組成個體，例如﹕字母順序排列或最小變
化排列。當我們與其他研究者之相關設計做比較，這些優點即被突顯出來
。

In this research, we shall propose several parallel algorithms
for the generation of the following combinatorial objects:
permutations, subsets, and set partitions. The proposed
parallel algorithms have the following advantages. First, they
are time efficient and have low computation cost. Second, they
can be executed on simple regular array processors, and hence
are amenable to VLSI implementation. Third, they generate
combinatorial objects in some desired order, such as
lexicographic order or minimum change order. These advantages
can be seen from the evaluation of the proposed designs and the
comparisons of them with existing ones.

Contents
圖目錄
表目錄
摘要
英文摘要
1. Introduction
1.1 Generation of Combinatorial Objects
1.2 An Overview of Previous Researches
1.3 Research Motivation
1.4 Design Approach
1.5 Dissertation Organization
2. Generation of Permutations in Minimum Change Order
2.1 Parallel Algorithm Design
2.2 Discussion
3. Generation of Permutations in Lexicographic Order
3.1 Design 1:A Triangular Systolic Array
3.2 Design 2:A Linear Systolic Array
3.3 Design 3:A Linear Systolic Array with Minimum Pipelining Period
3.4 Design 4:A Linear Systolic Array with Shared Memory
3.5 Discussion
4. Generation of Subsets
4.1 Design 1:A Word-Level Design
4.2 Design 2:A Bit-Level Design
4.3 Discussion
5. Generation of Set Partitions
5.1 Parallel Algorithm Design
5.2 Discussion
6. Conclusions and Suggestions for Future Researches
6.1 Dissertzation Summary
Reference