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

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

Dienstag.


-------- Forwarded Message --------
Subject: [i-prof] Einladung zur Verteidigung meiner Bachelorarbeit
Date: Tue, 29 Nov 2016 19:38:39 +0100
From: Benjamin Aram Berendsohn <beab@zedat.fu-berlin.de>
To: i-profs@inf.fu-berlin.de, i-wimis@inf.fu-berlin.de, 
i-studi@inf.fu-berlin.de
CC: renee.zentiks@fu-berlin.de

Sehr geehrte Damen und Herren,

hiermit möchte ich Sie herzlich zur Verteidigung meiner Bachelorarbeit
mit dem Titel "Deterministisches Partitionieren in linearer Zeit auf der
Word-RAM" einladen. Die Verteidigung findet am Dienstag, den 6.12.2016
um 12:00 s.t. im Raum 055 in der Takustraße 9 statt. Die Arbeit wurde
von Prof. Dr. Wolfgang Mulzer betreut, Zweitgutachter ist Prof. Dr.
Günter Rote.

Zusammenfassung: Sortieren ist ein fundamentales algorithmisches Problem
mit vielfältigen Anwendungsmöglichkeiten. Für die Laufzeit von
vergleichsbasiertem Sortieren ist eine untere Schranke von Omega(n log
n) bekannt, für das Sortieren von ganzen Zahlen (integer sorting) gilt
diese Schranke allerdings nicht. Für die Word-RAM, eine Variante der
RAM, die zwar Operationen im Einheitskostenmaß misst, aber eine abhängig
von der Anzahl und Größe der Eingabezahlen beschränkte Registergröße
hat, existieren Algorithmen, die Zahlen beliebiger Größe in o(n log n)
Zeit sortieren können. In dieser Arbeit soll der Algorithmus von Han und
Thorup mit einer Laufzeit von O(n sqrt(log log n)) vorgestellt werden.
Dabei wird sich auf das folgende Hauptergebnis beschränkt: ein
Algorithmus zum Partitionieren von n Zahlen in eine Folge von
Teilmengen, sodass alle Elemente einer Teilmenge kleiner als die der
folgenden Teilmenge sind und jede Teilmenge höchstens sqrt(n) Zahlen
oder nur gleiche Zahlen enthält.

Mit freundlichen Grüßen,

Benjamin Berendsohn

_______________________________________________
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