Wir freuen uns über Ihr Interesse. Wenn Sie an der Projektgruppe teilehmen möchten, schreiben Sie bitte bis zum 28.2.23 eine formlose Anmeldung per Email an Philip Mayer, damit wir die zu erwartende Teilnehmerzahl abschätzen können. Die Teilnehmerzahl ist auf 6 Teilnehmer beschränkt.
Modulhandbuch | BA-INF 051 |
---|---|
BASIS | BASIS |
Formale Anmeldung auf Basis | TBA |
Veranstalter | Prof. Dr. Petra Mutzel, Philip Mayer |
Termin | Wann | Wo |
---|---|---|
Vorbesprechung | TBA | TBA |
wöchentliche Besprechung | TBA | Raum 2.074 (Informatik Gebäude) |
Es wird eine dreitägige Blockveranstaltung geben, in der eine Einführung in C++ und in die Nutzung unserer Systeme gegeben wird. Diese wird wahrscheinlich vom 28-30.3 von 10:00-16:00 sein (der Termin kann sich noch nach hinten verschieben).
In diesem Semester beschäftigen wir uns in der PG Algorithm Engineering mit der Polygonalisierung von Punktmengen. Es sei eine Punktmenge S gegeben. Eine Polygonalsierung von S ist ein geschlossener Pfad (geradliniger Kanten), der sich nicht selbst schneidet und jeden Punkt in S genau einmal besucht. Solch ein Pfad teilt die Ebene in eine beschränkte und eine unbeschränkte Fläche. Die beschränkte Fläche ist ein einfaches Polygon. Eine beliebige Polygonalisierung einer Punktmenge kann sehr leicht in Zeit O(nlogn) gefunden werden. In der Projektgruppe beschäftigen wir uns mit flächenoptimalen Polygonalsierung, d.h. Polygonalisierungen, welche die Fläche des zugehörigen Polygons minimieren oder maximieren. Das finden solcher Polygonalsierungen ist NP-schwer. Des weiteren scheint das Problem auch aus praktischer Sicht schwer, da selbst die besten bekannten Algorithmen nur optimale Lösungen für sehr kleine Punktmengen berechnen können. Da die Algorithmen für relevante Anwendungen nicht praktikabel sind, wurden einige heuristische Ansätze zum Lösen der Probleme entwickelt.
In der Projektgruppe werden wir einige der heuristischen Ansätze implementieren, experimentell vergleichen und mit eigenen Idee erweitern. Die Ansätze sind motiviert durch heuristische Lösungsverfahren für das euklidische Traveling Salesperson Problem.
Ziel der Projektgruppe Algorithm Engineering ist es, ein erweitertes Verständnis für speicher- und laufzeiteffiziente Implementierung, die Durchführung von algorithmischen Experimenten, sowie die Interpretation der Ergebnisse solcher zu vermitteln.
Voraussetzung: Die Vorlesung Graphenalgorithmen oder Grundlagen der Algorithmischen Geometrie.
Im Fokus der Projektgruppe werden die Algorithmen, Datensätze und Ergebnisse des CG:SHOP 2019 liegen.
Eine gute Einführung bieten:
Nutzen sie für die weitere Literaturrecherche google scholar, DBLP oder ArXiV.
hilfreiche Tutorials zu diversen Themen (git, linux, ssh,...)
DozentInnen: Mutzel, Mayer