Abgeschlossene Bachelorarbeiten

58Abschlussarbeit(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

Becker, Marvin: Attraktorbasierte Überdeckung orthogonaler Polygone

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

In der Bachelorarbeit diskutieren wir die Attraktor-Überdeckung und das Attraktor-Routing in einfachen orthogonalen Polygonen. Diese beiden Probleme sind Varianten des klassischen Art Gallery Theorems. Bei der Attraktor-Überdeckung ist es das Ziel, das Innere eines solchen Polygons mit Attraktoren zu überdecken. Attraktoren ("beacons") sind dabei Punkte innerhalb des Polygons, die, wenn aktiviert, alle anderen Punkte innerhalb des Polygons auf direktem Wege anziehen. Das Attraktor-Routing-Problem beschäftigt sich mit der Frage, wie viele Attraktoren nötig sind, um zwischen zwei beliebigen Punkten innerhalb des Polygons zu routen. Einen Punkt zu einem Zielpunkt zu routen beschreibt dabei den Prozess, diesen Punkt durch sequentielle Aktivierung einer Menge von Attraktoren zu seinem Ziel zu leiten. Zu beiden Fragen werden in der Arbeit die kürzlich von Bae et al. bzw. von Shermer bewiesenen optimalen worst-case-Schranken vorgestellt. Zudem führen wir ein neues, stärkeres Modell des Attraktor-Routings ein und beweisen eine untere Schranke für den worst case.  

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.

Borzechowski, Michaela: The complexity class Polynomial Local Search (PLS) and PLS-complete problems

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

The complexity classes P and NP are well known. However we are often interested in the actual globally optimal solutions of some NP decision problems. Local search is an attempt to approximate a hard to find global optimum with a local optimum. The complexity class Polynomial Local Search (PLS) was introduced to analyze the complexity of local search algorithms, where it is verifiable in polynomial time, whether a solution is a local optimum or not. One can PLS-reduce local search problems to one another and establish PLS-completeness. This work presents the basic definitions of the class PLS, its relation to other complexity classes, PLS-reductions, PLS-completeness, as well as a list of PLS-complete problems. The aim is to give a general overview of this topic and make further proofs for PLS-completeness and further investigations of the characteristics of the class PLS easier.

Brockmann, Christoph: Implementing an Algorithm for Routing in Unit Disk Graphs

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

During this thesis a new routing scheme for Unit Disk Graphs described first in Kaplan et al. (2016) was implemented in Python and tested for performance. In addition, dynamic visualisation of the routing process was implemented through Mathplotlib allowing visual inspection of the routing process.
Although experiments show the routing scheme working as intended,  its routing tables scale unfavourably for most graphs that can be feasibly computed in 2016. It is also shown that for the class of random graphs presented in this thesis, routing results are much better than to be expected from the theoretical worst case considerations in the original paper. Finally, this thesis shows that the results given in the original paper can be improved considerably for smaller graphs if 'one-sided' well separated pair decompositions are used as the basis of the global routing tables.

Haim Kaplan, Wolfgang Mulzer, Liam Roditty, and Paul Seiferth. Routing in unit disk graphs.
In LATIN 2016: Theoretical Informatics - 12th Latin American Symposium, Ensenada, Mexico,
April 11-15, 2016, Proceedings, pages 536–548, 2016.

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. 

Steinmetz, Henning: Implementierung eines Flower Pollination Algorithm zur Minimierung des Fréchet Abstands

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

2012 stellte Xin-She Yang in einem Paper den Flower Pollination Algorithm for Global Optimization vor. Mit diesem konnte Yang in seinem Paper bereits einige mathematische Funktionen approximieren und auch Optimierungsprobleme lösen. In dieser Arbeit soll nun eine weitere Anwendungsmöglichkeit für diesen Algorithmus untersucht werden. Ziel ist es auf Grundlage von Yangs Arbeit einen Algorithmus zu entwickeln und zu implementieren, mit dem eine einfache Variante des Shape-Matching Problems approximiert werden kann. Dabei soll der Fréchet Abstand zwischen zwei Kurven minimiert werden.

Wiener, Felix: Jump Point Search auf verallgemeinerten Spielbrettern

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

Jump Point Search (kurz JPS) ist ein neuer Algorithmus in der Wegfindung. Durch seine herausragenden Performance findet er, vor allem in der Spiele-Entwicklung, viel Anwendung.Leider beschränkt sich die Definition dieses Algorithmus' auf quadratische Gitter.

Meine Arbeit beschäftigte sich mit der Idee, den Anwendungsbereich des JPS zu erweitern.Hierfür abstrahierte und mathematisierte ich sowohl seine Entwicklung, als auch seine Handlungsweise,adaptierte dieses Konzept auf regelmäßige Dreiecks-tesselierte Flächen und arbeitete die Kriterien für eine Verallgemeinerung heraus. Den entstandenen Algorithmus analysierte ich stochastisch und testete ihn gegen den "Jack of all trades"-Pathfinder A*.

Peters, Christoph: Algorithmen für gerade Triangulierungen spezieller planarer Graphen

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

Wir beschäftigen uns mit geraden Triangulierungen von 3-zusammenhängenden planaren Graphen. Dabei heißt eine Triangulierung gerade, falls sie ausschließlich gerade Knotengrade hat. Wir untersuchen zunächst 3-zusammenhängende bipartite planare Graphen und übertragen dann die gewonnenen Erkenntnisse auf sogenannte Mosaike, also 3-zusammenhängende planare Graphen, deren Facetten Dreiecke oder Vierecke sind und auch auf verallgemeinerte Mosaike. Wir geben für jede betrachtete Klasse von Graphen Kriterien an, in wie fern für diese Klasse eine gerade Triangulierung existiert und wie diese gegebenenfalls konstruiert werden kann.

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.

Habib, Julian: Robot Motion Planning Algorithmen und Visualisierung

Betreuer: Claudia Dieckmann
Abschluss: Bachelor of Science (B.Sc.)
Abgabedatum: 16.01.2018

Hartmann, Florian: Computing Graph-Theoretic Similarity Scores Efficiently

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

Similarity measures are useful for many applications, such as recommender systems and search engines. Graph-theoretic similarity measures try to determine similarities by analyzing the relations between objects. SimRank is a popular such similarity measure with an intuitively sensible notion of similarity that is strongly inspired by PageRank. However, SimRank suffers from the fact that the algorithm originally suggested for its computation has an efficiency of Θ(n4). It is not computationally feasible to apply such an algorithm to a large dataset, and hence this thesis explores various alternative algorithms. It is derived how memorizing subresults can improve the efficiency to O(n3). Furthermore, an alternative graph-theoretic similarity measure, called CoSimRank, is discussed. CoSimRank has the advantage that individual similarity scores can be computed in quadratic time. Finally, the performance of the various algorithms introduced is evaluated using data from MovieLens, a collection of large real-world datasets for recommender systems.

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.

Baeten, Miro: Erstellung eines GLL-Parsergenerators für kontextfreie Grammatiken

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

Die Arbeit beschäftigt sich mit der Erstellung eines Parsergenerators für allgemeine kontextfreie Grammatiken unter Verwendung des GLL-Algorithmus, welcher mit ambigen Grammatiken in O(n^3) umzugehen weiß. Sein Einsatz bietet sich unter anderem in der Computerlinguistik, dem Software Reengineering und in Compilern an. Die Laufzeit wird durch die Verwendung von als Graphen strukturierten Stacks (GSS) sowie einem Shared Packed Parse Forest (SPPF) erreicht, der mehrerer valide Ableitungen zusammenfasst. Zunächst wird auf den Algorithmus, danach auf den Generator und die Parser eingegangen. Der Generator abstrahiert die Grammatiken in einem Modell, analysiert dieses und erzeugt daraus einen Parser, der sich an die asymptotische Laufzeit des Algorithmus hält. Damit die Parser ambige Grammatiken schneller ableiten können, wird der Algorithmus um eine Parallelisierung erweitert. Abschließend wird beleuchtet, wie der Parsergenerator in Zukunft ausgebaut werden kann. Bedeutend ist sowohl der weitere Umgang mit den SPPFs als auch die Verbesserung des GSS.

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.

Preyer, Stefan: Verallgemeinerte Catalan-Zahlen und Primzerlegungen von balancierten Klammerausdrücken

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

In der Arbeit haben wir zwei Varianten zur Verallgemeinerung der aus der Kombinatorik bekannten Catalan-Zahlen diskutiert. Zum einen ging es um die von Manuel Wettstein in seinem Artikel „Trapezoidal Diagrams, Upward Triangulations, and Prime Catalan Numbers“ vorgeschlagene Variante, die Catalan-Zahlen als Anzahl balancierter Klammerausdrücke (BKA) zu definieren. Diese hat sich mathematisch als besonders fruchtbar herausgestellt. Das liegt vor allem daran, dass es möglich ist, für die d-dimensionalen Catalan-Zahlen eine geschlossene Formel anzugeben. Für einige Objektklassen haben wir gezeigt, dass sie sich in das Konzept der d-dimensionalen Catalan-Zahlen im Sinne von Wettstein einbetten lassen: bei den Standard-Young-Tableaus benötigten wir dazu noch die schwer zu beweisende Hook-Length-Formel als zusätzliches Hilfsmittel, bei den Gitterwegen und Dyck-Pfaden ergaben sich im d-dimensionalen natürliche Bijektionen.

Andere schon lange bekannte Interpretationen der Catalan-Zahlen passen jedoch nicht dazu. Die Catalan-Zahlen zählen die binären Bäume, jedoch weiß man, dass die Anzahl echter d-närer Bäume nicht den d-dimensionalen Catalan-Zahlen entspricht. Auch die Triangulation von konvexen Polygonen lässt sich nicht so auf höhere Dimensionen verallgemeinern, dass wir wieder die Catalan-Zahlen erhalten.

Wir haben trotzdem eine überraschende Erkenntnis über den Zusammenhang zwischen d-nären Bäumen und den primen BKA, die Wettstein eingeführt hat, gefunden. Nachdem wir nämlich eine Primzerlegung von BKA eingeführt haben und einfache BKA definiert haben, ergab sich die zentrale Erkenntnis, dass es eine Bijektion zwischen der Menge der echten d-nären Bäume und der Menge der einfachen BKA gibt. Außerdem haben wir Bijektionen zwischen zwei Mengen von geschlossenen Dyck-Pfaden und der Menge der primen BKA gefunden.

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

Betreuer: Prof. Dr. Wolfgang Mulzer
Abschluss: Bachelor of Science (B.Sc.)
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
Homepage des Autors:

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.

Berendsohn, Benjamin Aram: Weitere Details zum Integer-Sorting-Algorithmus von Han und Thorup

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

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.

Hofer, Christian: Planar Convex Hull Maintenance with Kinetic Heaps

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

Let a convex set in the plane be given by either a set of points or half-spaces. The maintenance of it under insertion and deletion of elements is a fundamental problem in computational geometry. This thesis considers a data-structure which solves this problem. It was drafted by the researchers Kaplan, Tarjan and Tsioutsiouliklis in a paper about kinetic heaps (priority queues with linear functions as keys rather than fixed values). However it was never written down in detail. We state their construction explicitly. Its foundation is built by a deletion-only structure which uses finger trees (height balanced trees with preferred access points) to represent convex sets. With the semi-dynamic structure at hand, a fully dynamic one may be constructed using given dynamization transformations. The binary counting scheme transformation of Bentley and Saxe yields an insertion-and-deletion structure with O(log2 n) worst-case vertical ray query time, O(log n) amortized insertion time and O(log n log log n) amortized deletion time. A transformation of Brodal and Jacob results in a structure with O(log n) worst-case vertical ray query time, O(log n log log log n) amortized insertion and O(log n log log n) amortized deletion time.

Köhler, Jakob: Optimale Orientierung eines 3D-Modells für den Metalldruck

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

Beim 3D-Druck dient die Stützstruktur der Stabilisierung des Modells während des Druckprozesses. Da die Stützstruktur das Modell von unten abstützt, wirkt sich dessen Orientierung im Raum stark auf das Volumen der notwendigen Stützstruktur aus. Es lässt sich zeigen, dass das Problem der optimalen Orientierung eines 3D-Modells unter diesem Gesichtspunkt in polynomieller Zeit lösbar ist. Desweiteren wird ein approximativer Algoritumus vorgestellt, welcher das Problem für konvexe Modelle in linearer Zeit löst. In modifizierter Form lässt sich der Algorithmus auch auf nicht-konvexe Modelle anwenden, was allerdings in einer quadratischen Laufzeit resultiert. In der Auswertung zeigt sich, dass durch Anwendung des Algorithmus auf bestimmte Modelle signifikante Einsparungen in den Materialkosten erzielt werden können.

Groß, Tobias: Algorithmen und Anwendungen für das Triangle Scheduling Problem

Betreuer: Claudia Dieckmann
Abschluss: Bachelor of Science (B.Sc.)
Abgabedatum: 08.08.2017

Das Triangle Scheduling Problem, von Dürr u.a. in [1] vorgestellt, ist ein Spezialfall von Mixed-criticility Scheduling mit Jobs in Form gleichschenkliger Dreiecke. Da es NP-schwer ist, kann der optimale Zeitplan im Allgemeinen nur mittels Brute-Force-Algorithmus gefunden werden, unter der Annahme P≠NP.

Der effiziente gierige Ansatz, jeweils das größte Dreieck in die größte Lücke im Zeitplan zu setzen, kann in vielen Fällen die optimale Lösung ermitteln, wie quantitative Tests mit gleich verteilt zufälligen Jobgrößen zeigen. An den wenigen Beispielen mit nicht optimalem Ergebnis kann man untersuchen, wann der gierige Algorithmus die falsche Entscheidung trifft.

Darüber hinaus kann mit Hilfe dynamischer Programmierung eine (1+ε)-Approximation des optimalen Zeitplans gefunden werden. Indem die Jobgrößen und Startzeiten vorher aufgerundet werden, reduziert sich die Lösung dabei auf die Lösung von O(n^log(n)) vielen Teilproblemen.

In dieser Arbeit entwerfe ich die drei Algorithmen in Pseudocode und implementiere sie in der Programmiersprache Java.

Außerdem ist das Triangle Scheduling Problem geometrisch betrachtet ein Spezialfall des Packungsproblems in einem Rechteck und ich verallgemeinere den Brute-Force-Algorithmus auf andere Figuren wie gleichseitige Dreiecke, Kreise etc.

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.

Dimitrov, Boris: Complexity of regular expression matching

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

Regular expressions, or regexes for short, are a pattern matching standard for string parsing and replacement. They are widely used computational primitive employed in many programming languages and text processing utilities such as JavaScript, Perl, Python, Ruby, Google RE2. They are also used in computer networks, databases and data mining, computational biology etc. A regular expression consists of symbols from some alphabet ∑ and a set of operators O. We will start by introducing various operators and explain their usage, giving us the basics with the help of which we will be able to construct different types of regular expressions. Then we will show the Thompson transformation, which converts an arbitrary regular expression into an equivalent nondeterministic finite automata, thus providing us with algorithm that solves the regular expression matching problem for the general case in the “rectangular” O(mn) time. Later there were improvements to this method that led to an algorithm that is the fastest for this problem known to date. However there are some specific types of regular expressions, for which faster matching algorithms exist. We will introduce some examples, which are reason to be considered that faster algorithm for the general case might exist. Finally we will classify the regular expressions based on their depth and the used set of operators and present the respective results.

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

Betreuer: Prof. Dr. Helmut Alt
Abschluss: Bachelor of Science (B.Sc.)
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
Homepage des Autors:

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.

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

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

Betreuer: Frank Hoffmann
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

Fisches, Zacharias: Image Sensitivity Assessment with Deep Neural Networks

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

Owing to its speed and simplicity, the peak signal to noise ratio (PSNR) is still one of the most widely used image quality metrics today. In runtime critical applications, such as live-video encoding, using a more sophisticated image quality metric can be prohibitive for encoder mode decisions. Bosse et al. 2017 improved on the PSNR’s mediocre performance by perceptually adapting the PSNR, thereby introducing the notion of distortion sensitivity.

In this work we will expand on the concept of distortion sensitivity and explore the possibilities of estimating distortion sensitivity with a data-driven approach.

Nguyen, Xuan Hoa: Erweiterte Anwendung des Shunting Yard Algorithmus zur Übersetzung von speziellen SQL-Ausdrücken

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

Dijkstra's Shunting Yard Algorithmus (dt. Rangierbahnhof Algorithmus) überführt mathematische Terme von der Infixnotation in die umgekehrte polnische Notation. Der ursprüngliche Shunting Yard Algorithmus ist jedoch nur eine effiziente Methode, um einfache mathematische Terme mit binären Operationen zu konvertieren. Für komplexere Terme, wie z.B. Funktionen mit mehreren Parametern, muss der Algorithmus erweitert werden.

Im Rahmen der Bachelorarbeit soll die Erweiterung zweistufig erfolgen. Die erste Stufe vervollständigt und erweitert die Grundidee des Algorithmus dahingehend, dass weitere mathematische Ausdrücke in umgekehrte polnische Notation überführt werden.

In der zweiten Stufe soll der Algorithmus CASE-WHEN Ausdrücke, die in einer SQL Abfrage auftreten, in abstrakte Syntaxbäume umwandeln. Aus einem abstrakten Syntaxbaum wiederum lässt sich ein Programmcode für semantisch äquivalente Ausdrücke in verschiedenen Programmiersprachen erzeugen.

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.

Blumenbach, Tilman: Untersuchungen zu CP/M

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

Das Mitte der 1970er Jahre veröffentlichte Betriebssystem CP/M stellte zum Zeitpunkt seiner Veröffentlichung das erste hardwareunabhängige Mikrocomputer-Betriebssystem dar und trug maßgeblich zum Entstehen eines von Hardware-Herstellern unabhängigen Software-Marktes bei.

Diese Arbeit untersucht den Aufbau und die Struktur der ersten öffentlich verfügbaren CP/M-Version 1.3, um Einblicke in die interne Funktionsweise von CP/M zu erlangen. Dazu wird zunächst auf die von CP/M genutzte Hardware-Umgebung eingegangen, um anschließend einen detaillierten Einblick in die einzelnen CP/M-Komponenten zu geben. Insbesondere wird auf die Hardwareabstraktionsschicht und das Dateisystem von CP/M eingegangen. Im weiteren Verlauf der Arbeit wird die Architektur von CP/M mit modernen Prinzipien der Betriebssystementwicklung verglichen.

Die Veröffentlichung des IBM-PCs und des MS-DOS-Betriebssystems Anfang der 1980er Jahre führte zum graduellen Niedergang von CP/M. MS-DOS war zu CP/M kompatibel, so dass im Rahmen dieser Arbeit Version 1.x von MS-DOS mit CP/M 1.3 verglichen wird, um etwaige Ähnlichkeiten oder Unterschiede zwischen beiden Systemen festzustellen. Dieser Vergleich ergibt, dass MS-DOS durchaus einige CP/M-Konzepte übernimmt, die Systemarchitektur allerdings in vielen Bereichen verbessert.

Insgesamt zeigt sich im Verlauf dieser Arbeit, dass CP/M 1.3 zwar dank der Hardwareabstraktionsschicht ein portables Betriebssystem darstellt, jedoch auf Grund von Hardware-Limitierungen und teilweise daraus resultierenden Architektur-Schwächen unter Leistungsproblemen zu leiden hat.

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
Abschluss: Bachelor of Science (B.Sc.)
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. 

Wesolek, Michael: Kompression von Englischen Texten unter Verwendung von Lexikalischer Kategorisierung und PPM

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

Die Englische Sprache hat ein starke SPO Struktur. (Subjekt, Prädikat, Object)

Diese Struktur/Redundanz des Satzbaues könnte potenziell zusätzlich genutzt werden um höhere Kompressionsraten zu erhalten. Hierfür wurde ein Kompressionsverfahren entwickelt/erweitert und ausgewertet. Ein Vergleich mit einer PPMC (mit exclusion) Referenz-Implementierung zeigt, dass die Ergebnisse durch das in der Bachelorarbeit vorgestellte Verfahren sich leicht verschlechtert haben. (Vergleich der besten Ergebnisse bei ca. 2000 Datensätzen) Potenzielle Gründe dafür wurden genannt, sodass die Ergebnisse aus dieser Arbeit noch weiter verbessert werden können.