Vorlesung im Wintersemester 2003/04

Algorithmen für Gruppen und Codes

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

Viele strukturierte Probleme können mit Hilfe von Methoden aus der Gruppentheorie beschrieben werden. Ein prominentes Beispiel ist Rubik's Cube. Die Vorlesung behandelt verschiedene algorithmische Fragestellungen der Gruppen- und Darstellungstheorie, beispielsweise die Bestimmung der Ordnung von Gruppen, Wortprobleme in Gruppen, Berechnung von Charaktertafeln und Darstellungen.

Ein zweiter Schwerpunkt der Vorlesung stellen algorithmische Fragen im Bereich der Codierungstheorie dar, z. B. Algorithmen zur Berechnung der Minimaldistanz.

Die prüfbare Vorlesung wendet sich an Studierende im Hauptstudium der Fachrichtungen Informatik und Mathematik sowie Physik und Elektrotechnik. Kenntnisse aus der Vorlesung Computeralgebra und Signale, Codes und Chiffren I sowie im Bereich der Gruppentheorie sind hilfreich, aber nicht Voraussetzung. Die erforderlichen Grundlagen werden in der Vorlesung vermittelt.

Es besteht die Möglichkeit, die Algorithmen der Vorlesung im Computeralgebrasystem MAGMA zu implementieren.

Termin: mittwochs, 945-1115 Uhr Seminarraum 236, Neubau Informatik erstmals: Mittwoch, 15. Oktober 2003

Vorlesungsübersicht

Gruppen

• 1. Vorlesung (15.10.03)
  Gruppen und Gruppenoperationen

• 2. Vorlesung (22.10.03)
  Bahnen und Transversalen

• 3. Vorlesung (29.10.03)
  Basis und starke Erzeuger (BSGS)

• 4. Vorlesung (05.11.03)
  Schreier-Sims-Algorithmus

• 5. Vorlesung (12.11.03)
  Anwendungen von BSGS

• 6. Vorlesung (19.11.03)
  Basiswechsel

• 7. Vorlesung (26.11.03)
  Schnitt von Gruppen, Faktorisierung mit Freiheitsgraden

• 8. Vorlesung (03.12.03)
  kurze Faktorisierungen

• 9. Vorlesung (10.12.03, Dr. R. Steinwandt)
  Kryptosysteme und Gruppenfaktorisierungen

• 10. Vorlesung (17.12.03)
  • kürzere Faktorisierungen (inverses Element, Multiplikation mit kurzem Wort)
  • endliche Körper
  • Basiswahl bei Matrixgruppen

Codes

• 11. Vorlesung (07.01.04)
  fehlerkorrigierende Codes

• 12. Vorlesung (21.01.04, Jens Bohli))
  Das McEliece-Kryptosystem

• 13. Vorlesung (28.01.04)
  Berechnung des Minimalgewichts

• 14. Vorlesung (04.02.04)
  zyklische Codes, Kongruenzen für die Gewichte

• 15. Vorlesung (10.02.04)
  Gewichtsverteilung von Codes

• 16. Vorlesung (11.02.04)
  Punktieren und Verkürzen von Codes

Literaturhinweise

• Bosma, Wieb and Cannon, John.
  "Structural computation in finite permutation groups".
  CWI-Quarterly, vol. 5, pp. 127-160, 1992.
  Preprint: "An Introduction to Permutation Group Algorithms".
• 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
• Grassl, Markus.
  "Searching for Good Linear Codes".
  Preprint, 2003.
  PostScript
• Grassl, Markus and White, Gerg.
  "New Good Linear Codes by Special Puncturings".
  IEEE International Symposium on Information Theory 2004.
  PostScript
• Murray, Scott H. and O'Brian, E. :A..
  "Selecting Base Points for the Schreier-Sims Algorithms for Matrix Groups".
  Journal of Symbolic Computation, vol. 19, pp. 577-584, 1995.
  PDF-File.
• 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

• Gruppentheoretische Algorithmen
  Peter Köhler, Universität Gießen, WS 2000/2001.

• Butler, Gregory.
  Fundamental algorithms for permutation groups.
  Lecture Notes in Computer Science, vol. 559.
  Berlin: Springer, 1991.
  UB: 91A5086, Info-Bib: D.But(14131)
• MacWilliams, F. J. and Sloane, N. J. A.
  The Theory of Error-Correcting Codes.
  Amsterdam: North-Holland, 1977.
• Seress, Ákos.
  Permutation group algorithms.
  Cambridge : Cambridge University Press, 2003.
  Leider nur am IAKS vorhanden.

• MAGMA, Computational Algebra Group, School of Mathematics and Statistics, University of Sydney.
  on-line help
  Lizenz
• GAP - Groups, Algorithms and Programming
  kostenlos

Markus Grassl Neubau Informatik, Zimmer 272 E-Mail: grassl@ira.uka.de Telefon: 0721/608-6299