> Friedrich-Schiller-Universität Jena
Fakultät für Mathematik und Informatik
Theoretische Informatik I
> Diplomarbeiten

Aktuelle Diplomarbeitsthemen:

Wir bieten Diplomarbeitsthemen aus den Bereichen Graphalgorithmik, algorithmische Bioinformatik und Wahlsysteme (Computational Social Choice), welche sich am aktuellen Forschungsstand orientieren. Eigene Themenvorschläge sind möglich und können betreut werden, falls sich das Thema mit den Expertisen des Arbeitsbereichs überschneidet.

Matching-Generalisierungen

Ansprechpartner: Hannes Moser

Das klassische, in Polynomzeit lösbare Matching-Problem ist ein gut untersuchter und wichtiger Forschungsgegenstand der theoretischen Informatik.
Aufgabe dieser Arbeit ist die Untersuchung NP-schwerer Generalisierungen des Matching-Problems, z.B. des induzierten Matchings, des multidimensionalen Matchings oder des constrained Matchings. Obwohl viele dieser Problemvarianten bereits aus Sicht der klassischen Komplexitätstheorie untersucht wurden, gibt es bisher nur wenige Resultate bezüglich ihrer parametrisierten Komplexität.
Es können im Rahmen dieser Diplomarbeit sowohl Probleme untersucht werden deren parametrisierte Komplexität unbekannt ist, als auch bereits existierende Resultate (z.T. von unserer Arbeitsgruppe) erweitert oder verbessert werden.

Literatur:

PCR Primer Selection

Ansprechpartner: Johannes Uhlmann

Polymerase-Kettenreaktion (PCR) ist eine Methode, um DNA zu vervielfältigen. Dafür benötigt man Primer, kurze DNA-Stücke, die dem Anfang des zu kopierenden Abschnittes entsprechen. In vielen Anwendungen muss man Serienexperimente machen und dabei jeweils bestimmte Primer für die PCR herstellen. Man kann dabei viel sparen, wenn man Primer wiederverwendet. Aufgabe ist es, mit möglichst wenigen der Kandidatenprimer auszukommen, wobei man aber mögliche Konflikte beachten muss. Es gibt diverse Problemformalisierungen. In einer Variante geht es z. B. darum, korrekte Messbarkeit mit Massenspektrometern sicherzustellen. Optimales Lösen ist meistens NP-schwer; es werden Heuristiken verwendet.
Aufgabe ist zu untersuchen, inwieweit andere Ansätze, insbesondere Festparameter-Algorithmen (FPT) und Datenreduktionsregeln verwendet werden können. Dies scheint erfolgversprechend, da es eine gute Auswahl von Problemvarianten und moeglichen Parametern gibt.

Literatur: Diese Arbeit kann evtl. in Zusammenarbeit mit dem Lehrstuhl Bioinformatik von Prof. Böcker bearbeitet werden.

Varianten des "Maximum Leaf Spanning Tree" Problems

Ansprechpartner:
Jiong Guo

Diese Arbeit beschäftigt sich mit dem Problem, einen Spannbaum in einem schwarz-weiss gefärbten bipartiten Graphen zu finden, der eine maximale mögliche Anzahl schwarzer Blätter hat. Das Problem ist NP-schwer auf bipartiten Graphen mit Maximimalgrad 4.
Ziel ist es zu untersuchen, ob sich existierende Algorithmen für "Maximum Leaf Spanning Tree" auf das beschriebene Spannbaum-Problem anwenden lassen. Eine weitere mögliche Aufgabe ist die Beantwortung der Frage ob das beschriebene Problem auch auf 3-regulären schwarz-weiss gefärbten bipartiten Graphen NP-schwer ist (offenes Problem von Fusco und Monti [International Symposium on Algorithms and Computation 2007]).

Literatur:

Vorhersage von Proteineigenschaften mittels Aufzählung dichter Teilgraphen (für Bioinformatiker).

Ansprechpartner: Christian Komusiewicz

Netzwerke bzw. Graphen sind ein wichtiges Werkzeug zur Modellierung biologischer Prozesse. In Protein-Interaktionsnetzwerken werden Proteine eines Organismus und ihre paarweisen Wechselwirkungen dargestellt. Aufgrund experimenteller Beschränkungen sind die Daten in diesen Netzwerken oft unvollständig.
Anliegen dieser Arbeit sollte es sein, zu untersuchen inwiefern Algorithmen unserer Gruppe zum Aufzählen dichter und isolierter Teilgraphen zur Vorhersage solcher fehlenden Daten geeignet sind. Insbesondere sollte hierbei ein Vergleich mit existierenden Methoden erfolgen.

Literatur: Diese Arbeit kann evtl. in Zusammenarbeit mit dem Lehrstuhl Bioinformatik von Prof. Böcker bearbeitet werden.
Valid HTML 4.01! Last modified: Tue Jan 22 16:29:53 CET 2008