Vorlesung im Wintersemester 2006/07

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, 08. November 2006

• Unterlagen zur Vorlesung aus dem Wintersemester 2004/05
• Vorlesungsmitschrieb von Wolfgang Globke.
  lokale Kopie (Stand: 09.08.2006)

• 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
• Murray, Scott H..
  "The Schreier-Sims algorithm".
  B.Sc. Thesis,
  Australian National University, Canberra, Australia, 1993.
• 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

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