[Mittagsseminar TI] [Fwd: [i-prof] [i-studi] Einladung zur Verteidigung meiner Bachelorarbeit]
Today in the noon seminar.
Sehr geehrte Damen und Herren,
hiermit lade ich Sie herzlich zur Verteidigung meiner Bachelorarbeit zum
Thema "Explorable Heap Selection" ein.
Die Verteidigung findet am Donnerstag, dem 18.09.2025, um 12:00 Uhr im
Raum 055 der Takustraße 9 statt.
Betreuer/Erstgutachter: Prof. Dr. László Kozma
Zweitgutachter: Prof. Dr. Wolfgang Mulzer
Mit freundlichen Grüßen
Felix Zimmerhofer
Abstract:
Ein prominentes Problem im Bereich der Algorithmik ist es, aus einer
(potenziell unendlich großen) Datenstruktur das n-kleinste Element zu
extrahieren. Abhängig vom zugrundeliegenden Maschinenmodell und der
betrachteten Datenstruktur kann dies mehr oder weniger effizient erfolgen.
Im Kontext von binären Heaps sind Algorithmen bekannt, welche das Problem
in O(n) Zeit lösen und damit optimal sind. Allerdings nur, wenn der
Zugriff auf die Knoten in konstanter Zeit möglich ist, das Maschinenmodell
also direkten Zugriff (engl. random access) erlaubt.
Muss ein Knoten hingegen erst gesucht werden, damit sein Wert ausgelesen
werden kann, und wird die Anzahl an Kanten, die dabei traversiert werden,
als Einheitskosten festgelegt, so konnte für dieses als "Explorable Heap
Selection" bezeichnete Problem eine superlineare obere Schranke bisher
noch nicht überwunden werden.
Die Arbeit beschreibt, analysiert und diskutiert verschiedene Algorithmen
zur Lösung dieses Problems und beleuchtet außerdem damit verbundene
Phänomene wie die Interdependenz zwischen Laufzeit und Speicher sowie das
Ausmaß des Einflusses von Zufall.
_______________________________________________
Automatischer Mailverteiler an Gruppe 'ml-i-prof-mi'.
Hinweise dazu siehe Hilfeseite:
https://www.mi.fu-berlin.de/w/Tec/AnkuendigungsVerteiler
