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) Bottom-Up-Parsierung: Grammatikanalyse und Visualisierung von Parsierungstechniken (Bachelor-Arbeit)

Es soll eine Anwendung entwickelt werden, mit der die Bottom-Up-Parsierung visualisiert und erläutert werden kann.

Der Nutzer soll Grammatiken (als Datei oder manuell) sowie zu parsierende Wörter eingeben können.  Die Grammatik wird analysiert und eine Analysetabelle abgeleitet.  Eine schrittweise Parsierung wird umgesetzt und mit allen Elementen (Grammatik, Tabelle, Stack, Eingabeband, etc.) visuell aufbereitet.

1b) Syntaktische und Semantische Analyse mit attributierten Grammatiken (Bachelor-/Master-Arbeit)

Dies ist eine Erweiterung von Thema 1a). Hierbei sollen Attributgrammatiken 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 Bottom-Up- als auch für die Top-Down-Parsierung und mit unterschiedlichen AG-Auswertungsmechanismen umgesetzt werden.

1c) SECD und Auswertungsstrategien (Bachelor-Arbeit)

Ziel ist die Realisierung eines interaktiven, visuellen Interpreters in Form einer SECD-Maschine.

Die SECD-Maschine ist eine virtuelle Maschine zur Interpretation funktionaler Sprachen.  Sie besteht im Wesentlichen aus 4 Stacks (S -Werte-Stack, E - Environment, C - Control, D - Dump) und realisiert zunächst eine call-by-value-Auswertungsstrategie.

In der Arbeit soll eine interaktive SECD-Maschine realisiert werden, die alternativ auch eine call-by-name/need-Auswertungsstrategie zulässt.

1d) Codeerzeugung und -optimierung (Bachelor-Arbeit)

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) Untersuchung und Vergleich von Methoden zur Lösung komplexer Probleme am Beispiel von Knobel- und Suchproblemen (Bachelor-/Master-Arbeit)

In dieser Arbeit sollen verschiedene Methoden zur Lösung komplexer (NP-vollständiger) Knobel- und Suchprobleme untersucht, evaluiert und optimiert werden. Ansätze zur Modellierung und Lösung bietet die Constraint-Programmierung. Probleme werden dort als sog. Constraint-Satisfaction-Probleme (CSPs) beschrieben und gelöst.

Unterschiedliche Modellierungen eines Problems unterscheiden sich aber nicht nur in der Problembeschreibung sondern auch darin, wie schnell eine, eine gute, eine optimale, alle oder eine bestimmte Anzahl von Lösungen für ein Problem gefunden werden können.

Ziel dieser Arbeit ist daher die Untersuchung unterschiedlicher Methoden zur Modellierung und Lösung von CSPs, hierunter die Problemzerlegung, Remodellierung durch redundante oder globale Constraints und die Parallelisierung.

2b) VCS - Suchbäume evaluieren (Bachelor-Arbeit)

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

In der Constraint-Programmierung kann man sehr klar und deklarativ komplexe Such- und Optimierungsprobleme beschreiben. Der Lösungsprozess wird durch einen sog. Constraint-Solver durchgeführt und ist für den Nutzer bei großen Problemen aber oft nur schwer nachvollziehbar. VCS unterstützt daher durch Interaktivität und Visualisierung das Verständnis des Lösungsprozesses.

Bisher viusalisiert VCS sowohl das ursprüngliche Constraint-Problem als Graphen als auch den Lösungsvorgang in Form eines Suchbaumes. Seine Form ist abhängig von sog. Variablen- und Wertauswahlheuristiken, wobei eine geschickte Wahl einer solchen Heuristik den Lösungsprozess beschleunigen kann.  In der Arbeit soll VCS um eine Komponente erweitert werden, die es erlaubt, verschiedene Suchbäume für ein Constraint-Problem gleichzeitig zu visualisieren, zu untersuchen, zu evaluieren und zu vergleichen.

2c) NoGoods und Regular-Constraints (Master-Arbeit)

Das Regular-Constraint ist ein globales Constraint (d.h. ein Constraint über einer Menge von Variablen). Sein Propagator, d.h. der Algorithmus, der die Einhaltung des Constraints sicherstellt und ggf. den Suchraum entsprechend beschneidet, basiert auf der Erzeugung und Anwendung eines deterministischen endlichen Automaten (DFA). Während das Regular-Constraint die zulässigen Lösungstupel erzeugt oder prüft (positive Information), arbeiten sog. Nogoods mit negativer Information, d.h. mit den verbotenen Lösungsvarianten. Je nach CSP kann die eine oder andere Repräsentation kleiner und effektiver sein.

Im Rahmen der Arbeit sollen das Regular-Constraint mit seinem Propagationsalgorithmus und das Konzept der Nogoods vorgestellt und verglichen werden. Es soll sowohl ein Verfahren entworfen werden, das Regular-Constraints automatisch in Nogoods umwandelt als auch eines, welches Nogoods in Regular-Constraints konvertiert. Weiterhin soll analysiert werden und es sollen Kriterien formuliert werden, wann der Einsatz von Nogoods und Regular-Constraints jeweils für eine schnellere Lösungsfindung vorteilhaft sein kann.

2d) Table- vs. Regular-Constraints - Ein Auswahlverfahren basierend auf maschinellem Lernen (Master-Arbeit)

Table und Regular sind zwei globale Constraints, die sich zur Formulierung der gleichen Bedingung eigenen, aber unterschiedliche Propagationsalgorithmen besitzen. Im Rahmen der Arbeit sollen zunächst die beiden Constraints mit ihren Propagationsalgorithmen vorgestellt werden.

Danach soll untersucht werden, ob und in welcher Form sich KI-Verfahren des maschinellen Lernens (z.B. neuronale Netze, Entscheidungsbäume, SVM, Multi-Layer-Perzeptron etc.) eignen können, um aus der Struktur und den Daten eines CSPs zu entscheiden, welches der beiden globalen Constraints für die Lösung dieses CSPs potentiell besser geeignet sein könnte.  Es sollen Kriterien formuliert werden und die Anwendung der Verfahren soll evaluiert werden.

2e) Modellierung von Suchproblemen mit CSPs (Master-Arbeit)

Bei bestimmten Optimierungsproblemen ergibt sich die Bewertung einer Lösung aus der Länge des Lösungswegs von einer gegebenen Startkonfiguration zur Zielkonfiguration. Im Gegensatz zur typischen CSPs, die nach Problemlösungen oder der Exisitenz von Lösungen mit bestimmten Eigenschaften suchen, geht es hier nicht nur um das Finden einer solchen Lösung, sondern auch um das Finden einer Lösung mit minimalem Aufwand. Im Sinne von Suchproblemen und einer globalen Suche wollen wir also die Anzahl der Suchschritte minimieren.

In der Arbeit sollen gegebene Beispielprobleme und Suchalgorithmen analysiert werden mit dem Ziel eine Formulierung der Suchaufgabe als CSP zu finden, die eine optimale (oder lokal optimale) Lösungsstrategie als Ergebnis generiert. Die Berechnung dieser Lösungsstrategie, d.h. die Berechnung einer möglichst kurzen Folge von Lösungsschritten, soll dabei selbst in möglichst kurzer Zeit erfolgen.

Die Lösung über ein CSP soll im Vergleich mit Standard-Lösungsverfahren evaluiert werden.

2f) Visualisierung von Arrays in Constraint Satisfaction-Problemen (CSPs)

Ziel der Arbeit ist die Analyse und Realisierung von Darstellungsmöglichkeiten für Arrays im Rahmen von Constraint Satisfaction Systemen. Umgesetzt werden soll zunächst die Darstellung 1- und 2-dimensionaler Arrays in verschiedenen Detailstufen, die Visualisierung von Constraints über Arrayvariablen und einzelnen Variablen sowie zwischen verschiedenen Arrays, Arrayüberlappungen und von Arraytransformationen. Darstellungsvarianten von mehrdimensionalen Arrays sollten diskutiert werden.