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
Datum:
Dozenten: Prof. Dr. Karsten Weihe
Semester: WiSe 2014/15
Themenbereiche: Ingenieurswissenschaften
Bereiche: Informatik
Sprache: deutsch
Links:
Vorlesungen:
- Effiziente Graphenalgorithmen - Vorlesung 03 31.10.2014
- Effiziente Graphenalgorithmen - Vorlesung 04 31.10.2014
- Effiziente Graphenalgorithmen - Tafelfoto Vorlesung 01 31.10.2014
- Effiziente Graphenalgorithmen - Tafelfotos Vorlesung 02 31.10.2014
- Effiziente Graphenalgorithmen - Tafelfotos Vorlesung 03 31.10.2014
- Effiziente Graphenalgorithmen - Vorlesung 01 31.10.2014
- Effiziente Graphenalgorithmen - Vorlesung 02 31.10.2014