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

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

PS: The defense will be held in English.

On 28.01.2013 08:25, Wolfgang Mulzer wrote:
> Tuesday's noon seminar.
>
>
> -------- Original Message --------
> Subject: [i-prof] Einladung zur Verteidigung meiner Bachelorarbeit
> Date: Thu, 24 Jan 2013 15:20:03 +0100
> From: Terese Haimberger <tvhtoo@gmail.com>
> To: i-profs@inf.fu-berlin.de, i-wimis@inf.fu-berlin.de,
> i-studi@inf.fu-berlin.de, renee.zentiks@fu-berlin.de
>
> Sehr geehrte Damen und Herren,
>
> hiermit lade ich Sie herzlich zur Verteidigung meiner Bachelorarbeit
> mit dem Titel "Theoretische und Experimentelle Untersuchung von
> Kuckucks-Hashing" ein.
>
> Die Verteidigung findet im Rahmen des Forschungsseminars Theoretische
> Informatik am Dienstag, den 29.01.2013 um 12 Uhr s.t. im SR 055 der
> Takustraße 9 statt.
>
> Betreut wurde die Arbeit von Prof. Dr. Wolfgang Mulzer und Dr. Frank
> Hoffmann.
>
> Mit freundlichen Grüßen
>
> Terese Haimberger
>
>
> Zusammenfassung:
>
> Kuckucks-Hashing ist ein Hashverfahren, das einen amortisiert
> konstanten erwarteten Zeitaufwand für Einfügeoperationen und einen
> garantiert konstanten Zeitaufwand für Such- und Löschoperationen
> anbietet. Der Speicherplatzbedarf für eine Schlüsselmenge der Größe n
> ist dabei 2(1+ε)n für ein ε > 0. Die wesentliche Schwäche des
> Verfahrens ist, dass das Einfügen der Schlüsselmenge mit
> Wahrscheinlichkeit O(1/n) scheitert; es müssen neue Hashfunktionen
> gewählt und alle Schlüssel neu eingefügt werden.
>
> Im ersten Teil unserer Arbeit stellen wir einen Kodierungsbeweis zur
> Laufzeit der Einfügeoperation und zur Wahrscheinlichkeit des
> Scheiterns vor, der zuerst von Mihai Pătraşcu skizziert wurde. Wir
> verallgemeinern den Beweis, so dass er für beliebige ε > 0, statt nur
> für ε = 1, funktioniert.
>
> Im zweiten Teil führen wir Experimente durch, die einerseits die
> theoretischen Ergebnisse aus dem ersten Teil bestätigen und
> andererseits zeigen, dass es effiziente Hashfunktionen gibt, die beim
> Kuckucks-Hashing vergleichbare Eigenschaften aufweisen wie zufällige
> Funktionen; die Anzahl der Schritte beim Einfügen und die
> Wahrscheinlichkeit des Scheiterns steigen nur geringfügig.
>
> _______________________________________________
> 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