Teaching

• Vorlesung: dienstags 13:30-15:10 in S2|02 (Robert-Piloty-Gebäude) Raum C120, Beginn: 25.10.2011, Dozent: Dr. Wolfgang Stille (stille AT cs DOT tu-darmstadt DOT de)
• Übung / Praktikum: donnerstags 11:40-13:20 in S2|02 (Robert-Piloty-Gebäude) Raum C120, Beginn: 3.11.2011
• Sprechzeiten: im Anschluß an die Vorlesung/Übung und nach Vereinbarung per Email
• Klausurtermin: Dienstag 3.4.2012 11-13 Uhr in C205 (Piloty, S2|02)
• Material zu VL und Ü

Die Vorlesung vom 22.11.2011 verschiebt sich auf den 24.11.2011 11:40 - 13:20

Die Vorlesung vom 17.1.2012 verschiebt sich auf den 12.1.2012 11:40 - 13:20

Auf Basis analytischer Sachverhalte entwickeln wir algorithmische Ideen für Verfahren auf Graphen. Daraus entstehen zunächst generische Verfahren, welche formal bezüglich ihrer Korrektheit und Laufzeit analysiert werden. Im Anschluß daran werden in jedem Kapitel Techniken zur Verbesserung und Beschleunigung vorgestellt. Abgerundet wird der Stoffplan durch zahlreiche Modellierungs- und Anwendungsbeispiele und der (optionalen) Implementierung eines Benchmarks verschiedener algorithmischer Varianten. Die Veranstaltung vermittelt folgende Kompetenzen:

• Grundlegende Algorithmen und Datenstrukturen auf Graphen beherrschen
• Korrektheit und Laufzeit von Graphenalgorithmen analysieren
• Exakte und heuristische Möglichkeiten zur Effizienzsteigerung anwenden
• Ausnutzen spezieller Eigenschaften (Planarität, Dünnbesetztheit) und effizienter Datenstrukturen
• Urteilsfähigkeit, welche Verfahren in der Praxis effizient einsetzbar sind
• Implementierung verschiedener Varianten
• Modellierung verschiedener Problemstellungen auf Basis von Graphen, u.a. Problemen aus dem Knowledge Processing und der Sprachtechnologie
  

• Grundlegende Definitionen und Graphenrepräsentationen
• Graphtraversierung, BFS, DFS, (Strongly) Connected Components, TOPSORT, Bipartite und Eulersche Graphen, Graph Clustering
• Optimale Bäume und Branchings: MST Algorithmen, Edmonds Branching Algorithmus
• Kürzeste Wege-Probleme, Label Setting und Label Correcting Verfahren, Beschleunigungstechniken
• Netzwerkfluß-Probleme
  
  
  • Maximale Flüsse: Augmenting Path und Preflow-Push Algorithmen, Blocking Flows
  • Kostenminimale Flüsse: Optimalität, Dualität, Augmenting Path und Cycle Cancelling Algorithmen
• Matching- und Assignment Probleme: Weighted Matching, Cardinality Matching, Bipartite Graphs, Blossom Shrinking, Ungarische Methode
• Algorithmen auf speziellen Graphen: Planare Graphen, ...

• Mathematisches Grundverständnis (Mathe I-III)
• Kenntnisse in Algorithmen und Datenstrukturen (GdI II)
• gute Programmierkenntnisse in mindestens einer Programmiersprache (JAVA, C++) erwünscht
• Einführung in FoC und DKE oder gleichwertige Kenntnisse sind von Vorteil