Logo der Universit├Ąt   IMPRESSUM    DATENSCHUTZ
Fakultät für Mathematik Universität Regensburg
Einführung in die Graphen- und Berechenbarkeitstheorie
Semester
SoSe 2019

Dozent/in
Florian Strunk

Veranstaltungsart
Seminar /Proseminar

Inhalt
In dieser Veranstaltung beschäftigen wir uns zunächst mit den grundlegenden Begriffen der
Graphentheorie und elementaren Beziehnungen zwischen diesen. So werden zum Beispiel der Heiratssatz,
die Plättbarkeit von Graphen und Färbbarkeitsprobleme untersucht. Diese Probleme spielen
auch in der Praxis eine wichtige Rolle: Beispielsweise ist das Problem, eine Schaltung so auf eine
Platine zu drucken, dass sich keine zwei Leiterbahnen überschneiden, ein
Plättbarkeitsproblem eines Graphen. Der Fünffarbensatz entscheidet das folgende
Färbbarkeitsproblem: Ist es möglich jede vernünftige Landkarte so mit fünf
Farben zu färben, dass keine zwei Länder mit derselben Farbe aneinandergrenzen? Um
nicht nur eine theoretische 'ja/nein'-Antwort auf diese Fragen zu bekommen sondern um zu
entscheiden, ob eine Lösung der genannten Probleme in hinnehmbarer Zeit praktisch z.B. durch
einen Computer zu konstruieren ist, wollen wir uns mit der Theorie der Berechenbarkeit und
Komplexität beschäftigen. Es wird auf die grundlegenden Begriffe der
Berechenbarkeitstheorie wie den Begriff der endlichen Automaten und der Turing Maschinen
eingegangen, um die Komplexität eines Problems präzise beschreiben zu können. Dieses
führt zu dem vermutlich wichtigsten ungelösten Problem der Informatik: Ist P=NP oder
nicht? Diese und weitere spannende Fragen werden wir zu verstehen versuchen. Bei der genauen Wahl
der Themen kann auf besondere Interessen der TeilnehmerInnen eingegangen werden. Es ist
möglich, entweder einen Proseminarvortrag über ein elementares Thema oder einen
Seminarvortrag über ein fortgeschrittenes Thema zu halten.

Termin
Mittwochs, 10-12 Uhr

Ort
M009

Anmeldung
  • Vorbesprechung/Themenvergabe: Mittwoch, den 6.2. um 14:15 in M219
  • Anmeldung zu Studienleistungen/Prüfungsleistungen: FlexNow
Studienleistungen
  • Referat: Halten eines Seminarvortrags von ca. 90 Minuten
Prüfungsleistungen
  • Schriftliche Ausarbeitung des Seminarvortrags
Regelungen bei Studienbeginn vor WS 2015 / 16
  • Benotet:
    • O. g. Studienleistung und o. g. Prüfungsleistung; die Note ergibt sich aus der Prüfungsleistung
  • Unbenotet:
    • O. g. Studienleistung und Bestehen der o. g. Prüfungsleistung
Module
BSem, LA-GySem

ECTS
3 für BSem, 6 für LA-GySem
Druckansicht