|
Einführung in die Graphen- und Berechenbarkeitstheorie SemesterSoSe 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
BSem, LA-GySem ECTS 3 für BSem, 6 für LA-GySem |