Veranstaltung

Inhalt: Viele Anwendungen der Informatik beinhalten das Clustern und die Partitionierung von Graphen, z. B. die Finite Element Methode in wissenschaftlichen Simulationen, Digitaler Schaltkreisentwurf, Routenplanung, Analyse des Webgraphen oder auch die Analyse von Sozialen Netzwerken.

Ein bekanntes Beispiel, in dem gute Partitionierungen von unstrukturierten Graphen benötigt werden, ist die Parallelverarbeitung. Hier müssen Graphen partitioniert werden, um Berechnungen gleichmäßig auf eine gegebene Anzahl von Prozessoren zu verteilen und die Kommunikation zwischen diesen zu minimieren. Wenn man k Prozessoren verwenden möchte, muss der Graph in k ungefähr gleich große Blöcke aufgeteilt werden, so dass die Anzahl Kanten zwischen den Blöcken minimal ist.
Da in der Praxis viele Partitionierungs- und Clusteringprobleme auftreten, werden die besprochenen Probleme vorgestellt und motiviert.

Es werden sowohl theoretische als auch praktische Aspekte der Graphpartitionierung und des Graphenclusterns vermittelt. Dies beinhaltet NP-Schwere-Beweise, heuristische und exakte Algorithmen, sowie parallele und verteilte Algorithmen.

Ziel der Vorlesung ist es, den Studierenden einen ersten Einblick in die Problematik des Graphpartitionierens und des Graphenclusterns zu vermitteln und dabei Wissen aus der Graphentheorie sowie der Algorithmik umzusetzen.Auf der einen Seite werden die auftretenden Fragestellungen auf ihren algorithmischen Kern reduziert und anschließend effizient gelöst. Auf der anderen Seite werden verschiedene Modellierungen und deren Interpretationen behandelt. Nach erfolgreicher Teilnahme können Studierende die vorgestellten Methoden und Techniken autonom auf verwandte Fragestellungen anwenden.

Die Erfolgskontrolle erfolgt in Form einer mündlichen Prüfung nach § 4 Abs. 2 Nr. 2 SPO und einer Übung als Prüfungsleistung anderer Art nach § 2 Abs. 2 Nr. 3. Gewichtung: 80 % mündliche Prüfung, 20 % Übung.

Kenntnisse zu Graphentheorie und Algorithmentechnik sind hilfreich

Arbeitsaufwand: Vorlesung mit Projekt/Experiment mit 3 SWS, 5 LP entsprechen ca. 150 Arbeitsstunden, davonca. 30 Std. Besuch der Vorlesungca. 60 Std. Vor- und Nachbereitungca. 30 Std. Bearbeiten des Projekts/Experiments ca. 30 Std. Prüfungsvorbereitung