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