20-00-0110-iv Effiziente Graphenalgorithmen

Lehrende: Prof. Dr. rer. nat. Karsten Weihe

Veranstaltungsart: Integrierte Veranstaltung

Orga-Einheit: FB20 Informatik

Anzeige im Stundenplan: Effiz. Graphalgorith

Fach:

Anrechenbar für:

Semesterwochenstunden: 4

Unterrichtssprache: Englisch

Min. | Max. Teilnehmerzahl: - | -

Lehrinhalte:
Besonderheit im Wintersemester 2021/22:

In diesem Semester findet diese Lehrveranstaltung ohne Vorlesungstermine statt, ansonsten gibt es keine Unterschiede zu früheren Semestern. Die Vorlesung wurde in einem früheren Jahr aufgezeichnet und steht Ihnen in der Videothek Algorithmik auf youtube zur Verfügung. Alle Informationen zu Vorlesung, Übungsbetrieb und Prüfung finden Sie auf moodle.informatik.tu-darmstadt.de im Kurs "Effiziente Graphenalgorithmen WS 21/22".


Lernziele:

• Grundlegende Algorithmen kennen lernen
  
• Verfahren zur Effizienzsteigerung kennen lernen
  
• Analyse von Graphenalgorithmen
  
• Ausnutzen von speziellen Eigenschaften (Planarität, Dünnbesetztheit)
  
• Urteilsfähigkeit, welche Verfahren in der Praxis effizient sind
  

• Kürzeste-Wege-Probleme
  
• Netzwerk-Flussprobleme
  
• Matching-Probleme und Verallgemeinerungen
  
• Zusammenhangsprobleme in Graphen
  
• Minimal aufspannende Bäume
  
• Algorithmen für Probleme auf planaren Graphen
  

Literatur:

• Ahuja, Magnanti, Orlin: Network Flows, Prentice Hall, 1993.
• Cormen, Leiserson, Rivest, Stein: Introduction to Algorithms, MIT Press, 2nd edition, 2001.
• A. Schrijver: Combinatorial Optimization, Springer, 2003.
• R.E. Tarjan: Data Structures and Network Algorithms, SIAM, 1983.

Voraussetzungen:
Vorwissen:

• Grundlagen der Informatik II
• Einführung in Foundations of Computing