Abgeschlossene Bachelorarbeiten

39Abschlussarbeit(en)

Hinze-Hüttl, Alexander: Integration von Softwareprototypen zur optischen und teilautomatisierten Erkennung von Leiterplattenstrukturen

Betreuer: Prof. Dr. Wolfgang Mulzer
Abschluss: Bachelor of Science (B.Sc.)
Abgabedatum: 25.05.2016

Leiterplatten sind heutzutage essenzieller Bestandteil vieler Wirschafts- und Konsumgüter. Ist eine Leiterplatte defekt, beeinträchtigt dies meist das ganze Produkt oder macht es komplett unbrauchbar.

Für die Reparatur und Nachfertigung solcher defekten Leiterplatten werden Schalt- und Layoutpläne benötigt. Sind diese Pläne nicht verfügbar, müssen sie nachträglich abgeleitet werden.

Am Fraunhofer-Institut für Produktionsanlagen und Konstruktionstechnik wurden in dem Forschungsprojekt INPIKO mehrere automatisierte Verfahren vorgestellt und prototypisch implementiert, um besagte Pläne zu rekonstruieren.

Im Rahmen dieser Arbeit wurde eine neue Softwarelösung konzipiert und implementiert, die die Rekonstruktion solcher Plänen anhand eines Computertomographiescans einer Leiterplatte ermöglicht. Die in dem Forschungsprojekt entstandenen Verfahren wurden in die neue Softwarelösung integriert und erweitert. Durch die Kombination von manuellen und automatisierten Rekonsturktionsverfahren entsteht schließlich ein teilautomatisierter Rekonstruktionsprozess zur Ableitung der Pläne.

Mertens, Josephine: Entwicklung und Implementierung eines Verfahrens zur automatisierten CAD-Baugruppenrekonstruktion

Betreuer: Prof. Dr. Wolfgang Mulzer
Abschluss: Bachelor of Science (B.Sc.)
Abgabedatum: 20.05.2015

In industriellen Betrieben muss die Verfügbarkeit von kostenintensiven Maschinen und Anlagen über 30 bis 50 Jahre sichergestellt werden. Viele Unternehmen setzen daher zunehmend 3D-Scanning-Verfahren zur Inspektion und Instandhaltungsplanung (Reverse Engineering, RE)  ein. Problematisch hierbei ist der hohe manuelle Aufwand. Am Fraunhofer IPK im Bereich virtuelle Produktentstehung wird intensiv an einem automatisierten Prozessablauf geforscht. Dabei ist eine komplette Demontage der Baugruppe nicht mehr vorgesehen, wodurch Kosten und Zeit eingespart werden können. Diese Arbeit stellt ein grundlegendes Verfahren vor, dass eine automatisierte Rekonstruktion des Baugruppenmodells mit eingebauter Nutzerassistenz vorsieht. Dazu wurde ein Algorithmus für das Fitting von Einzelteilen in ein Gesamtobjekt unter der Verwendung der Open-Source-Bibliothek Point Cloud Library in C++ entwickelt. Ein weiterer Schwerpunkt bestand in der Programmierung der graphischen Benutzeroberfläche. Hierbei musste der Einbau einer manuellen Rotationsbedienung berücksichtigt werden, da eine automatisierte Rotation mittels algorithmischer Verfahren derzeit nicht möglich ist.  

Ehrhardt, Marcel: Computing the Convex Hulls and Voronoi Diagrams on GPU

Betreuer: Prof. Dr. Helmut Alt
Abschluss: Bachelor of Science (B.Sc.)
Abgabedatum: 01.01.2014

Knötel, David: Schnelle parallele Multiplikation großer Zahlen mit CUDA

Betreuer: Prof. Dr. Helmut Alt
Abschluss: Bachelor of Science (B.Sc.)
Abgabedatum: 01.02.2012

Der Schönhage-Strassen-Algorithmus ist ein 1971 vorgestellter schneller Algorithmus zur Multiplikation von großen natürlichen Zahlen. Es wird zunächst die Funktionsweise des Algorithmus und anschließend eine Implementierung des Algorithmus in C vorgestellt. Weiterhin wird die Möglichkeit aufgezeigt, den Algorithmus durch massiv parallele Ausführung einiger Teilabschnitte zu beschleunigen. Die parallelen Berechnungen werden auf die Grafikkarte ausgelagert und erfolgen mit Hilfe der NVIDIA-Architektur CUDA. Durch Einsatz von Laufzeittests und Profiling-Tools werden abschließend die Ergebnisse evaluiert.

Buntrock, Lydia: Schnittgraphen geometrischer Objekte - Intersection Graphs of geometric objects

Betreuer: Prof. Dr. Helmut Alt
Abschluss: Bachelor of Science (B.Sc.)
Abgabedatum: 14.10.2014

Die Schnittgraphen geometrischer Objekte sind ein interessanter Bestandteil der Graphentheorie, da sie eine Verbindung zur Geometrie schlagen und außerdem ein weitreichendes Feld an Anwendung, zum Beispiel in Genetik und Elektrotechnik, bieten.

Ein Schnittgraph (engl. intersection graph) ist ein Graph, der die Gestalt von Schnittpunkten einer Familie von Mengen darstellt. Wir betrachten Familien geometrischer Objekte in der Ebene und ordnen jeder Menge, das heißt jedem Objekt, einen Knoten zu und beschreiben eine Kante genau dann, wenn sich die betreffenden geometrischen Objekte berühren oder überlagern. Daher kann man Schnitt- graphen in das Feld der geometrischen Graphentheorie einordnen.

Wenn man beliebige Mengen zulässt, kann jeder Graph als Schnittgraph dargestellt werden. Betrachtet man jedoch Mengen bestimmter Kategorien, gibt es zu einigen Graphen keine Mengenfamilie in dieser Kategorie, welche den Graphen als Schnittgraphen hervorbringen. Diese Graphen müssen somit bezüglich dieser Kategorie bestimmte Eigenschaften erfüllen. Wir betrachten in dieser Arbeit Mengen von Intervallen, Kurven, Strecken und Kreisscheiben als geometrische Objekte.

Wir befassen uns in dieser Arbeit besonders mit den folgenden Fragestellungen bezüglich unseren geometrischen Objekten:

Wann ist ein gegebener Graph ein Schnittgraph beziehungsweise wie ist er charakterisiert?

Ist ein Graph ein Schnittgraph einer Art von geometrischen Objekten? Können wir einen Algorithmus angeben, um die Realisierung zu einem Schnittgraphen zu geben? Welche Laufzeit hat dieser?

Welche besonderen Eigenschaften haben die Schnittgraphen zu den gegebenen Objekten?

Soroceanu, Tudor: Implementierung eines Approximations-Algorithmus für die Berechnung der diskreten Fréchet-Metrik

Betreuer: Prof. Dr. Wolfgang Mulzer
Abschluss: Bachelor of Science (B.Sc.)
Abgabedatum: 19.05.2015

Die Fréchet-Metrik ist ein weit verbreitetes und gut untersuchtes Maß zur Bestimmung der Ähnlichkeit zwischen Kurven. Es gibt mehrere Varianten dieser Metrik; der Schwerpunkt der Bachelorarbeit liegt auf der diskreten Fréchet-Metrik, welche die Eckpunkte von Polygonzügen betrachtet. Der initiale Algorithmus von Eiter und Mannila [1] hat eine Laufzeit von O(n^2). Erst kürzlich konnten leicht subquadratische Algorithmen dafür gefunden werden. Jedoch hat Bringmann [2] gezeigt, dass es unmöglich ist, für das Problem eine Lösung mit stark subquadratischer Laufzeit O(n^(2-e)), für ein konstantes e > 0, zu finden. Daraufhin sind Bringmann und Mulzer [3] der Frage nachgegangen, wie gut sich die Fréchet-Metrik approximieren lässt und haben zwei Approximationsalgorithmen dazu vorgestellt: Einen gierigen Algorithmus mit linearer Laufzeit, der eine Approximationsschranke von 2^O(n) hat und einen allgemeinen alpha-approximativen Algorithmus, der O(n \log n + (n^2) / alpha) Zeit benötigt, für jedes 1 <= alpha <= n. Im Rahmen der Bachelorarbeit wurden diese beiden Algorithmen und zwei Referenzalgorithmen implementiert und experimentell untersucht. Die Ergebnisse des gierigen Algorithmus sind weitaus besser, als es die Schranke von 2^O(n) vermuten lässt. Die Implementierung des alpha-Approximationsalgorithmus konnte in den Experimenten die gute theoretische Laufzeit jedoch nicht bestätigen. 

Bartkowiak, István: Statistische Analyse der Knotengrade zufälliger Triangulierungen

Betreuer: Prof. Dr. Günter Rote
Abschluss: Bachelor of Science (B.Sc.)
Abgabedatum: 07.05.2013

Im Rahmen der Bachelorarbeit wurde die statistische Verteilung der Knotengrade bei zufälligen Triangulierungen untersucht. Als Triangulationsverfahren werden neben einem universellen Greedy-Verfahren auch die Delaunay-Triangulierung und das zufällige Kantenkippen auf einer beliebigen Triangulierung einer gegebenen Knotenmenge V verwendet. Das hierzu entwickelte Java-Werkzeug wird ebenfalls vorgestellt. 

Keidel, Luca: Packen von Polygonen mit Hilfe von Metaheuristiken

Betreuer: Prof. Dr. Helmut Alt
Abschluss: Bachelor of Science (B.Sc.)
Abgabedatum: 21.07.2015

Die Klasse der Packungs- und Zuschnittsprobleme umfasst eine Vielzahl diverser
praktischer und theoretischer Problemstellungen, aus der in dieser Arbeit das
zweidimensionale nesting problem betrachtet wird. Das nesting problem ist ein
Optimierungsproblem, bei dem die Problemstellung darin besteht, die Anordnung
mehrerer geometrischer Objekte so zu optimieren, dass der Platz optimal ausgenutzt
wird.

Bei den zu packenden Objekten handelt es sich in dieser Arbeit um einfache und
lochfreie Polygone, d.h. Polygone, deren Kanten sich jeweils untereinander nicht
schneiden dürfen. Die Anordnung der Polygone wird dahingehend optimiert, dass die
Ausnutzung der Fläche der achsenparallelen Bounding Box maximiert bzw. der Verschnitt
in Bezug auf ebendiese minimiert wird.

Da es sich bei dem nesting problem um ein NP-schweres Optimierungsproblem handelt,
ist bis dato kein effizienter Algorithmus bekannt, der in der Lage ist, eine optimale
Lösung für das Problem zu erzeugen. Daher wird eine Lösung mittels Metaheuristiken
approximiert, bei denen es sich um problemunabhängige abstrakte Verfahren zur Erzeugung
von heuristischen Optimierungsalgorithmen handelt.

In der Arbeit werden die Metaheuristiken Simulated Annealing und genetische Algorithmen
verwendet. Es werden verschiedene Ansätze zur Anwendung der beiden Metaheuristiken auf das
nesting problem vorgestellt und implementiert. Anhand eines Schnittmusters für T-Shirts aus
der Praxis und weiteren Probleminstanzen, wie Legepuzzles, werden die Ansätze getestet und
die Ergebnisse ausgewertet.

Die erzielten Ergebnisse der verschiedenen Ansätze unterscheiden sich teilweise deutlich in
ihrer Qualität. Insgesamt werden mit den Ansätzen gute, allerdings entsprechend der
heuristischen Natur der Verfahren, nicht optimale Ergebnisse erzielt. 

Haimberger, Terese: Theoretische und Experimentelle Untersuchung von Kuckucks-Hashing

Betreuer: Prof. Dr. Wolfgang Mulzer
Abschluss: Bachelor of Science (B.Sc.)
Abgabedatum: 29.01.2013

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.

Kauer, Alexander: Implementation of and Experiments on Centerpoint Approximation Algorithms

Betreuer: Prof. Dr. Wolfgang Mulzer
Abschluss: Bachelor of Science (B.Sc.)
Abgabedatum: 17.02.2015

Der eindimensionale Median ist einer der grundlegenden Bestandteile der Informatik und Mathematik. Die Idee des Medians kann auf höhere Dimensionen als Centerpoint verallgemeinert werden. Hierbei zerlegen alle Hyperebenen durch einen Centerpoint die Eingabe in zwei etwa gleich große Teile.

Der bisher schnellste Algorithmus um einen Centerpoint für n Punkte in d Dimensionen zu finden hat eine erwartete Laufzeit von O(n^(d - 1)). Durch die in d exponentielle Laufzeit ist dieser Algorithmus nur für kleinere Dimensionen sinnvoll anwendbar. Es ist kein Algorithmus bekannt um einen Centerpoint in polynomieller Laufzeit bezüglich sowohl n als auch beliebiger Dimension d zu finden. Aus diesem Grund sind vor allem approximative Algorithmen für dieses Themengebiet von großem Interesse.

In dieser Arbeit werden mehrere approximative Algorithmen für eine beliebige Anzahl an Dimensionen vorgestellt. Diese Algorithmen haben ein bezüglich Anzahl der Punkte n und der Dimension d polynomielles Laufzeitverhalten. Weiterhin wurden diese Algorithmen implementiert und deren durchschnittliche Güte bei zufälliger Eingabe ermittelt, da die Algorithmen nur eine untere Schranke der Güte des Ergebnisses garantieren.

Herter, Felix: On the Size of Simultaneous Geometric Embeddings for a Tree and a Matching

Betreuer: Klaus Kriegel
Abschluss: Bachelor of Science (B.Sc.)
Abgabedatum: 11.02.2014

Given k planar graphs on a shared vertex set V , simultaneous geometric embedding (SGE) is the problem of finding an embedding of V into the plane such that none of the k graphs intersects itself when edges are drawn as straight line segments. Several positive results, i.e., graphs that always admit an SGE, as well as negative results are known today.

In this thesis, we analyse the size of drawings obtained by two algorithms from Cabello et al. [1]. The first creates an SGE for a wheel and a cycle. We show that an O(n^2) x O(n^2) integer grid suffices to support the resulting drawing. The second creates an SGE for a tree and a matching.

Here, we show that there exist graphs such that a grid with more than singly exponential size is needed if one uses the original algorithm. Afterwards an improvement is suggested so that singly exponential size suffices. Furthermore, we prove that a wheel and the union of two matchings always admit an SGE. In contrast to that, we give two wheels on the same six vertices such that each planar embedding of one forces the other into intersecting itself.

Tigges, Johannes: Dissecting DOS 1.x. Details Beyond the Known Historical Parts

Betreuer: Prof. Dr. Wolfgang Mulzer
Abgabedatum: 02.02.2016

IBM/MS/PC-DOS war weltweit auf Millionen von Computern für mehrere Jahrzehnte in Betrieb. Während dieser Zeit hat es die Benutzung von Computern durch Menschen stark beeinflusst, z.B. durch die 8+3 Namenskonvention für Dateinamen.
Mittlerweile wurde DOS größtenteils durch andere Betriebssysteme ersetzt. Sein Nachlass jedoch, darunter das Dateisystem FAT, ist noch sehr verbreitet. Es kann unter anderem in den Standards bekannter Hardware oder Software die viele Menschen täglich benutzen gefunden werden, z.B. SD-Karten, Smartphones oder Digitalkameras.
2014 hat das Computer History Museum (CHM) ein Archiv mit dem Quellcode der ersten beiden Versionen von DOS veröffentlicht.
Dies erlaubt es erstmals genau zu studieren, wie dieses einflussreiche Stück Software bestimmte Funktionalität umsetzt und warum es bestimmte Limitationen aufweist.

Diese Arbeit untersucht den Quellcode aus dem veröffentlichten Archiv, um zu diesem Ziel beizutragen. Es werden wenig bekannte Details zum Bootprozess des IBM PC und seiner Nachfolger, die bis zum heutigen Tag verkauft werden, präsentiert. Des weiteren werden beachtenswerte Merkmale der ersten FAT-Implementierung in DOS genauer untersucht. Die daraus gewonnenen Erkenntnisse werden hinsichtlich ihres Einflusses auf aktuelle Systeme evaluiert.

Um dies zu erreichen werden die Inhalte des vom CHM veröffentlichten Archivs zunächst in ihren Zusammenhang gesetzt was das Hardware- und das historische Umfeld angeht. Anschließend werden Auszüge des Quellcodes präsentiert und detailliert diskutiert, um dem Leser ein detaillierteres Verständnis der prägenden Konzepte von DOS zu ermöglichen.

Die Geschichte von DOS und die weite Verbreitung und Annahme seiner Konzepte dienen als erstklassiges Beispiel dafür, wie ein Prototyp, seine erwartete Lebensdauer um Jahrzehnte überschritten hat und dadurch die Nutzung von Computern durch Endanwender und Systemprogrammierer für Jahrzehnte geprägt hat.
Auch wenn DOS 1.x und 2.x tatsächlich eine sehr begrenzte Lebensdauer hatten, wurden die dort enthaltenen Konzepte und Design-Entscheidungen in ihren Nachfolgern übernommen ohne diese für das neue Einsatzgebiet erneut zu evaluieren.
Dadurch kam es zu einem de-facto Standard, der bestimmte Gebiete bis heute beeinflusst. 

Willert, Max: Schranken für eine orthogonale Variante des Chromatischen Art Gallery Problems

Betreuer: Klaus Kriegel
Abschluss: Bachelor of Science (B.Sc.)
Abgabedatum: 09.12.2014

In der Arbeit wird das Problem betrachtet, wie man ein einfaches orthogonales Polygon P mit einer endlichen Wächtermenge abdecken kann, bei der jeder Wächter eine von k Farben zugeordnet bekommt. Diese zugehörige Färbung der Wächter heißt konfliktfrei, falls jeder Punkt p in P wenigstens einen Wächter sieht, der einzigartig gefärbt ist unter allen Wächtern, die von p aus sichtbar sind. Für die Anzahl der benötigten Farben konnte eine O(loglog n)-Schranke, sowie eine Omega(loglog n/logloglog n)-Schranke nachgewiesen werden (wobei n die Anzahl der Eckpunkte von P ist). Dabei gingen wir von der r-Sichtbarkeit aus, d.h. dass sich zwei Punkte genau dann sehen, wenn ihr aufgespanntes achsenparalleles Rechteck innerhalb des Polygons liegt. Bei der starken Version unseres Färbungsproblems - das heißt alle Wächter, die von einem Punkt aus gesehen werden, müssen unterschiedliche Farben haben - konnte sogar eine Theta(log n)-Schranke nachgewiesen werden.

Nührenberg, Georg: Algorithmen für das Containment Problem in 2 und 3 Dimensionen

Betreuer: Prof. Dr. Helmut Alt
Abschluss: Bachelor of Science (B.Sc.)
Abgabedatum: 05.08.2014

In dieser Arbeit wird das Problem untersucht, ob ein Polygon in ein anderes hineinpasst, bzw. ein Polyeder in einen anderen Polyeder. Das Ziel ist dieses “Containment Problem” mit linearer Programmierung zu lösen. Dabei werden verschiedene Varianten des Problems betrachtet und Lösungen vorgestellt. Zu Beginn ist nur eine Translation erlaubt, um das eine Objekt in das andere hinein zu verschieben. Später kann dafür zusätzlich zur Translation auch eine Rotation verwendet werden. Um den Drehwinkel der Rotation mit linearer Programmierung zu betrachten werden zwei Lösungsansätze untersucht. Als erster Ansatz wird eine bestimmte Anzahl von Winkeln diskretisiert. Für zwei Dimensionen wird zusätzlich der zweite Lösungsansatz verwendet, bei dem eine Bedingung für den Drehwinkel linearisiert wird.

Ein weiterer wesentlicher Bestandteil dieser Arbeit war die Implementierung der herausgearbeiteten Algorithmen. Bedienung und Funktionsweise des geschaffenen Programmes werden als Teil der Arbeit erläutert.

Sähn, Marcus: Implementierung einer Datenstruktur für den dynamischen Zusammenhang für allgemeine und Unit Disk Graphen

Betreuer: Prof. Dr. Wolfgang Mulzer
Abschluss: Bachelor of Science (B.Sc.)
Abgabedatum: 05.04.2016

Graphen werden häufig genutzt, um Beziehungen zwischen Objekten zu modellieren. Ein bekanntes Beispiel ist das von Milgram beschriebene Kleine-Welt-Phänomen. Dabei geht es unter anderem um die Frage, ob sich zwei zufällig ausgewählte Personen (über weitere Personen) kennen. Im Modell werden Personen als Knoten und Bekanntschaften als Kanten des Graphen dargestellt. Eine Bekanntschaft zwischen zwei Personen besteht, wenn sich die entsprechenden Knoten in der gleichen Zusammenhangskomponente befinden.


Mit wachsender Komplexität der Modelle und häufigeren Änderungen am Graphen rückten dynamische Datenstrukturen vermehrt in den Fokus. Wenn diese Datenstrukturen zusätzlich Zusammenhangsanfragen schnell beantworten können, unterstützen sie den so genannten dynamischen Zusammenhang (dynamic connectivity).


In dieser Arbeit werden zwei Datenstrukturen für den dynamischen Zusammenhang vorgestellt und implementiert. Eine unterstützt allgemeine Graphen, die andere Unit Disk Graphen. Die Laufzeiten beider Datenstrukturen betragen für eine Graphveränderung amortisiert O(log 2 n) und für eine Zusammenhangsanfrage amortisiert O(log n). Für die Auswertung werden beide Datenstrukturen mit simulierten Daten getestet und mit naiven Ansätzen verglichen. Zur Anschauung und zum besseren Verständnis wurden Visualisierungen für Unit Disk Graphen und für die untere Kontur (lower envelope) entwickelt und implementiert.

Pockrandt, Christopher: Planarity Testing via PQ-Trees: Then and Now

Betreuer: Prof. Dr. Wolfgang Mulzer
Abschluss: Bachelor of Science (B.Sc.)
Abgabedatum: 19.09.2013

Graphen, die sich in die Ebene zeichnen lassen, ohne dass sich ihre Kanten schneiden, heißen planare Graphen. Sie spielen in der Informatik eine wichtige Rolle: einige algorithmische Probleme lassen sich auf planaren Graphen effizienter als auf allgemeinen lösen, wie zum Beispiel dem Finden von kürzesten Wegen oder dem Bestimmen von maximalen Flüssen. Es gibt eine Vielzahl von Algorithmen, die in linearer Zeit entscheiden, ob ein Graph planar ist und gegebenenfalls eine Einbettung in die Ebene finden. Ein grundlegender Meilenstein hierfür war der Algorithmus von Booth und Lueker, der auf einer neuen Datenstruktur namens PQ-Bäumen basiert. Es wurden immer einfachere Algorithmen vorgestellt, die einen anderen Ansatz verfolgten oder die Datenstruktur modifizierten. Diese Arbeit stellt neben den PQ-Bäumen zwei dieser Algorithmen vor: den Algorithmus von Booth und Lueker (1976), sowie einen neuen, einfacheren Algorithmus von Häupler und Tarjan (2008), der PQ-Bäume auf eine andere Weise benutzt.

Tippenhauer, Simon: Algorithmen zum effizienten Packen und Stapeln von geometrischen Objekten

Betreuer: Prof. Dr. Helmut Alt
Abgabedatum: 01.11.2012

In der vorliegenden Arbeit werden Algorithmen zum effizienten Packen und Stapeln von geometrischen Objekten untersucht und entwickelt. Beim Packen von Objekten soll eine möglichst kompakte Anordnung gefunden werden, sodass alle Objekte disjunkt sind. Im Gegensatz dazu dürfen die Objekte beim Stapeln auch ineinander platziert werden.

Der Schwerpunkt der Arbeit basiert auf den aktuellen Ergebnissen von Arkin et al. für das Stapeln einer Menge von konvexen Polygonen. Sie haben gezeigt, wie die Polygone in polynomieller Zeit so angeordnet werden können, dass der Umfang der konvexen Hülle eine (1+ epsilon)–Approximation bezüglich der konvexen Hülle einer optimalen Anordnung ist.

Darauf aufbauend konnte ein Verfahren für das effiziente Stapeln von dreidimensionalen Polytopen zur Optimierung des Durchmessers der konvexen Hülle entwickelt werden.

Krompass, Daniel: Quake-Heap vs Fibonacci-Heap: Implementierung, Untersuchung, Bewertung

Betreuer: Prof. Dr. Wolfgang Mulzer
Abschluss: Bachelor of Science (B.Sc.)
Abgabedatum: 20.06.2013

In den vergangenen Jahren wurden zahlreiche Heapalgorithm vorgestellt, welche unterschiedliche Eigenschaften in Sachen Struktur und Performance für ein breites Spektrum von Anwendungen besitzen. Sie werden vor allem für die Realisierung von Priority-Queues, Clustering- oder Graphalgorithmen eingesetzt. Ersteres werden häufig von Schedulern in Servern oder Betriebssystemen verwendet. 2009 stellte [5] die Theorie zu Quake-Heap, einer effizienten Alternative zum vielfach implementierten und untersuchten Fibonacci-Heap, vor. Dieser Algorithmus, so die Behauptung des Autors, soll vor allem durch seine Einfachheit einen pädagogischen mehrwert liefern.

In dieser Arbeit wurde der Quake Heap erstmals implementiert und in zweierlei Hinsicht untersucht. Laufzeitmessungen des Dijkstra Algorithmus auf randomisierten Graphen haben ergeben, dass der Quake-Heap auf der Grundlage mehrerer Messreihen durchschnittlich bessere Werte liefert als der Fibonacci-Heap, was eine praktische Rechtfertigung dieser Datenstruktur liefert. Ebenfalls ließ sich die Datenstruktur
des Quake-Heaps auf Grund der Vermeidung von doppelt verketteten, zyklischen Listen wie sie im Fibonacci-Heap verwendet werden, einfacher implementieren, was für einen höheren pädagogischen Mehrwert spricht.

Klost, Katharina: Details on the Integer Sorting Algorithm by Han and Thorup Using O(n sqrt(loglog n)) Time and Linear Space

Betreuer: Prof. Dr. Wolfgang Mulzer
Abschluss: Bachelor of Science (B.Sc.)
Abgabedatum: 15.01.2015

Sortieren ist eines der grundlegenden Probleme in der Informatik. Die Zeitkomplexität für vergleichsbasiertes Sortieren ist bekanntermaßen Theta(n log n). Wenn nun die Eingaben auf Integer beschränkt werden und eine RAM mit einer beschränkten und von der Eingabegröße abhängigen Wortlänge als Modell für die Komplexitätsanalyse gewählt wird, kann diese Schranke unterschritten werden. Die Beschränkung der Wortlänge ist notwendig um reale Einschränkungen abbilden zu können. Die Frage ob mit diesen Vorraussetzungen in linearer Zeit sortiert werden kann ist noch offen.
Der in der Arbeit vorgestellte Algorithmus von Han und Thorup kombiniert bekannte Algorithmen für die Sortierung von Integern mit einem neuen Algorithmus der eine Eingabemenge in kleinere Mengen auf denen eine gewisse Ordnung definiert ist aufteilt. Somit wird eine Komplexität von O(n sqrt(log log n)) für das randomisierte Sortieren beliebig langer Integer erreicht. 

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

Betreuer: Prof. Dr. Wolfgang Mulzer
Abschluss: Bachelor of Science (B.Sc.)
Abgabedatum: 05.02.2015

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.

Wesolek, Piotr: Reduzierung geometrischer Gebäudedaten für die Simulation des Wärmeverlustes

Betreuer: Prof. Dr. Günter Rote
Abschluss: Bachelor of Science (B.Sc.)
Abgabedatum: 18.08.2016

Diese Bachelorarbeit nimmt sich der Problematik an die geometrischen Eigenschaften von Gebäuden zu vereinfachen. Die Ergebnisse der Vereinfachungen werden durch eine Simulation der auftretenden Sonnenenergie evaluiert. Dazu wurde ein Tool geschrieben mit welchem sich die Vereinfachungen und Simulationen durchführen lassen und welches erlaubt eine Visualisierung der Simulation und Gebäude-Vereinfachungen in OpenGL durchzuführen.

Kresse, Antonia: Effiziente Berechnung von letzten gemeinsamen Vorfahren und Anwendungen

Betreuer: Frank Hoffmann
Abschluss: Bachelor of Science (B.Sc.)
Abgabedatum: 01.01.2011

Schmidt, Florian: Heuristiken zum effizienten Stapeln und Packen von konvexen Polygonen

Betreuer: Prof. Dr. Helmut Alt
Abschluss: Bachelor of Science (B.Sc.)
Abgabedatum: 01.01.2011

Bach, Alexander: Balancing in kompetitiven Spielumgebungen

Betreuer: Prof. Dr. Helmut Alt
Abschluss: Bachelor of Science (B.Sc.)
Abgabedatum: 01.01.2011

Kassem, Yussuf: Approximation von Kreispackungen

Betreuer: Prof. Dr. Helmut Alt
Abschluss: Bachelor of Science (B.Sc.)
Abgabedatum: 15.02.2016

Ich habe mich mit der Approximation einer minimalen rechteckigen Packung für Kreise beliebiger Größe beschäftigt. 

Die Approximation basiert auf einen Algorithmus von Prof. Helmut Alt, Prof. Mark de Berg und Prof. Christian Knauer, welcher für die Approximation von rechteckigen minimalen Packungen konvexer Polygone entwickelt wurde. Das Ergebnis der Anwendung auf Kreise ist ein Approximationsfaktor von 9,049 in linearer Laufzeit. Der besagte Algorithmus kann auch für die Approximation einer konvexen Packung verwendet werden. Diese Möglichkeit wird für die Anwendung auf Kreisen untersucht.

Lüke, Kai: Design of a Python-subset Compiler in Rust targeting ZPAQL

Betreuer: Prof. Dr. Günter Rote
Abschluss: Bachelor of Science (B.Sc.)
Abgabedatum: 30.09.2016

The compressed data container format ZPAQ embeds decompression algorithms as ZPAQL bytecode in the archive. This work contributes a Python-subset compiler written in Rust for the assembly language ZPAQL, discusses design decisions and improvements. On the way it explains ZPAQ and some theoretical and practical properties of context mixing compression by the example of compressing digits of π. As use cases for the compiler it shows a lossless compression algorithm for PNM image data, a LZ77 variant ported to Python from ZPAQL to measure compiler overhead and as most complex case a implementation of the Brotli algorithm. It aims to make the development of algorithms for ZPAQ more accessible and leverage the discussion whether the current specification limits the suitability of ZPAQ as an universal standard for compressed archives.

Feist, Tom Morris: Bestimmung von Schnittpunkten in periodischen topologischen Graphen auf dem Zylinder

Betreuer: Prof. Dr. Günter Rote
Abschluss: Bachelor of Science (B.Sc.)
Abgabedatum: 30.10.2015

Ein topologischer Graph ist die Projektion eines Graphen auf eine Oberfläche, so dass jeder Knoten auf einen eindeutigen Punkt und jede Kante auf eine einfache Kurve auf der Oberfläche abgebildet wird. Es wird ein Algorithmus gegeben, um für eine Menge von bis auf Homeomorphie der Kurven äquivalenten topologischen Graphen auf dem Zylinder die minimale Menge an erforderlichenSchnittpunkten zwischen den jeweiligen Kurven zu bestimmen.

Scharf, Nadja: Theoretische Betrachtung von B+-Bäumen mit vereinfachter Löschoperation

Betreuer: Prof. Dr. Wolfgang Mulzer
Abschluss: Bachelor of Science (B.Sc.)
Abgabedatum: 08.03.2013
Homepage des Autors:

In der von mir vorgestellten Arbeit werden B- -Bäume theoretisch untersucht. B- -Bäume sind B+ -Bäume mit dahingehend vereinfachter Löschoperation, dass unterbesetzte Knoten zugelassen sind. Dadurch können die Bäume aber entarten, das heißt sie sind nicht mehr balanciert und ihre Höhe ist nicht mehr logarithmisch in der Anzahl der gespeicherten Elemente.

Um trotzdem die von B+ -Bäumen gewohnten Schranken in Bezug auf Platzverbrauch und Höhe zu garantieren, müssen die Bäume regelmäßig neu gebaut werden. Im wesentlichen basiert diese Arbeit auf den Ergebnissen von Sen und Tarjan in "Deletion Without Rebalancing in Multiway Search Trees".

Kassem, Mahmoud: Über das planare Morphing zwischen Zeichnungen planarer Graphen

Betreuer: Frank Hoffmann
Abschluss: Bachelor of Science (B.Sc.)
Abgabedatum: 27.02.2015

Ein planares Morphing ist eine stetige Transformation zwischen topologisch äquivalenten straight-line-Zeichnungen Z_s und Z_t desselben planaren Graphen G. Ein solches Morphing kann z.B durch eine Sequenz von linearen Morphingschritten angegeben werden, dabei bewegt sich jeder Knoten in jedem Schritt mit konstanter Geschwindigkeit auf einer Geraden und zu jedem Zeitpunkt liegt eine topologisch äquivalente Zeichnung vor. Die Komplexität des Morphings ist dabei die Länge dieser Sequenz, also die Anzahl der linearen Morphingschritte. In einer Arbeit aus dem Jahre 2014 haben Angelini et al. gezeigt, dass für einen gegebenen planaren Graphen G und topologisch äquivalenten straight-line-Zeichnungen Z_s und Z_t eine Morphingsequenz existiert, deren Länge in O(n) liegt, wobei n die Anzahl der Knoten des Graphen ist. Auf der anderen Seite existieren Zeichnungen ein und desselben planaren Graphen auf n Knoten, sodass jede lineare Morphingsequenz Ω(n) Schritte benötigt. Die Bachelorarbeit entwickelt zunächst die Grundlagen und präsentiert dann die wesentlichen Ideen der Arbeit.

Gottwald, Robert L.: Approximation Algorithms for Interval Scheduling Problems with Given Machines

Betreuer: Prof. Dr. Wolfgang Mulzer
Abgabedatum: 21.02.2014

Most interesting discrete optimization problems are NP-hard and thus the
existence of algorithms that find optimal solutions efficiently is very
unlikely for these problems. One approach to encounter this is to design
efficient algorithms that find approximate solutions. In this thesis two NP-
hard interval scheduling problems are studied. In both the goal is to schedule
a set of intervals on given machines such that intervals scheduled on the same
machine do not overlap. Additionally, the machines have a capacity constraint
in one of the variants, while in the other one an interval can be restricted
to a subset of the machines. They fall into a class of problems called
separable assignment problems, for which a framework to obtain approximation
algorithms, whose guarantees depend on the problem for a single machine,
exists.
On the basis of this framework I will describe a local search approximation
algorithm and one using linear programming with randomized rounding for both
problems.      

Hinze, Nico: Darstellung und Vergleich von Beweisen für planare Separatoren

Betreuer: Prof. Dr. Wolfgang Mulzer
Abschluss: Bachelor of Science (B.Sc.)
Abgabedatum: 28.08.2015

„Divide-and-conquer“ erweist sich als effektive Methode algorithmische und
kombinatorische Probleme in der Informatik zu lösen. Die Idee hinter diesem
Ansatz ist es, das ursprüngliche Problem in einfachere Teilprobleme zu
zergliedern, welche, nachdem sie gelöst wurden, wieder zum Ausgangsproblem
zusammengesetzt werden. Um diesen Ansatz auf planare Graphen anwenden zu können,
werden planare Separatoren benötigt, die die Graphen in mehrere Komponenten
zerlegen. Ziel der vorliegenden Arbeit ist es, verschiedene Beweise für planare
Separatoren eingehender zu untersuchen und einen Überblick über die
verschiedenen Beweise zu geben. Zu diesem Zweck werden zunächst die wichtigsten
theoretischen Begriffe vorgestellt. Aufbauend auf den theoretischen Grundlagen
werden vier ausgewählte Beweise für planare Separatoren vorgestellt. Dabei
handelt es sich um die Beweise von Lipton und Tarjan, Goodrich, Gazit und Miller
sowie Spielman und Teng. Sie werden im Detail untersucht, um sie anhand der
hieraus gewonnenen Erkenntnisse zu vergleichen und in einer Rangliste zu
bewerten. Der Beweis von Spielman und Teng überzeugt durch die kurze Darstellung
und die Verknüpfung von Graphentheorie und Geometrie. Der grundlegende Beweis
von Lipton und Tarjan belegt den zweiten Platz, weil er am einfachsten
nachzuvollziehen ist. Der Ansatz von Goodrich folgt auf Platz drei, da die
zusätzlich benötigten Datenstrukturen den Beweis komplizierter gestalten. Die
Herangehensweise von Gazit und Miller belegt den letzten Platz durch ihre
hohe Komplexität.