Einführung in die Graphen- und Berechenbarkeitstheorie

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 ueberschneiden, 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 Fraben 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 formalen Sprache, der Grammatiken, der endlichen Automaten und der Turing Maschinen eingegangen, um die Komplexität eines Problems präzise beschreiben zu können. Dies 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 (3 Leistungspunkte) über ein elementares Thema oder einen Seminarvortrag (6 Leistungspunkte) über ein fortgeschrittenes Thema zu halten. Eine Vorbesprechung findet am Mittwoch, den 9.7. um 11:00 Uhr in M201 statt. Hier sollen die ersten Vorträge vergeben werden. Eine Anmeldung ist auch per Email (florian.strunk@mathemath.uni-regensburg.de) möglich. Literatur: -- Diestel, Reinhard. Graphentheorie. -- Hopcroft, John E., J. D. Ullman. Einführung in die Automatentheorie, formale Sprachen und Komplexitätstheorie.