Graphenalgorithmen

Vorlesung und Übung (2VO+2UE)

Spezialvorlesung Diplom (042615+042616)
Vertiefungsmodul Master INF-MA-608
Wintersemester 2009/10

Dr. Markus Chimani

Thema

Viele Anwendungsprobleme aus der Praxis können als Graphenprobleme formuliert werden. In dieser Vorlesung beschäftigen wir uns mit einer Auswahl unterschiedlicher Graphenprobleme und betrachten verschiedene Strategien diese zu lösen. Gerade das Erlernen dieser verschiedenen möglichen Herangehensweisen bildet den Kern dieser Vorlesung.

Wir werden Probleme betrachten für die sich effiziente (d.h. polynomielle) Algorithmen finden lassen, und algorithmische Techniken kennenlernen um die erforderliche Laufzeit zu drücken. Ebenso werden wir uns aber auch mit NP-scheren Problemen beschäftigen: Auch für diese Aufgaben hat das Feld der Algorithmik einiges zu bieten!

Wir werden Algorithmen diskutieren, die solche Probleme z.B. beweisbar effizient lösen können, wenn bestimmte Instanzeigenschaften erfüllt sind - als Beispiel sei die Klasse der Graphen mit fixer Baumweite genannt (was immer dieses Konzept genau bedeutet; wir werden es in der Vorlesung schon noch definieren). Auf der anderen Seite werden wir auch FPT-Algorithmen kennen lernen, also Algorithmen die die Lösung exakt polynomiell berechnen können, unter der Voraussetzung, dass die Zielfunktion beschränkt werden kann.

Schliesslich werden wir auch Ansätze diskutieren, wie man NP-schwere Graphenprobleme (ohne bestimmte Parameter, wie oben genannt, zu kennen) oft in der Praxis dennoch exakt lösen kann, wenn man es nur geschickt angeht.

Da ich die Auswahl der Probleme gerne auch ein bisschen abhängig vom Vorwissen der Teilnehmer machen möchte, seien die folgenden Probleme nur exemplarisch aufgelistet, um eine Ahnung zu erhalten: Färbe-, Matching- und Schnittprobleme; Tour-, Netzwerkdesign- und Augmentierungsprobleme; Planarität, etc.

Teilnahmevoraussetzungen

Gründliche Kenntnisse der mathematischen Pflichtveranstaltungen sowie der Inhalte von DAP 2 und GTI im Studiengang Informatik oder Angewandte Informatik (für BA: Algorithmen und Datenstrukturen).

Prüfungsmodalitäten, Anrechenbarkeit

Diplomstudium

Schwerpunktgebiete:

Algorithmen, Komplexität und formale Modelle; Computational Intelligence und Natural Computing; Intelligente Systeme.

Mündliche Fachprüfung (Möglichkeit A):

über 2VO+2UE, 6LP, Stoff der VO und UE, mündliche Prüfung.
(Formal darf keine Teilnahme an der UE gefordert werden, der Stoff ist jedoch in dem Prüfungsstoff, da 6LP).

Leistungsnachweis (Möglichkeit B):

über 2VO+2UE, 6LP, Stoff der VO und UE, regelmässige aktive Teilnahme an UE, Fachgespräch.

Master

Forschungsbereich:

Algorithmen und Komplexität.

Modulprüfung:

über 2VO+2UE, 6LP, Stoff der VO und UE, regelmässige aktive Teilnahme an UE, mündliche Prüfung.

Vorlesung

Regelmässiger Termin: Mi. 14:15-15:45, OH14, Raum 304

11. Nov: Entfällt wegen Fachschaftsvollversammlung.
18. Nov: Raumänderung wegen Schülertag. OH14, Raum 204 (genau ein Stockwerk darunter).

Die Vorlesungseinheit zu Baumzerlegung basiert teilweise auf dem Buch Invitation to Fixed-Parameter Algorithms von Prof. R. Niedermeier (Oxford University Press), sowie seinen Vorlesungsfolien (vergl. http://theinf1.informatik.uni-jena.de/~niedermr/). Die Vorlesungseinheit zum Primal-Dualen Approximationsalgorithmus basiert teilweise auf dem Buch Approximation Algorithms von Prof. V. Vazirani (Springer Verlag).

Übung

Die Übung ist eine Mischung zwischen verschiedenen Aufgaben, die in Kleingruppen bearbeitet werden: Zum einen "klassische" Übungsaufgaben für alle; zum anderen spezielle Aufgaben (Kurzvorträge), die auf die einzelnen Gruppen aufgeteilt werden (z.B. sich mit einem weiterführenden Paper beschäftigen, etc.).

Ca. 2-wöchentlicher Termin (s.u.): jeweils Mo. 14:00-16:00, OH14, Raum 304

Für die "zweite Runde" bei den Vorträgen: Ihr dürft die wirklich kurz halten, und nur die direkten Fragen der Aufgabe beantworten!