Vorlesung im Wintersemester 2003/04

Algorithmen für Gruppen und Codes

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

8. Vorlesung: Kurze Faktorisierungen

• Vorberechnung
  • Paar: Gruppenelement und Faktorisierung
  • kurze Paare: Gruppenelemente mit kurzer Faktorisierung
  • "faule" Paare (lazy pairs): Gruppenelemente mit vielen Fixpunkten
  • konjugierte Paare: konjugiere kurze (faule) Paare mit kurzen Paaren
• heuristische Basiswahl
  schrittweise Verfeinerung eier Partition von {1,...,n}:
  • suche ein Element, das viele Fixpunkte im ersten Block der Partition hat
  • zerlege die erste Partition in Fixpunkte und bewegte Punkte
• Vervollständigung der Transversalen
  • Vervollständigung des Orbitgraphs:
    verwende alle bekannten (kurzen) Elemente (auch aus unteren Stufen), um die Bahn eines Elementes zu berechnen
  • suche kurze Wege im Orbitgraph
  • "Quotienten": verschiedene Wege im Orbitgraph zu einem Punkt liefern Elemente des Stabilisators
  • (kurze) zufällige Worte
  • Scheiergeneratoren

• Egner, Sebastian and Püschel, Markus.
  "Solving puzzles related to permutation groups".
  Proceedings of the 1998 International Symposium on Symbolic and Algebraic Computation (ISSAC 98).
  Rostock, 1998. pp. 186-193.
  ACM online