Graphenalgorithmen (Sommersemester 2017)

Dozent: Prof. Dr. Tobias Friedrich (Algorithm Engineering) , Dr. Pascal Lenzner (Algorithm Engineering)

Allgemeine Information

• Semesterwochenstunden: 4
• ECTS: 6
• Benotet: Ja
• Einschreibefrist: 28.04.2017
• Lehrform: Vorlesung / Übung
• Belegungsart: Wahlpflichtmodul

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. Für die Benotung ist nur die Prüfung relevant. Die Prüfung wird am Semesterende stattfinden in Form einer mündlichen Prüfung durchgeführt.

Termine

• wöchentlich Dienstag um 13:30 Uhr, Raum A-2.2
• wöchentlich Donnerstag um 09:15 Uhr, Raum A-2.2

Der erste Termin findet am Dienstag, den 18.04.2017, statt.

Zurück