GRAPA
Im Projekt GRAPA haben wir uns mit NP-schweren Problemen auf Graphen beschäftigt. Graphen sind eine Datenstruktur, die Knoten durch Kanten in Beziehung setzen und damit eine sehr intuitive Modellierung von Netzwerken erlaube. NP-schwere Probleme können wir nach heutigem Kenntnisstand nicht effizient lösen. So benötigt eine größere Eingabe, also z.B. ein Graph mit doppelt so vielen Knoten, ein Vielfaches an Berechnungszeit.
Kern unseres Projekts ist die Teilnahme an der PACE Challenge 2022. Dies ist ein internationaler Wettbewerb, in dem es darum geht, einen Algorithmus für ein konkretes Problem zu entwickeln. In diesem Jahr war das Problem das “Directed Feedback Vertex Set (DFVS)”, ein klassisches NP-schweres Problem. Ein DFVS ist eine Menge von Knoten, so dass ein Graph kreisfrei wird, wenn die Menge der Knoten entfernt wird. Es ist schwer ein kleinstes DFVS zu finden. Würden wir uns ein Straßennetz aus Einbahnstraßen vorstellen, so würden wir die kleinste Zahl von Kreuzungen suchen, so dass wir mit unserem Fahrrad von keinem Punkt einen Weg zurück zu unserem Startpunkt finden – egal, wo sich dieser befindet.
Das Ergebnis, wie wir bei dem Wettbewerb abgeschnitten haben, kennen wir noch nicht. In der Vorbereitungsphase gab es aber ein öffentliches Leaderboard, in dem wir uns im exakten-Track meist auf den oberen vier Plätzen bewegt haben. Gelernt haben wir aber jetzt schon sehr viel. Wir haben im Projekt verschiedene andere NP-schwere Probleme kennengelernt und viel über die Arbeit mit Graphen herausgefunden.
Auf dem Projekttag am 15.07.2022 findest du unser Projekt im Raum 1460. Von 11:30 bis ca. 12:00 Uhr stellen wir unser Projekt in einem Vortrag vor.
Außerdem haben wir einen Workshop vorbereitet, in dem du von 12:00 Uhr bis 13:00 Uhr selbst lernen kannst, wie du NP-Schwere Probleme praktisch angehen kannst. Der Workshop findet in Java statt, bitte merke dir dein Passwort für den Uni-Account.
Zur Projekt-Webseite