Vorlesung im Wintersemester 2014/15

Algorithmen für Gruppen und Codes

(Dr. Markus Grassl, Prof. Dr. Andreas Knauf)

Vorlesung mit Übung, 2,5 SWS, ECTS-Studium, ECTS-Credits: 5
Zeit: mittwochs 10:00-12:00 Uhr
Ort: Übung 2 / 01.251-128

Die Vorlesung behandelt verschiedene algorithmische Fragestellungen der Gruppen- und Codierungstheorie. Im ersten Teil der Vorlesung geht es beispielsweise um die Bestimmung der Ordnung von Gruppen, dem Test, ob ein Element in einer Gruppe enthalten ist, und die Darstellung von Elementen in den Erzeugern.

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

Fragestellungen

• Größe einer Gruppe:
  Gegeben eine (endliche) Gruppe G und eine Teilmenge S⊆G, wieviele Elemente hat die von S erzeugte Untergruppe H≤G?
• Gegeben ein Element g∈G, liegt g in der Untergruppe H≤G?
• Wie zählt man alle Gruppenelemente auf?
• Wie zieht man gleichverteilt ein zufälliges Gruppenelement?
• Wie wertet man einen Gruppenhomomorphismus aus, der auf den Erzeugern der Gruppe definiert ist?
• Wie berechnet man den Schnitt von (Unter-)Gruppen?
• Wie bestimmt man die Fehlerkorrektureigenschaften eines linearen Blockcodes?
• Wie korrigiert man Fehler mit Hilfe eines linearen Blockcodes?