施賴埃爾一西姆斯算法(the Schreier-Sims algo-rithm)一種群論算法.置換群計算的基本方法.由西姆斯( Sims , C. C.)於20世紀60年代末提出.對於由一組生成置換給出的n次置換群G，該算法根據施賴埃爾(Schreier , O.)關於子群生成元的定理求出G的一個基以及相應的強生成集，同時給出了G中元素的一個結構.利用這個結構可以方便地求出G的階、計算G及其某些點穩定子群的軌道、判斷一個置換是否屬於G等.在最壞情形下，該算法的計算複雜度為O(ns).利昂(Leon,J. S.)於1980年把陪集計數引人算法，使之在處理n較大的群時效率得以提高.這一算法常被稱為施賴埃爾一托德-考克斯特一西姆斯算法.此後，杰倫(Jerrum, M.)提出G的既約表示的概念，進而設計了一個求G的基和強生成集的新算法，使其計算複雜度降至O(n5).
基本介紹
- 中文名：施賴埃爾一西姆斯算法
- 外文名：the Schreier-Sims algo-rithm
