Lilian Hung

Untersuchung einer Verbesserung des Algorithmus für das 3SUM-Problem und Anwendung an einem 3SUM-schweren Problem

Betreuer: Prof. Dr. Wolfgang Mulzer
Abschluss: Bachelor of Science (B.Sc.)
Abgabedatum: 05.02.2015

Kurzbeschreibung

Das 3SUM-Problem beschreibt das Ermitteln dreier Zahlen aus einer gegebenen Menge von n reellen Zahlen, die aufaddiert null ergeben. Bisher hat man noch keinen vergleichsbasierten Algorithmus für das 3SUM-Problem gefunden, der eine schnellere Laufzeit als n² hat. Diese Arbeit beschäftigt sich mit der genaueren Analyse des Artikels ”Threesomes, Degenerates and Love-Triangles” und vor allem mit dem Algorithmus zur Erstellung eines Entscheidungsbaums mit der subquadratischen Tiefe von O(n^(3/2)*(log n)^(3/2)). Dieser wird Schritt für Schritt in seinem Aufbau und Vorgehen erläutert. Es wird der wichtige Unterschied zwischen Entscheidungsbäumen und der Laufzeit von Algorithmen betrachtet.

Im zweiten Teil wird das 3SUM-schwere Problem "Ein Punkt auf drei Geraden" betrachtet. Es wird seine Komplexität untersucht und gezeigt, dass das 3SUM-Problem transformierbar zum "Ein Punkt auf drei Geraden"-Problem ist.