Zur Startseite der Abteilung Theoretische Informatik

Algorithmische Gruppentheorie (WS 2016/17)

Besondere Ankündigungen

Am Montag, den 15. Dezember 2014 besuchen wir den Weihnachtsmarkt dazu sind alle Studenten herzlich eingeladen. Treffpunkt ist um 17:30 Uhr vor dem Nordeingang des Informatik-Gebäudes oder gegen 18:00 Uhr direkt am Marktplatz (Ecke Schulstraße).

Organisatorisches

Dozent: Volker Diekert

ZeitRaumTermine
Di 14:00-15:30 0.124 wöchentlich ab 14.10.2014
Mo 9:45-11:15 0.124 wöchentlich ab 27.10.2014

Der Termin vom Donnerstag wurde auf Montag 9:45 verlegt! Am 27.10. findet die Vorlesung am Montag statt.

Inhalt

Bereits 1911 formulierte Max Dehn drei fundamentale algorithmische Probleme in der (kombinatorischen) Gruppentheorie:

  1. Wortproblem: Ist ein gegebenes Gruppenelement g (als Wort in Erzeugern) das Einselement in der Gruppe G?
  2. Konjugationsproblem: Sind zwei Elemente g und h konjugiert?
  3. Isomorphieproblem: Definieren zwei gegebene Darstellungen isomorphe Gruppen?

Im Allgemeinen sind alle diese Fragen unentscheidbar, also kann man positive Antworten nur in Spezialfällen erhalten. Die weitreichensten Ergebnisse liegen für das Wortproblem vor. Hier gibt es eine große Klasse von Gruppen, die in der Praxis auftreten und für die man sehr gute Algorithmen kennt. In der Vorlesung sollen Techniken behandelt werden, die zu positiven Lösungen zu den obigen Fragen führen und für welche Klasse von Gruppen diese anwendbar sind. Eine prominente Rolle spielen hierbei konfluente Wortersetzungssysteme, die auch in anderen Bereichen zum Einsatz kommen. Insgesamt lebt die Theorie von Querbezügen zu vielen anderen Bereichen, wie Kombinatorik, Topologie, Geometrie, theoretischer Informatik. Dieses Zusammenspiel verschiedener Methoden macht die algorithmische Gruppentheorie sehr attraktiv.

Materialen

Aktuelle Folien (PDF) (werden laufend aktualisiert)

Folien aus dem WS 2008/09 (PDF)

Die Folien zum Vortrag vom 10.11.14 befinden sich hier

Übungsblätter

Die finale Version von Blatt 2 gibt es ohne Hinweise (sehr schwer) und mit Hinweisen (normale Schwierigkeit).

Blatt3: PDF

Literatur

  • Volker Diekert, Manfred Kufleitner, Gerhard Rosenberger: Diskrete algebraische Methoden, Walter de Gruyter, 2013.
  • Lyndon, Schupp: Combinatorial Group Theory, Springer, 1977.