Algorithmen für Gruppen und Codes

(Prof. Dr. Thomas Beth, Dr. Markus Grassl)

4. Vorlesung: Schreier-Sims-Algorithmus

Bestimmung einer Basis B und einer starken Erzeugermenge (base and strong generating set, BSGS) zu einer Permutationsgruppe, die durch eine Menge S von Erzeugern gegeben ist.
Grundidee:
- Teste, ob die Schreiergeneratoren schon in der entsprechenden Untergruppe enhalten sind; falls nicht, füge diese hinzu.
- Berechne die Bahnen und Transversalen zum Basispunkt &beta_j bzgl. des Stabilisators der vorherigen Basispunkte
- Füge ggf. neue Basispunkte hinzu.

Literatur:

Sims, Charles C.
"Computation with permutation groups".
In: Proceedings of the second ACM symposium on Symbolic and algebraic manipulation.
Los Angeles, CA, 1971. pp. 23-28.
ACM online
Notizen zum Algorithmus

zurück zur Hauptseite