Algorithmische Graphentheorie
Overview
| Instructor |
Prof. Dr. rer. nat. Volker Turau
|
| ECTS credit points | 2.0 |
| Workload | 60 hours total |
| Performance record | Presentation, Participation |
| Period | Is offered no more |
| Language | German |
Beschreibung
Jedes System, das aus diskreten Zuständen oder Objekten und Beziehungen zwischen diesen besteht, kann als Graph modelliert werden. Viele Anwendungen erfordern effiziente Algorithmen zur Verarbeitung derartiger Systeme. Der Schwerpunkt dieses Seminars liegt auf Entwurfsmethoden für die algorithmische Graphentheorie. Viele allgemeine Entwurfsmethoden der Algorithmik lassen sich auch beim Entwurf von Algorithmen für graphentheoretische Probleme einsetzen. Die Vorträge in diesem Seminar stellen jeweils eine Entwurfsmethode vor und setzen diese in einem Beispiel um.
Inhalt
Es werden folgende Themen behandelt:
- Datenstrukturen für Graphen
- Greedy Technik
- Backtracking
- Branch & Bound
- Teile & Herrsche
- Dynamische Programmierung
- Lineare Programmierung
- A* und iterativer A* Algorithmus
- Sortieren mit Bäumen, Vorrangwarteschlangen
- Algorithmen von Prim und Kruskal
- Steinerbäume, Approximation
- Intervallgraphen und chordale Graphen