[Mittagsseminar TI] Fwd: [i-prof] [i-studi] Einladung zur Verteidigung meiner Bachelorarbeit

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

On Thursday. The talk will be in German.


-------- Weitergeleitete Nachricht --------
Betreff: [i-prof] [i-studi] Einladung zur Verteidigung meiner Bachelorarbeit
Datum: Tue, 26 Nov 2019 13:23:28 +0100
Von: Jennifer Manke <jennyonline@zedat.fu-berlin.de>
An: i-profs@inf.fu-berlin.de
Kopie (CC): diana.schueler@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 Verteidigung meiner Bachelorarbeit mit
dem Thema "Zip-Trees: Analysis, Implementation and Comparison with Related
Data Structures" ein.
Die Verteidigung findet am 28.11.2019 um 12:00Uhr im Raum SR055 in der
Takustraße 9 statt.
Betreut wurde die Arbeit von Prof. Dr. Wolfgang Mulzer und Zweitgutacher
ist PD Dr. Klaus Kriegel.
Der Vortrag wird auf Deutsch gehalten.

Mit freundlichen Grüßen,
Jennifer Manke


Zusammenfassung:
Die Arbeit behandelt Zip-Trees, eine neue Art binärer Suchbäume, die von
Tarjan, Levy und Timmel 2019 eingeführt wurde. In einem Zip-Tree bekommt
jeder Knoten einen sogenannten "Rang" zugewiesen, der einer aus einer
geometrischen Verteilung gezogenen natürlichen Zahl entspricht. Betrachtet
man einen perfekt balancierten binären Baum fällt auf, dass die Verteilung
der Knoten auf die verschiedenen Ebenen des Baumes exakt einer
geometrischen Verteilung mit Mittelwert eins entspricht. Daher besteht die
Kernidee hinter Zip-Trees darin, die Knoten zusätzlich zur binären
Suchbaumeigenschaft anhand des zugewiesenen Ranges nach der
max-heap-Eigenschaft anzuordnen, um den Baum damit in eine einigermaßen
balancierte Form zu bringen. Der zweite Grundgedanke der Zip-Trees besteht
darin, anstatt Rotationen sogenannte "zip" und "unzip" Operationen zu
verwenden, um die Struktur des Baumes beim Einfügen und Löschen zu
erhalten.
Neben einer theoretischen Analyse der Eigenschaften der Zip-Trees befasst
sich die Bachelorarbeit mit einem Vergleich dieser neuen Bäume gegen
bereits etablierte verwandte Datenstrukturen. Ausgewählt wurden hierbei
Treaps, Skip-Listen, AVL-Bäume sowie Rot-Schwarz-Bäume. All diese
Datenstrukturen werden in der Arbeit kurz besprochen und sowohl in ihren
theoretischen Eigenschaften als auch mit Hilfe konkreter Implementierungen
mit Zip-Trees verglichen. Damit konnte gezeigt werden, dass Zip-Trees,
insbesondere in einer neueren, optimierten Variante, durchaus performant
sind und sie aufgrund ihrer vergleichsweise einfachen Implementierung
durchaus als Alternative zu "klassischeren" Datenstrukturen in Erwägung
gezogen werden sollten.

_______________________________________________
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