Vorlesung im Wintersemester 2004/05

Algorithmen für Gruppen und Codes

(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, 20. Oktober 2004

Vorlesungsübersicht

Literaturhinweise

Vorlesungsmitschrieb von Wolfgang Globke.
Vielen Dank!

• Berlekamp, E.; McEliece, R.; van Tilborg, H.
  "On the inherent intractability of certain coding problems".
  IEEE Transactions on Information Theory, Vol. 24, No .3, May 1978, pp. 384-386.
  IEEE Xplore
• Bitner, J. R.; Ehrlich, G; and Reingold, E. M..
  "Efficient Generation of the Binary Reflected Gray Code and Its Applications".
  Communications of the ACM, vol. 19, no. 9, pp. 517-521, September 1976.
  ACM Online
• 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".
• Chase, P. J.
  "Algorithm 382: Combinations of M out of N Objects".
  Communications of the ACM, vol. 13, no. 6, p. 368 & p.  376, June 1970.
  ACM Online
• 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
• Knuth, D. E.
  The Art of Programming, Vol. 4.
  Pre-Fascicle 2a: Generating all n-tuples.
  http://www-cs-faculty.stanford.edu/~knuth/news.html
• Knuth, D. E.
  The Art of Programming, Vol. 4.
  Pre-Fascicle 3a: Generating all combinations.
  http://www-cs-faculty.stanford.edu/~knuth/news.html
• Murray, Scott H..
  "The Schreier-Sims algorithm".
  B.Sc. Thesis,
  Australian National University, Canberra, Australia, 1993.
• 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
• Vardy, A.
  "The intractability of computing the minimum distance of a code".
  IEEE Transactions on Information Theory, Vol. 43, No .6, Nov. 1997, pp. 1757-1766.
  IEEE Xplore

• 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