Hasso-Plattner-Institut
Prof. Dr. Tobias Friedrich
 

Graph Algorithms

MSc Vorlesung - Winter 2022/23

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.

Ein Teil der Vorlesungen wird auf Englisch gehalten!

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. Die Prüfungen werden auf Englisch abgehalten.

Termine

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

Donnerstags um 09:15 - 10:45 Uhr im Hörsaal HS3

Vorlesungsteam

Die Vorlesung wird veranstaltet vom Fachgebiet Algorithm Engineering. An der Durchführung sind die folgenden Personen beteiligt:

Dr. Pascal Lenzner

Dozent

Office: K-2.17
E-Mail: Pascal.Lenzner(at)hpi.de

Dr. George Skretas

Dozent

Office: K-2.07
E-Mail: Georgios.Skretas(at)hpi.de