Zur Startseite der Abteilung Theoretische Informatik

Algorithmische Gruppentheorie (WS 2016/17)

Organisatorisches

Dozent: Volker Diekert

ÜbungenLukas Fleischer

Zeit Raum Termine
Di 14:00-15:30 0.124 wöchentlich
Do 11:30-13:00 0.124 wöchentlich

Inhalt

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

  1. Wortproblem: Ist ein gegebenes Gruppenelement (als Wort in Erzeugern) das Einselement in der Gruppe?
  2. Konjugationsproblem: Sind zwei Elemente 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.

Folien und Skript zur Vorlesung

Übungsblätter

  • Blatt 1 (Besprechung am 10.11.2016)
  • Blatt 2 (Besprechung am 15.11.2016)
  • Blatt 3 (Besprechung am 06.12.2016 und am 08.12.2016)
  • Blatt 4 (Besprechung am 10.01.2017, Stand: 10.01.2016)

Literatur

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