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.
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 der Regression wird der Zusammenhang zwischen einer abhängigen Variable y und mehreren unabhängigen Variablen (oder Merkmalen) x1,x2,...xd untersucht. Die einfachsten Regressionmodelle gehen von einem linearen Zusammenhang der abhänigen und unabhängigen Variablen aus, d.h. y ≈ w1x1+w2x2+...wdxd + w0. Möglichst gute Modelle werden ermittelt, indem die Parameter w so eingestellt werden, dass die Abweichung von vorhergesagtem Wert w1x1+w2x2+...wdxd + w0 und vorher bekanntem Wert y für eine vorliegende Menge an N Daten möglichst gering ist. Klassische Verfahren gehen dabei von einem wahlfreien Zugriff auf die Daten aus. Aktuell werden in der theoretischen Informatik Verfahren entwickelt, die auch für einen nicht wahlfreien Zugriff auf die Daten (etwa wenn N die Größe des Hauptspeichers überschreitet) gute Parameter w bestimmen. Aufgabe der Arbeit ist die Untersuchung solcher Algorithmen unter der Berücksichtung von gewissen Einschränkungen (Ridge/LASSO) für w.
Thresholdfunktionen, d.h. Boolesche Funktionen, deren Funktionswert 1 ist, wenn die Summe der durch reelle Koeffizienten gewichteten Eingabebits einen reellen Schwellwert überschreitet, spielen in vielen Bereichen der Informatik eine wichtige Rolle. Eingeschränkte Thresholdfunktionen, sogenannte multivariate Thresholdfunktionen, haben sich in der Analyse OBDD-basierter impliziter Graphalgorithmen bewährt. Es ist wohlbekannt, dass die Darstellungsgröße von OBDDs für eine Boolesche Funktion je nach Wahl der Variablenordnung stark variieren kann. Die Schwierigkeit des Problems für eine Thresholdfunktion ein OBDD minimaler Größe zu bestimmen, ist offen, d.h. es ist unbekannt, ob es sich um ein NP-hartes Problem handelt. Beschränkt man die Anzahl verschiedener Koeffizienten auf eine Konstante, so existiert ein polynomieller Algorithmus, der auf Dynamischer Programmierung beruht. Aufgabe der Bachelorarbeit ist die Analyse und die Implementierung dieses Algorithmus und seine experimentelle Evaluierung, sowie Untersuchungen des Variablenordnungsproblems für multivariate Thresholdfunktionen.
OBDD-basierte Graphalgorithmen arbeiten auf impliziten Knoten- und Kantenmengen, d.h. anstelle von Adjazenzlisten oder -matrizen sind die Eingabegraphen über charakteristische Funktionen ihrer Knoten- und Kantenmengen gegeben. Bei geeigneter Wahl einer Datenstruktur für die entsprechenden Booleschen Funktionen kann es für stark strukturierte Graphen zu erheblichen Größeneinsparungen kommen. Allerdings werden manche der zu lösenden Graphprobleme komplexer. So ist gezeigt worden, dass es z.B. bei der Berechnung minimaler Spannbäume zu einem exponentiellen blow-up von Eingabe- zur Ausgabelänge kommen kann. Ziel der Bachelorarbeit ist die Betrachtung bekannter worst-case Beispiele für verschiedene Graphprobleme und die Untersuchung, welchen Einfluss die Wahl der Knotencodierung auf die erzielten Ergebnisse hat.
OBDD-basierte Graphalgorithmen arbeiten auf impliziten Darstellungen der Knoten- und Kantenmenge eines Eingabegraphen, d.h. anstelle expliziter Repräsentationen wie Adjazenzlisten oder -matrizen sind die Eingabegraphen über charakteristische Funktionen ihrer Knoten- und Kantenmengen gegeben, wobei Knoten und Kanten geeignet binär codiert sind. Prioritätsfunktionen sind ein wichtiges Konzept, um effizient Kanten oder Nachbarknoten auszuwählen. Auf der einen Seite sollen Prioritätsfunktionen in kleiner Größe dargestellt werden können, auf der anderen Seite sollen sie bei der Auswahl von Kanten und Nachbarknoten möglichst gut streuen. Ziel der Bachelorarbeit ist die Untersuchung verschiedener Prioritätsfunktionen und eine experimentelle Evaluierung, welchen Einfluß die Wahl der Prioritätsfunktion auf verschiedene (bekannte) implizite Graphalgorithmen hat. Neben einer experimentellen Analyse besteht der theoretische Anteil der Arbeit in der Konstruktion von worst-case Beispielen.
Die Behandlung von Matchings ist ein wichtiges Teilproblem für viele Optimierungsprobleme. Ein Matching in einem ungerichteten Graphen ist eine Teilmenge der Kantenmenge, so dass für zwei beliebige Kanten aus dieser Teilmenge gilt, dass sie keinen gemeinsamen Knoten haben. Ein Matching ist kardinalitätsmaximal für einen Graphen G, wenn es kein Matching in G gibt, das mehr Kanten enthält. In gewichteten Graphen sind die Kosten eines Matchings die Summe der Kanten, die zu dem Matching gehören. Für bipartite Graphen, d.h. Graphen G, deren Knotenmenge in zwei nichtleere Teilmengen partitioniert werden können, so dass jede Kante in G zu Knoten aus beiden Teilmengen inzident ist, existieren OBDD-basierte Graphalgorithmen, die für die Berechnung kardinalitätsmaximaler Matchings mit einer sublinearen Anzahl von Operationen auskommen (in Bezug zur Knotenanzahl der Eingabegraphen). Ziel der Arbeit ist die Erweiterung dieser Algorithmen für die Berechnung maximaler gewichteter Matchings (in bipartiten Graphen), d.h. Matchings, die maximale Kosten haben. Hier interessieren wir uns auch für Approximationsalgorithmen, d.h. für Algorithmen, die nicht notwendigerweise eine exakte Lösung bestimmen, für deren Ausgabe jedoch garantiert werden kann, dass sie nicht zu weit von einer optimalen Lösung entfernt ist.
Die Bestimmung von Matchings ist ein wichtiges Teilproblem für viele Optimierungsprobleme. Ein Matching in einem ungerichteten Graphen ist eine Teilmenge der Kantenmenge, so dass für zwei beliebige Kanten aus dieser Teilmenge gilt, dass sie keinen gemeinsamen Knoten haben. Ein Matching ist kardinalitätsmaximal für einen Graphen G, wenn es kein Matching in G gibt, das mehr Kanten enthält. Es ist ein offenes Problem in der Theoretischen Informatik, ob es für bipartite Graphen, d.h. Graphen G, deren Knotenmenge in zwei nichtleere Teilmengen partitioniert werden können, so dass keine Kante in G zu zwei Knoten aus der gleichen Teilmenge inzident ist, OBDD-basierte Graphalgorithmen existieren, die für die Berechnung kardinalitätsmaximaler Matchings mit einer polylogarithmischen Anzahl von Operationen auskommen (in Bezug zur Knotenanzahl der Eingabegraphen). Die Antwort auf diese Frage würde ein wichtiges Problem aus der Komplexitätstheorie lösen. Für eingeschränkte Graphklassen konnte die Frage bereits geklärt werden. Ausgehend von einem bereits bekannten parallelen Algorithmus ist das Ziel der Bachelorarbeit, einen OBDD-basierten Algorithmus zu entwerfen und zu analysieren, der die Berechnung kardinalitätsmaximaler Matchings für eingeschränkte bipartite Graphen mit einer polylogarithmsichen Anzahl von Operationen durchführt.
Die Berechnung von Matchings spielt als Teilproblem in vielen Anwendungen eine wichtige Rolle. Ein Matching in einem ungerichteten Graphen ist eine Teilmenge der Kantenmenge, so dass für zwei beliebige Kanten aus dieser Teilmenge gilt, dass sie keinen gemeinsamen Knoten haben. Ein Matching ist inklusionsmaximal für einen Graphen G, wenn es keine echte Teilmenge eines anderen Matchings in G ist. OBDD-basierte Graphalgorithmen arbeiten auf impliziten Knoten- und Kantenmengen, d.h. anstelle von Adjazenzlisten oder -matrizen sind die Eingabegraphen über charakteristische Funktionen ihrer Knoten- und Kantenmengen gegegen. Für die Bestimmung inklusionsmaximaler Matchings existiert ein OBDD-basierter Graphalgorithmus, der lediglich eine polylogarithmische Anzahl von Operationen benötigt (in Bezug zur Knotenanzahl der Eingabegraphen). Ausgehend von einem bereits bekannten parallelen Algorithmus ist das Ziel der Bachelorarbeit, einen weiteren OBDD-basierten Algorithmus für die Berechnung inklusionsmaximaler Matchings zu entwerfen und zu analysieren, wobei dieser auf einer anderen Vorgehensweise als der bereits bekannte implizite Algorithmus beruht.
Eine Teilmenge der Kantenmenge eines ungerichteten Graphen ist ein Matching, wenn für zwei beliebige Kanten aus dieser Teilmenge kein gemeinsamer Knoten existiert. Ein Matching ist inklusionsmaximal für einen Graphen G, wenn es keine echte Teilmenge eines anderen Matchings in G ist. Ein Matching ist kardinalitätsmaximal für, wenn es kein Matching in G gibt, das mehr Kanten enthält. Inklusionsmaximale Matchings bilden häufig den Ausgangspunkt bei der Berechnung kardinalitätsmaximaler Matchings, indem erstere solange schrittweise verbessert werden, bis keine Verbesserung mehr möglich ist. Ziel der Arbeit ist die systematische Untersuchung, welchen Einfluß die Berechnung inklusionsmaximaler Matchings auf die Effizienz bereits bekannter impliziter Algorithmen für die Bestimmung kardinalitätsmaximaler Matchings hat. Ein Teilziel bildet der Entwurf und die Analyse verschiedener Heuristiken für die Berechnung inklusionsmaximaler Matchings.
Das Problem des Handlungsreisenden, kurz TSP genannt, ist ein wichtiges NP-hartes kombinatorisches Optimierungsproblem. Gegeben ist ein gewichteter, ungerichteter Graph, für den ein Kreis gesucht wird, der jeden Knoten genau einmal berührt und der minimale Kosten hat, wobei die Kosten eines Kreises als Summe der Kosten der Kanten, die auf dem Kreis liegen, definiert sind. Ein gewichteter Graph ist metrisch, wenn die Dreiecksungleichung erfült ist, d.h. das Gewicht einer Kante von einem beliebigen Knoten u zu einem beliebigen Knoten w ist immer höchstens so groß wie die Summe der Gewichte der Kanten von u nach v und von v nach w, wobei v ein beliebiger Knoten im Eingabegraphen ist. OBDD-basierte Graphalgorithmen arbeiten auf impliziten Knoten- und Kantenmengen, d.h. anstelle von Adjazenzlisten oder -matrizen sind die Eingabegraphen über charakteristische Funktionen ihrer Knoten- und Kantenmengen gegegen. Motivation für die Behandlung OBDD-basierter Graphalgorithmen ist die Hoffnung, dass sehr große strukturierter Graphen auf diese Weise effizienter behandelt werden können. Ziel der Arbeit ist der Entwurf, die Analyse und die experimentelle Evaluierung impliziter OBDD-basierter Approximationsalgorithmen für das metrische TSP, d.h. gesucht werden Algorithmen, die nicht notwendigerweise eine exakte Lösung bestimmen, für deren Ausgaben jedoch garantiert werden kann, dass sie nicht zu weit von einer optimalen Lösung entfernt sind. Ausgangspunkt ist ein bekannter Approximationslagorithmus, der auf Adjazenzdarstellungen von Graphen arbeitet und ein bereits bekannter implizite Algorithmus für die Berechnung minimaler Spannbäume.
Weitere Themen können auch direkt bei den Dozenten angefragt werden.