TU BRAUNSCHWEIG

Wenn Sie eine Bachelor-, Master-, Studien-, Projekt- oder Diplomarbeit bei der Theoretischen Informatik machen wollen, sind Sie hier richtig.

Sie können die Mitarbeiter auch direkt zu Themen ansprechen (wenn Sie beispielsweise einen konkreten anderen Themenwunsch haben).


SRM-Baukasten:

Schieberegistermaschinen (SRM'n) spielen in vielen Bereichen der Informatik eine wichtige Rolle, so z.B. auch in der Theorie fehlerkorrigierender Codes.  Sie bilden (endliche) Tupel oder auch (unendliche) Ströme über einem endlichen Körper
auf andere derartige Tupel oder Ströme ab.  Statt von Tupeln oder
Strömen kann man auch von Polynomen und Potenzreihen sprechen.

Ziel ist es, einen virtuellen SRM-Baukasten zu programmieren, der neben elementaren Bauteilen (Schieberegistern, algebraischen Operatoren, Schaltern, Verbindungen, Verzweigungen usw.) auch gewisse Standard-Maschinen bereitstellt (etwa für die Multiplikation mit oder Division durch Polynome, mit oder ohne Rest, oder für die Multiplikation mit gewissen rationalen Funktionen) und es erlaubt, auf
einer graphischen Oberfläche daraus neue Maschinen "zusammenzuklicken".  Diese sollen auch lauffähig sein, damit man die intendierte Arbeitsweise der Maschinen überprüfen kann, auch im single-step Modus.

Als endlicher Körper sollte GF(q) mit q Primzahlpotenz <10 wählbar sein.

Optional könnte man versuchen, TeX-Code für die konstruierten Maschinen auszugeben (etwa via TikZ und pgf).

Art der Arbeit: Bachelor-/Studienarbeit oder Master-/Diplomarbeit

Kontakt: Dr. Jürgen Koslowski


Formale Verifikation für Adaptive Interaktionsmechanismen

Im Projekt "Adaptive Interaktionsmechanismen" (AIM) der NTH Graduiertenschule über IT-Ökosysteme entwickeln wir ein inkrementellen Verifikationsverfahren auf der Basis von formalen Schnittstellenspezifikationen (Interface Automaten von T. Henzinger/L. De Alfaro). Aus dem Projekt ergeben sich verschiedene Themen für studentische Arbeiten.

Art der Arbeit: Bachelor-/Studienarbeit oder Master-/Diplomarbeit

Kontakt: Gianina Gănceanu


Automaten als Koalgebren

Verschiedenen Typen von deterministischen und nichtdeterministischen Automaten kann man als Koalgebren formalisieren und dadurch ihr Verhalten durch Koinduktion charakterisieren. Ziel der Arbeit ist eine allgemeine Beschreibung dieser Automaten zu formulieren.

Art der Arbeit: Bachelor-/Studienarbeit oder Master-/Diplomarbeit

Kontakt: Prof. Dr. Jiri Adamek


Markierte Transitionssyteme und terminale Koalgebren

Bisimilarität von Transitionssystemen lässt sich durch den Begriff der terminalen Koalgebra darstellen. Die Konstruktion der entspechenden terminale Koalgebra soll in dieser Arbeit durchgeführt werden.

Art der Arbeit: Bachelor-/Studienarbeit oder Master-/Diplomarbeit

Kontakt: Prof. Dr. Jiri Adamek


Abstands-Automaten

Der Hamming-Abstand zwischen zwei Wörtern gleicher Länge ist durch die Anzahl unterschiedlicher Komponenten gegeben. Diese stimmt mit der Minimalzahl der Substitutionen einzelner Buchstaben überein, mit der eines der Wörter in das andere überführt werden kann. Beim Levenshtein-Abstand sind außer Substitutionen auch Einfügungen und Löschungen einzelner Buchstaben erlaubt, um ein Wort in ein anderes zu überführen. Insbesondere brauchen die Ausgangswörter nun nicht mehr die gleiche Länge zu haben. Beim Damerau-Levenshtein-Abstand sind schließlich auch noch Transpositionen benachbarter Buchstaben als Operation erlaubt. Ein Levenshtein-Automat fuer ein Wort w und einen Zahl k ist ein endlicher Automat, der die Sprache V aller Wörter mit einem Levenshtein-Abstand <<i>k von w erkennt. Er kann in linearer Zeit bzgl. |w| konstruiert werden und erkennt V viel schneller, als die explizite Berechnung der Levenshtein-Abstände der Wörter in V von w benötigen würde, siehe ; Wikipedia. In der neueren Literatur (Mihov und Schulz: Fast Approximate Search in Large Dictionaries, 2004) werden auch sogenannte "universelle Levenshtein Automaten" eingeführt. Ziel der Arbeit ist es, Abstands-Automaten bzw. universelle Abstands-Automaten auch fuer den (einfacheren) Hamming-Abstand und den (komplizierteren) Damerau-Levenshtein-Abstand zu untersuchen und ggf. zu konstuieren, vorzugsweise auch in graphischer und lauffähiger Form. (Die Automaten sollen schrittweise entstehen, am Bildschirm oder in pdf-Form, und sollen anschließend benutzergewählte Eingaben schrittweise verarbeiten koennen.) Es soll sich also um ein didaktisches Werkzeug zur Visualisierung der Konstruktion und Arbeitsweise dieser Automaten handeln.

Art der Arbeit: Bachelor-/Studienarbeit oder Master-/Diplomarbeit

Kontakt: Dr. Jürgen Koslowski


Colimiten in set per Computer

Während in der Kategorie set der Mengen und Funktionen sogenannte "Limiten" leicht berechnet werden können (es handelt sich immer um Teilmengen cartesischer Produkte), sind "Colimiten" schwerer zu handhaben. Zwar lassen sie sich immer als Quotienten disjunkter Vereinigungnen darstellen, aber die zugehörigen &AUML;quivalenzrelationen können recht unhandlich werden. Gesucht ist ein Programm, das zumindest die Colimiten "kleiner" Diagramme aus Mengen und Funktionen zwischen ihnen berechnet. Die Umformung eines allgemeinen Diagramms in ein Paar von Funktionen zwischen zwei geeigneten disjunkten Mengen sollte möglich sein. Eine graphische Darstellung wäre wünschenswert, wobei auf frei verfügbare Grafik-Software zurückgegriffen werden kann.

Art der Arbeit: Bachelor-/Studienarbeit oder Master-/Diplomarbeit

Kontakt: Dr. Jürgen Koslowski


Anpassung der Krypto-Umgebung an moderne Entwicklungen

Die im Krypto-Praktikum zum Einsatz kommende Krypto-Umgebung ist ein weitgehend handgestricktes Konstrukt. Eine bessere Integration mit z.B. Eclipse wäre wünschenswert, ebenso wie das Design weiterer Alternativ-Aufgaben.

Art der Arbeit: Bachelor-/Studienarbeit oder Master-/Diplomarbeit

Kontakt: Dr. Jürgen Koslowski


Praktikum Fehlerkorrigierende Codes

Analog zum Krypto-Praktikum ist ein Praktikum zum Thema fehlerkorrigierende Codes in Planung. Design und Umsetzung einer geeigneten Programmierumgebung und erster Praktikumsaufgaben sind vor dem Start dieses Projekts erforderlich.

Art der Arbeit: Bachelor-/Studienarbeit oder Master-/Diplomarbeit

Kontakt: Dr. Jürgen Koslowski


Kategorielle Diagramme mittels PGF und TikZ

Bisher war das Macro-Paket xypic-3.7 Werkzeug der Wahl, wenn es galt kategorielle Diagramme für Veröffentlichungen zu erzeugen. Leider ist diese Paket für PostScript optimiert und nur unter Mühen zur Produktion von Diagrammen im PDF-Format zu bewegen. Dies gelingt besser mit dem TikZ-Frontend zum PGF-Macro-Paket von Till Tantau, das allerdings nicht vorrangig für kategorielle Diagramme entworfen wurde. Analog zu den schon existierenden Libraries für Automaten soll eine Library für kategorielle Diagramme entworfen werden. Ein ; Tutorial von Felix Lenders kann als Ausgangspunkt dienen.

Art der Arbeit: Bachelor-/Studienarbeit oder Master-/Diplomarbeit

Kontakt: Dr. Jürgen Koslowski


Algebraische Theorie Boolescher Schaltkreise

gemäß des kürzlich erschienenen Artikels von Yves Lafont (Towards an algebraic theory of Boolean circuits, Journal of Pure and Applied Algebra 184 (2003) 257-310)

Art der Arbeit: Bachelor-/Studienarbeit oder Master-/Diplomarbeit

Kontakt: Dr. Jürgen Koslowski


Rechnen mit Relationen und Spannen

Relationen zwischen zwei Mengen A und B lassen sich als Graphen auffassen, bei denen zwei Knoten durch höchstens eine Kante verbunden sind. Diese kann man auch mit binären AxB-Matrizen identifizieren, deren Einträge nur aus Nullen und Einsen bestehen. Bei allgemeineren Graphen sind auch mehrere Kanten zulässig, was sich darin wiederspiegelt, daß in den Matrizen natürliche Zahlen oder gar Mengen stehen können; die entsprechenden Verallgemeinerungen von Relationen heißen auch Spannen (spans). Während zwei Relationen von A nach B mittels Mengeninklusion verglichen werden können, sind im Fall von Spannen Mengenabbildungen zu nehmen. Viele Relationenoperationen lassen sich dennoch übertragen, Handrechnung wird aber zunehmend schwieriger. Neben der Komposition von Relationen bzw. Spannen gibt es noch andere interessante Operationen. Ziel der Arbeit ist es, ein interaktives Programm zur Berechnung dieser Operationen auf Relationen bzw. endlichen Spannen zwischen endlichen Mengen zu erstellen, das auch die Inklusionen zwischen Relationen bzw. Funktionen zwischwen Spannen berücksichtigt. Für hinreichend kleine Graphen wäre auch eine graphische Ein-/Ausgabe wünschenswert.

Art der Arbeit: Bachelor-/Studienarbeit oder Master-/Diplomarbeit

Kontakt: Dr. Jürgen Koslowski



  aktualisiert am 28.05.2014
TU_Icon_E_Mail_1_17x17_RGB Zum Seitenanfang