置换群的计算机算法

Algorithms for Permutation Groups

从电子计算机一诞生起人们就注意到,它不仅能进行具体的数值运算,还具备记忆、判断等功能,因而有可能被用来进行抽象的符号运算。随着计算机技术(包括硬件设备和软件系统)的发展,上述设想变成了现实。1960年首先出现了Neubuser借助计算机研究子群格的工作。尔后,计算机越来越多地被用于研究各种各样的代数结构,产生了众多的算法,以至形成了所谓的“计算代数(ComPutational Algebra)”。事实上。

Over the past two decades computational group theory has been developed rapidly Alarge number of powerful algorithms have been designed and implemented, and have already played an important role in research works. On the other hand, after the accomplishment of the classification of finite simple groups, advances are also made in the theoretic aspect of computational group theory itself.In this paper we give a brief survey,in both applied and theoretic aspects, about the algorithms for permutation groups. The paper consists of five sections. 1. onset enumeration, 2. base and strong generating set,3. certain algorithms for permutation groups, 4. random methods, 5. computational complexity.