Hasso-Plattner-Institut
Prof. Dr. Tobias Friedrich
 

Graphenalgorithmen

MSc Lecture - Winter 2021/22

Beschreibung

Graphen spielen in der Welt der Algorithmen eine zentrale Rolle. Beispielsweise verwenden Navigationsgeräte zur Beantwortung einer Routenanfrage einen Algorithmus zur Berechnung kürzester Wege in einem Graphen.  Auch viele Planungs- und Zuweisungsprobleme lassen sich leicht als Probleme auf Graphen modellieren.  Im Prinzip gilt, dass man sehr viele Probleme als Graphenprobleme auffassen kann, weshalb der Entwurf effizienter Algorithmen für solche Probleme ein wichtiges Teilgebiet der theoretischen Informatik darstellt.

In dieser Vorlesung begeben wir uns in die Welt der Graphenalgorithmen. Dabei werden wir einerseits wichtige algorithmische Problemklassen auf Graphen und effiziente Algorithmen zu deren Lösung kennenlernen. Unter anderem werden wir uns mit dem Finden von kürzesten Wegen, Flüssen, Schnitten, Separatoren und Matchings in Graphen befassen. Algorithmen für diese Probleme haben vielfältigste Anwendungsmöglichkeiten und sind somit ein wichtiges und nützliches Werkzeug für jeden Algorithmiker.  Andererseits werden wir auch untersuchen, inwiefern sich Einschränkungen an die vorliegenden Graphen auf die Komplexität der Probleme und deren algorithmische Lösung auswirkt. Beispielsweise sind viele algorithmische Probleme auf Bäumen und planaren Graphen (d.h. Graphen die kreuzungsfrei in die Ebene eingebettet werden können) effizienter lösbar, als auf allgemeinen Graphen. Außerdem werden wir einige Eigenschaften von Graphen untersuchen, die wir gezielt für den Entwurf von effizienten Algorithmen ausnutzen können. Beispielsweise haben Bäume und planare Graphen kleine Separatoren (Knotenmengen, deren Entfernung die Graphen in mehrere Zusammenhangskomponenten zerfallen lassen), was dabei hilft effiziente Divide & Conquer Algorithmen zu entwerfen.

Ziel der Vorlesung ist die Entwicklung und Schulung einer strukturierten Herangehensweise an algorithmische Probleme auf Graphen. Wir entwickeln dabei gemeinsam effiziente Graphenalgorithmen mit passenden Datenstrukturen, beweisen deren Korrektheit und analysieren deren Ressourcenbedarf (Laufzeit und Speicherplatz). Außerdem wird die Vorlesung spezielle Graphklassen und andere wichtige Konzepte der Graphentheorie und deren Auswirkung auf die Welt der Algorithmen beleuchten.

Voraussetzungen

Die Vorlesung richtet sich an Master-Studierende, die Interesse am Entwurf und der Analyse von Algorithmen haben. Es gibt keine formalen Voraussetzungen, um diese Vorlesung zu belegen.

Lern- und Lehrformen

In der Vorlesung werden wir problemorientiert und zum Teil interaktiv arbeiten. Um dies zu erreichen, werden Vorlesungs- und Übungstermine je nach Bedarf gemischt.

Leistungserfassung

Es werden regelmäßig Übungsaufgaben gestellt, von deren erfolgreicher Bearbeitung die Zulassung zur Prüfung abhängt. Für die Prüfungszulassung ist das Erreichen von 50% der Gesamtpunktzahl in den Übungsserien notwendig. Am Ende des Semesters wird es eine mündliche Prüfung von ca. 30 Minuten geben.

Termine

Montags um 13:30 - 15:00 Uhr im Hörsaal HS3

Mittwochs um 13:30 - 15:00 Uhr im Hörsaal HS3