Sprungmarken

Servicenavigation

       

Hauptnavigation

Bereichsnavigation

Diplom/Bachelor/Master-Arbeiten am Lehrstuhl 2


Aktuelle Themen (weitere Themen können auch direkt bei den Dozenten angefragt werden)

  • Kernmengen für Probabilistisches Clustering (vergeben)

    Clustering ist eine Methode, um Objekte in Gruppen zu unterteilen, so, dass Objekte in der gleichen Gruppe ähnlich, und Objekte in verschiedenen Gruppen deutlich verschieden sind. Beim euklidischen k-median Clustering sind die Objekte Punkte im euklidischen Raum, und die Ähnlichkeit zweier Punkte entspricht ihrem euklidischen Abstand. Probabilistisches k-median Clustering ist eine Erweiterung dieses Problems auf unsichere Eingabedaten, d.h. jeder Eingabepunkt kann an verschiedenen Stellen im euklidischen Raum erscheinen. Eine Kernmenge ist eine kleine gewichtete Teilmenge der gegebenen Punkte, die die Punktmenge bzgl. der Zielfunktion approximiert. Aufgabe der Bachelorarbeit ist die Implementierung eines vorhandenen Algorithmus für die Berechnung einer Kernmenge für probabilistisches k-median Clustering und die experimentelle Analyse dieses Algorithmus.

  • Parallelisierung von Streamingalgorithmen für geometrische Probleme (vergeben)

    MapReduce ist ein Framework zur Parallelisierung von Berechnungen auf massiven Datenmengen das 2004 von Google eingeführt wurde. Es entkoppelt den Entwurf von Algorithmen (und deren Implementierung) von der technisch schwierigen Realisierung der Nebenläufigkeit. Merge-and-Reduce hingegen ist ein Entwurfsmuster für Streamingalgorithmen, das auf der Idee von Kernmengen (s.o.) basiert und diese strukturiert vereinigt und reduziert, sodass zu jeder Zeit eine Menge an Daten erhalten wird, welche die ursprüngliche Eingabe bzgl. einer Zielfunktion approximiert und nur polylogarithmisch viel Speicher benötigt wird. Die rein sequenzielle Natur eines solchen Streamingalgorithmus für Clusteringprobleme soll im Rahmen der Arbeit konzeptionell in das parallele Setting von MapReduce umgesetzt und implementiert werden. Der wissenschaftliche Anteil kann, je nach Interessen und Vorlieben, bei der empirischen Analyse von realen Daten aus einem Projekt der Fakultät für Physik oder auch bei der theoretisch algorithmischen Analyse liegen.

Bei Interesse wenden Sie sich bitte an Herrn Prof. Dr. Sohler.