Seminar: Das Wortproblem, WS2014/15

Aktuelles

Ersatztermin für den 23. Dezember: Mittwoch, 7. Januar, 16:00 (s.t.!), M 101.
Ab 14. Oktober findet das Seminar in M 102 (statt M 104) statt.
Der erste Vortrag fand am 7. Oktober 2014 statt. Das Seminar beginnt um 8:25 und endet um 10:00.
Die Vortragstermine finden Sie in GRIPS.
Die Übersicht über die Vorträge ist online.
Die Vorlagen für Handouts/Ausarbeitungen sind online (s.u.); selbstverständlich können Sie Ihre Handouts/Ausarbeitungen auch anders erstellen/gestalten.
On reqeuest this seminar can be held in English.

Seminar: Das Wortproblem

Ein grundlegendes mathematisches Problem ist, welche Fragen algorithmisch beantwortet werden k�nnen bzw. welche Objekte �berhaupt algorithmisch klassifiziert werden k�nnen.

Ausgehend von Turings Entdeckung, dass das sogenannte Halteproblem nicht algorithmisch gel�st werden kann, kann man zeigen, dass selbst die einfachsten gruppentheoretischen Probleme nicht algorithmisch gel�st werden k�nnen. Ein solches Problem ist das Wortproblem: Gegeben sei eine Beschreibung einer Gruppe durch (endlich viele) Erzeuger und Relationen. Gibt es einen Algorithmus, der f�r W�rter in den Erzeugern entscheidet, ob das entsprechende Gruppenelement trivial ist oder nicht?

Diese algorithmische Unzug�nglichkeit der Gruppentheorie hat weitreichende Konsequenzen f�r viele mathematische Teilgebiete. Zum Beispiel folgt daraus, dass das Hom�omorphieproblem f�r Mannigfaltigkeiten nicht algorithmisch l�sbar ist. Insbesondere k�nnen Mannigfaltigkeiten nicht algorithmisch klassifiziert werden.

In diesem Seminar werden wir die Grundlagen der (Un)Entscheidbarkeit kennenlernen und auf gruppentheoretische Probleme anwenden. Insbesondere werden wir sehen, dass es Gruppen mit algorithmisch unentscheidbarem Wortproblem gibt und die Konsequenzen f�r topologische Klassifikationsprobleme betrachten.

On request, this course can be held in English

Zeit und Ort

Di, 8:25 -- 10:00, M 102

Material

Die �bersicht �ber alle Vortr�ge (und einige Hinweise zum Ablauf des Seminars).
LaTeX-Vorlage für Handouts: .tex, .pdf
LaTeX-Vorlage für Ausarbeitungen: .tex, .pdf
Hinweise zum Schreiben mathematischer Texte.

Voraussetzungen

Analysis I/II, Lineare Algebra I/II;
Grundbegriffe der Gruppentheorie (wie aus den Grundvorlesungen);

Leistungsnachweis

Notwendig f�r den Erwerb eines Leistungsnachweises sind:

F�r einen unbenoteten Leistungsnachweis: Halten eines Seminarvortrags; regelmäßige und aktive Teilnahme am Seminar; ein Handout von ein bis zwei Seiten, das die wichtigsten Aspekte des Vortrags und ein paar Übungsaufgaben enthält; eine schriftliche Ausarbeitung des Vortrags (diese muss bis spätestens eine Woche vor dem Vortrag abgegeben werden).
F�r einen benoteten Leistungsnachweis: Genauso wie für einen unbenoteten Leistungsnachweis. Grundlage für die Note ist der Vortrag.

Das Seminar kann im Bachelor/Master, Diplom, sowie im Lehramtsstudium eingebracht werden.
Aufbauend auf diesem Seminar können Themen für Abschlussarbeiten vergeben werden.

Letzte �nderung: 21. Dezember 2014