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

Zeit Raum Termine
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.

News

[June 19] The paper “The power word problem” by Markus Lohrey and Armin Weiß has been accepted at MFCS 2019.

[May 19] The paper “On the Average Case of MergeInsertion” by Florian Stober and Armin Weiß has been accepted at IWOCA 2019.

[Oct’18] The paper “Worst-Case Efficient Sorting with QuickMergesort” by Stefan Edelkamp and Armin Weiß has been accepted at ALENEX 2019.

[Jun’18] At CCC 2018, Lukas Fleischer received a Best Student Paper Award for his submission “On the Complexity of the Cayley Semigroup Membership Problem”.

[Jun’18] The paper “Testing Simon’s congruence” by Lukas Fleischer and Manfred Kufleitner was accepted at MFCS 2018.

[Jun’18] The paper “The Intersection Problem for Finite Semigroups” by Lukas Fleischer was accepted at DLT 2018.

[Apr’18] The paper “The isomorphism problem for finite extensions of free groups is in PSPACE” by Géraud Sénizergues and Armin Weiß was accepted at ICALP 2018.

[Apr’18] The paper “On the Complexity of the Cayley Semigroup Membership Problem” by Lukas Fleischer was accepted at CCC 2018.

[Jan’18] On March 24-29, 2019 Volker Diekert, Markus Lohrey, Olga Kharlampovich and Alexei Miasnikov will organize the Schloss Dagstuhl Seminar “Algorithmic Problems in Group Theory”.

[Dec’17] The paper “The Intersection Problem for Finite Monoids” by Lukas Fleischer and Manfred Kufleitner was accepted at STACS 2018.

[Jun’17] At the 12th International Computer Science Symposium in Russia (CSR), Lukas Fleischer and Manfred Kufleitner received a Best Paper Award for their publication “Green’s Relations in Finite Transformation Semigroups”, and Armin Weiss received a Best Paper Award for “The conjugacy problem in free solvable groups and wreath product of abelian groups is in $\text{TC}^0$ \text{TC}^0 “ which is joint work with Alexei Miasnikov and Svetla Vassileva.