Abschlussarbeiten

Nachfolgend finden Sie Themen-Vorschläge für Bachelor- und Masterarbeiten aus den Themenkomplexen Compilerbau und Constraint-Programmierung. Die formulierten Aufgaben sind mit dem entsprechenden Niveau (Bachelor oder Master) gekennzeichnet (und können in Abwandlung oder Ergänzung manchmal auch für das jeweils andere Niveau angepasst werden).

In Absprache können wir Ihnen weitere Aufgabenstellungen z.B. aus den Bereichen des maschinellen Lernens, der Anwendung von Sensorik/Aktuatorik/Robotik oder der modellbasierten Software-Entwicklung anbieten.

Haben Sie Interesse an einer der nachfolgenden Aufgabenstellung, den o.g. oder einem verwandten Thema?
Dann sprechen Sie uns bitte an!

1) Themenkomplex: Der gläserne Compiler

Um Studierenden das Verständnis von Übersetzungstechniken im Rahmen der Lehre zu erleichtern bieten wir verschiedene Themen unter dem Schwerpunkt "Der gläserne Compiler" an. Alle vorgeschlagenen Themen werden in der Veranstaltung "Compilerbau" (Modulnr. 12350) im Detail vorgestellt und besprochen. Für diese Arbeiten ist es also von Vorteil, wenn die Kandidaten dieses Modul besucht haben.

1a) Syntaktische und Semantische Analyse mit attributierten Grammatiken (Bachelor-/Masterarbeit)

Es soll eine Anwendung entwickelt werden, mit der die Parsierung und semantische Analyse mit Hilfe von Attributgrammatiken visualisiert und erläutert werden kann. Hierbei sollen Attributgrammatiken (AGs) bzw. SDDs (Syntax-directed Definitions) eingegeben werden können und nach oder parallel zur Parsierung semantische Eigenschaften des Programms überprüft werden können. Die Aufgabe kann sowohl für die Top-Down- als auch für die Bottom-Up-Parsierung und mit unterschiedlichen AG-Auswertungsmechanismen umgesetzt werden. Eine schrittweise Auswertung umgesetzt und visuell aufbereitet werden.

1b) Codeerzeugung und -optimierung (Bachelorarbeit)

Ziel dieser Arbeit ist ein Tool zur visuellen Repräsentation der letzten Stufen eines Compilers. Ausgehend von einer internen Repräsentation in Form von abstrakten Syntaxbäumen sollen einfache Methoden zur Codeerezeugung und -optimierung aufbereitet und visualisiert werden.

2) Themenkomplex: Constraint-Programming- und Constraint-Solving-Techniken

Die Constraint-Programmierung ist ein Teilgebiet der künstlichen Intelligenz zur Modellierung und zur Lösung komplexer (NP-vollständiger) Such- und Optimierungsprobleme. In diesem Bereich bieten wir verschiedene Arbeiten zur Entwicklung und Adaption von Lösungsmethoden oder zur Modellierung von CSPs und Anwendung von Lösungstechniken an.

2a) Logistikspielwiese (Bachelorarbeit)

Diese Bachelorarbeit legt die Grundlage für ein größeres Projekt, dessen Ziel es ist, Probleme aus dem Bereich des Operations Research im Rahmen einer Videospielengine zu simulieren und erforschen.

Operations Research betrachtet i.A. mathematische und algorithmische Lösungsansätze für Optimierungprobleme im Wirtschaftsbereich, z.B. Transportprobleme, Dienst- und Belegungsplanungen, oder Zuschnittsprobleme. Das Projekt möchte eine Vielzahl solcher Probleme im Rahmen einer Videospielumgebung simulieren, im Zusammenspiel erproben und erforschen.

Diese Bachelorarbeit soll hierzu Videospielengines vergleichen, um dann in der bestgeeignetsten Engine ein exemplarisches Problem zu implementieren und visualisieren. Hierbei soll die Eignung der Engine für zügiges Prototyping und die Integration externer Tools evaluiert werden.

In diesem Bereich ergeben sich in Zukunft auch weitere Bachelor- und Masterarbeiten

2b) Constraint-basierte Erzeugung von CSPs (Masterarbeit)

Constraint-Programmierung ist ein Programmierparadigma zur deklarativen Beschreibung von komplexen Such- und Optimierungsproblemen. Um Constraint-Solver entwickeln und testen zu können bedarf es vieler Beispielprobleme.
Ziel der Arbeit ist es, einen systematischen Überblick über bestehende Lösungen zu erarbeiten, sinnvolle Kriterien und Maße für CSPs abzuleiten und hierauf basierend eine eigene Methode zu entwickeln und mithilfe von Constraints wiederum Constraint Satisfaction Probleme zu erzeugen.

2c) VCS - Suchbäume (Bachelor-/Masterarbeit)

Der Visual Constraint Solver (VCS) ist ein Tool zur Visualisierung von Constraint-Lösungsprozessen. Er wurde im Rahmen von Abschlussarbeiten am Fachgebiet Programmiersprachen und Compilerbau entwickelt.

In der Constraint-Programmierung können sehr klar und deklarativ komplexe Such- und Optimierungsprobleme beschrieben werden. Der Lösungsprozess wird durch einen sogenannten Constraint-Solver durchgeführt und ist für den Nutzer bei großen Problemen in der Regel nur schwer nachvollziehbar. VCS unterstützt daher durch Interaktivität und Visualisierung das Verständnis des Lösungsprozesses.

Derzeit visualisiert VCS sowohl das ursprüngliche Constraint-Problem als Graphen als auch den Lösungsvorgang in Form eines Suchbaumes. Die Form des Suchbaumes ist dabei abhängig von sogenannten Variablen- und Wertauswahlheuristiken, wobei eine geschickte Wahl einer solchen Heuristik den Lösungsprozess beschleunigen kann. Mittels einer einfachen Sprache können Kriterien für interessante Suchbaumausschnitte formuliert, ausgewertet und in der Visualisierung gekennzeichnet werden.

In dieser Arbeit soll die Komponente zur Suchbaumauswertung und Visualisierung analysiert und erweitert werden. Neben der Erweiterung der Sprache zur Kriterienformulierung um Constraint-basierte
Kriterien- und Baum- bzw. Knotenmengen-Muster soll die gleichzeitige Auswertung mehrerer Suchbäume gleicher oder verschiedener CSPs ermöglicht werden sowie für deren Ergebnisse ein Verfahren zur Evaluation und zum Vergleich von Suchstrategien entwickelt und umgesetzt werden.

2d) Modellierung und Lösung des Ubongo-Spiels als kombiniertes Such- und Constraint-Problem

Knobelspiele und Logikspiele lassen sich oft sowohl als Such- als auch als Constraint-Probleme formulieren. Auch wenn es sich hierbei um Spiele handelt, lassen sich ganz ähnliche Problemstellungen in Planungs- und Optimierungsproblemen von Anwendungen der realen Welt wiederfinden und Lösungsideen und -verfahren auch oft auf reale Probleme überführen.

Im Rahmen dieser Arbeit soll das Spiel Ubongo betrachtet werden.
Es soll zunächst sowohl als Suchproblem als auch als Constraint-Problem modelliert und gelöst werden. Dabei sollen verschiedene Varianten und Implementierungen von informierten und
uninformierten Suchverfahren untersucht werden. Dabei sollen unter
anderem die folgenden Fragen behandelt werden:

  1. Welche Auswirkungen haben verschiedene Suchstrategien (informierte und uninformierte) auf die benötigte Dauer für das Finden einer Lösung im Ubongo-Spiel?
  2. Welche Erkenntnisse aus der Suche können genutzt werden, um die Modellierung und Suchstrategie des Constraint-Problems zu optimieren und schnellere Lösungen zu ermöglichen?
  3. Inwiefern können Erkenntnisse aus dem Constraint-Modell in die Suche überführt werden?

Hieraus sollen hybride Verfahren abgeleitet und umgesetzt werden. Für die Evaluation der entwickelten hybriden Verfahren ist das Erstellen und Durchführen einer ausgiebigen Testreihe notwendig. Dafür muss ein Ubongo-Problemgenerator erstellt werden, der das Generieren erschiedener Muster erlaubt. Im Anschluss daran soll untersucht werden, ob bestimmte Muster mit bestimmten Verfahren besonders schnell gelöst werden können.

Die Arbeit soll zu einer verbesserten Modellierung und Lösung des Ubongo-Spiels als kombiniertes Such- und Constraint-Problem führen. Zudem können die gewonnenen Erkenntnisse zur Optimierung der Constraint-Modellierung beitragen.

3) Themenkomplex: Probleme aus der Praxis

Immer wieder treten Partner an uns heran mit Problemen direkt aus dem Arbeitsleben und dem Forschungsalltag. Diese Themen haben hohe Praxisrelevanz, werden gegen echte Anwendungssituationen evaluiert und finden oft Eingang als reale Problemlösung.

3a) Untersuchung unterschiedlicher Zielfunktionen bei der constraintbasierten Schleusenbelegungsplanung (Bachelor-/Masterarbeit)

Thema der Arbeit ist die Entwicklung, Implementierung und Analyse von Optimierungskriterien und Zielfunktionen für die Planung einer Schleusenbelegung. Die Arbeit erfolgt im Rahmen des vom Bundesverkehrsministerium geförderten Projektes “SchleusenNOK40” und wird in Kooperation zwischen Fraunhofer FOCUS und der BTU CS betreut. Details  Details (ENG)

3b) Quellcodeähnlichkeitserkennung mithilfe Maschinellen Lernens (Masterarbeit)

Die Ähnlichkeit von verschiedenen Quellcodes verlässlich und schnell auf Plagiate prüfen zu können ist nicht nur in der Hochschullehre relevant, sondern stellt auch Complaince-Ableitungen von großen Firmen regelmäßig vor Herausforderungen.

Ziel dieser Arbeit ist die Evaluation des State-of-the-Art im Bereich Quellcodeähnlichkeitserkennung, sowie die Implementierung und Evaluierung eigener Lösungen Lösung mit Techniken des Maschinellen Lernens.

3c) Schüttgutoptimierung (Masterarbeit)

Bei der Schüttgutoptimierung werden kontinuierlich Massengüter, wie z. B. Kohle, Getreide oder Erze angeschichtet, über Förderbänder verteilt und von „Stackern“ aufgehaldet. Die Halden dienen sowohl als Zwischenlager als auch als „Mischbehälter“, die von „Reclaimern“ wieder abgetragen werden. Von dort läuft das Schüttgut über Förderbänder entweder zur erneuten Aufhaldung/Vermischung oder zur Verfrachtung.
Ziel der Schüttgutoptimierung ist die Minimierung der Zeit, die zum Ablegen, Vermischen (Veredeln) und wieder Aufladen der Waren von und auf Züge oder Schiffe, benötigt wird. Durch diese Optimierung kann die Liegezeit der Schiffe und Züge und somit auch die Gebühren dafür reduziert und die Produktivität gesteigert werden.
Zum Erreichen des Optimierungsziels muss geplant werden, wann welche Güter wohin transportiert und gegebenenfalls vermischt werden müssen. Die Planung obliegt dabei Nebenbedingungen, die sich aus dem Aufbau der jeweils konkreten Anlage ergeben. Zum Beispiel können nicht zwei Maschinen zur selben Zeit am selben Ort eingesetzt werden, oder verschiedene Transporte das gleiche Förderband benutzen.

3d) Routenoptimierung unter intermodalem Verkehr (Masterarbeit)

Routen und ihre Optimierung spielen z.B. bei der Car-Navigation oder der Navigation in öffentlichen Verkehrsnetzen eine wichtige Rolle. Als Route wird dabei ein genauer, geordneter Wege über mehrere
Punkte hinweg (für ein Fahrzeug oder eine Person) bezeichnet. Bei der Routenoptimierung sollen somit optimale Wege bzw. Strecken ermittelt werden.  Dabei spielen neben Entfernungen und Fahrzeiten z.B. auch plötzlich auftretende Streckenstörungen oder neu notwendige Zwischenziele, die Umplanungen zur Folge haben können, eine Rolle. Intermodales Routing umfasst die Kombination verschiedener Mobilitätsmodi, wie z.B. Bus, Bahn, Car-Sharing, One-Way-Rental oder Taxi unter dynamischen Bedingungen.

In dieser Arbeit soll Routing und Routing-Verfahren im intermodalen Verkehr untersucht werden. Dazu soll auf der einen Seite eine einfache Anwendung für intermodales Routing aus Nutzersicht entwickelt werden. Auf der anderen Seite soll eine Anwendung zum Monitoring mehrerer/vieler Nutzer und zur Simulation von Verkehrssituationen und Störungen implementiert werden, so dass
verschiedene Nutzer verbunden, statische und dynamische Daten hinzugeladen, und das Verhalten der Nutzer visualisiert werden kann.