Graphenalgorithmen (Sommersemester 2019)

Dozent: Prof. Dr. Tobias Friedrich (Algorithm Engineering) , Dr. Pascal Lenzner (Algorithm Engineering)
Website zum Kurs: https://hpi.de/friedrich/teaching/ss19/graphenalgorithmen.html

Allgemeine Information

• Semesterwochenstunden: 4
• ECTS: 6
• Benotet: Ja
• Einschreibefrist: 26.04.2019
• Lehrform: Vorlesung / Übung
• Belegungsart: Wahlpflichtmodul
• Lehrsprache: Deutsch
• Maximale Teilnehmerzahl: 60

Studiengänge, Modulgruppen & Module

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. Es ist jedoch vorteilhaft die Vorlesung "Algorithmix" bereits gehört zu haben.

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 Hausaufgaben gestellt, von deren erfolgreicher Bearbeitung die Zulassung zur Prüfung abhängt. Am Ende des Semesters wird es eine mündliche Prüfung von ca. 30 Minuten geben.

Termine

Dienstags um 11:00-12:30 Uhr im Raum H.E.51

Donnerstags um 11:00-12:30 Uhr im Raum H.E.51

Ausnahmsweise wird der 1. Termin (09.04.) im Raum H-2.57 und der 2. Termin (11.04.) im Raum A-1.1 stattfinden!

Zurück