Graphpartitionierung und Graphenclustern in Theorie und Praxis

  • Typ: Block-Vorlesung (BV)
  • Semester: SS 2017
  • Zeit: 06.06.2017
    08:00 - 11:30 täglich
    50.34 Raum 236 50.34 INFORMATIK, Kollegiengebäude am Fasanengarten


    07.06.2017
    14:00 - 17:15 täglich
    50.34 Raum 236 50.34 INFORMATIK, Kollegiengebäude am Fasanengarten

    08.06.2017
    14:00 - 17:15 täglich
    50.34 Raum -120 50.34 INFORMATIK, Kollegiengebäude am Fasanengarten

    09.06.2017
    08:00 - 11:30 täglich
    50.34 Raum 236 50.34 INFORMATIK, Kollegiengebäude am Fasanengarten

    12.06.2017
    09:45 - 13:00 täglich
    50.34 Raum -120 50.34 INFORMATIK, Kollegiengebäude am Fasanengarten

    13.06.2017
    08:00 - 11:30 täglich
    50.34 Raum 236 50.34 INFORMATIK, Kollegiengebäude am Fasanengarten

    14.06.2017
    14:00 - 17:15 täglich
    50.34 Raum 236 50.34 INFORMATIK, Kollegiengebäude am Fasanengarten

    16.06.2017
    08:00 - 11:30 täglich
    50.34 Raum 236 50.34 INFORMATIK, Kollegiengebäude am Fasanengarten

    24.07.2017
    09:45 - 13:00 täglich
    50.34 Raum -120 50.34 INFORMATIK, Kollegiengebäude am Fasanengarten

    25.07.2017
    08:00 - 11:30 täglich
    50.34 Raum 236 50.34 INFORMATIK, Kollegiengebäude am Fasanengarten

    26.07.2017
    14:00 - 17:15 täglich
    50.34 Raum 236 50.34 INFORMATIK, Kollegiengebäude am Fasanengarten

    27.07.2017
    14:00 - 17:15 täglich
    50.34 Raum -120 50.34 INFORMATIK, Kollegiengebäude am Fasanengarten

    28.07.2017
    08:00 - 11:30 täglich
    50.34 Raum 236 50.34 INFORMATIK, Kollegiengebäude am Fasanengarten
  • Dozent: Dr. Christian Schulz
    Prof. Dr. Peter Sanders
  • SWS: 2/1
  • LVNr.: 2400008
VoraussetzungenEmpfehlungen:

Kenntnisse zu Graphentheorie und Algorithmentechnik sind hilfreich.

Beschreibung
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 die theoretischen als auch die praktischen Aspekte der Graphpartitionierung und des Graphenclusterns vermittelt.Dies beinhaltet Heuristiken, Meta-Heuristiken, evolutionäre und genetische Algorithmen sowie Approximations- und Streamingalgorithmen.
LehrinhaltDieses Modul soll Studierenden die theoretischen und praktischen Aspekte der Graphpartitionierung und des Graphenclusterns vermitteln.
AnmerkungDie Lehrveranstaltung findet unregelmäßig statt, Auskünfte erteilt das Institut für Theoretische Informatik, Prof. Sanders.
ArbeitsbelastungVorlesung mit Projekt/Experiment mit 3 SWS, 5 LP entsprechen ca. 150 Arbeitsstunden, davon

ca. 30 Std. Besuch der Vorlesung
ca. 60 Std. Vor- und Nachbereitung
ca. 30 Std. Bearbeiten des Projekts/Experiments
ca. 30 Std. Prüfungsvorbereitung

ZielZiel 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.

PrüfungDie Erfolgskontrolle erfolgt durch eine mündliche Prüfung nach § 4 Abs. 2 Nr. 2 SPO und eine Erfolgskontrolle anderer Art nach § 4 Abs. 2 Nr. 3 der SPO (Seminararbeit/Präsentation/Programmieraufgabe o. ä.). Die Gesamtnote setzt sich aus den benoteten und gewichteten Erfolgskontrollen (i.d.R. 80% der mündlichen Prüfung und 20% der weiteren Leistung) zusammen.