[Mittagsseminar TI] Fwd: Einladung zur Praesentation meiner Bachelorarbeit

[Wolfgang Mulzer <mulzer@inf.fu-berlin.de>]

Noon seminar Thursday.


-------- Forwarded Message --------
Subject: [i-prof] Einladung zur Praesentation meiner Bachelorarbeit
Date: Fri, 23 Jan 2015 22:45:06 +0100
From: Lilian Hung <lilian.hung@fu-berlin.de>
To: i-profs@inf.fu-berlin.de, i-wimis@inf.fu-berlin.de, 
i-studi@inf.fu-berlin.de

Sehr geehrte Damen und Herren,


hiermit lade ich Sie herzlich zur Präsentation meiner Bachelorarbeit mit
dem Titel

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

ein.

Die Präsentation findet am Donnerstag den 05.02.2015, 12:00 Uhr st in SR
055, Takustraße 9 statt.
Die Arbeit wurde von Prof. Dr. Wolfgang Mulzer betreut.


Zusammenfassung:

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.


Mit freundlichen Grüßen,
Lilian Hung

_______________________________________________
Automatischer Mailverteiler an Gruppe 'ml-i-prof-mi'.
Hinweise dazu siehe Hilfeseite:
https://www.mi.fu-berlin.de/w/Tec/AnkuendigungsVerteiler

Attachment: smime.p7s
Description: S/MIME Cryptographic Signature