Department of Computer Science
Chair of Algorithm Engineering (Ls11)
Home Contact Deutsch English
menu-en
Vorlesung+Übung WS09/10: Graphenalgorithmen

Graphenalgorithmen

Vorlesung und Übung (2VO+2UE)

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

Dr. Markus Chimani


Thema
Teilnahmevoraussetzungen
Prüfungsmodalitäten, Anrechenbarkeit

Vorlesung
Übung

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).

Thema   Datum      1 Folie/Seite    6 Folien/Seite  
Einleitung & Heiratsproblem 14. Okt [PDF-1] [PDF-6]
Treewidth (&FPT) 21. Okt, 28. Okt, 4.Nov [PDF-1] [PDF-6]
Planaritätstest 18.Nov, 25.Nov [PDF-1] [PDF-6]
Graph-Isomophie 2.Dez, 9.Dez [A-1],[B-1] [A-6],[B-6]
TSP 16.Dez [PDF-1] [PDF-6]
Zweizusammenhangsaugmentierung 6.Jan [PDF-1] [PDF-6]
Dreizusammenhang 13.Jan, 20.Jan [A-1],[B-1] [A-6],[B-6]
Steinerbaum & Co / Primal-Dual Approx 27.Jan, 3.Feb [PDF-1] [PDF-6]

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

Blatt     Thema     Ausgabe    Besprechung     Kurzvorträge
Blatt 1 Heiratsproblem, Treewidth 21. Okt2. Nov 1.8: Zhivko
Blatt 2 Treewidth 4. Nov16. Nov 2.5: Sylvie, Carola;
2.6: Malte, Thomas, Henning
Blatt 3 Planarität 18. Nov30. Nov 3.5: Marianna, Maike;
3.6: Julie, Sebastian
Blatt 4 Einbettungen, Isomorphie 2. Dez14. Dez 4.6: Dominik, Lars;
4.7: Robert
Blatt 5 Isomorphie, TSP 16. Dez11. Jan 5.6: Marianna, Maike;
5.7: Dominik, Lars
Blatt 6 Bi- & Triconnectivity 21. Jan1. Feb 6.5: Robert

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

Imprint
<webmaster  ls11.cs.tu-dortmund.de>
The university does not accept liability for the contents of linked external internet sites