Forschungsgebiete

Die Berechenbarkeitstheorie beschäftigt sich aus mathematischer Sicht mit der Idee der Berechnung, oder auch des Algorithmus. Verschiedene Modelle zur Fassung der Idee der Berechnung werden betrachtet und deren Möglichkeiten erforscht. Die Berechenbarkeitstheorie ist eng mit der mathematischen Logik verwandt.

Bei der Circuit Complexity werden als Berechnungsmodell Schaltkreise betrachtet. Dadurch ergeben sich andere Maße für den Ressourcenbedarf als in der klassischen Komplexitätstheorie. Wir interessieren uns besonders für den Zusammenhang von gewissen Schaltkreisklassen, Logiklassen erster Stufe und Algebra. [read more ...]

Neben der Frage, wie ein Problem algorithmisch gelöst werden kann, ist auch die Frage nach der Effizienz einer solchen algorithmischen Lösung fundamentaler Bestandteil der Informatik. Die Komplexitätstheorie beschäftigt sich mit der Frage, welchen Ressourcenaufwand die Lösung ein Problems erfordert. [read more ...]

Fixed-Parameter-Algorithmen liefern optimale Lösungen zu gegebenen diskreten kombinatorischen Problemen. In der Regel sind die betrachteten Probleme NP-schwer, man muss sich also mit exponentieller Laufzeit abfinden. Jedoch kann es sein, dass das exponentielle Wachsen der Laufzeit nur von bestimmten, problemspezifischen Parametern abhängt, die Teil der Eingabe sind. Ziel ist es, derartige Parameter zu identifizieren: falls die Werte dieser Parameter dann in konkreten Anwendungen des jeweiligen Problems klein sind, kann das exponentielle Wachstum gegebenenfalls in Kauf genommen werden und das Problem mit einem Fixed-Parameter-Algorithmus effizient gelöst werden. Ein solcher Parameter kann zum Beispiel die Baumweite eines Graphen sein: viele Graphenprobleme sind für Graphen mit kleiner Baumweite schnell lösbar.

Formale Sprachen sind ein grundlegendes Mittel der theoretischen Informatik um Problemstellungen zu Formalisieren. Sie ermöglichen eine strukturierte und linearisierte Darstellung von Daten. Anwendungen in der Praxis sind beispielweise im Compilerbau zu finden. Bekannte Beispiele für Formale Sprachen, die in der Praxis auftauchen, sind Programmiersprachen, oder auch HTML und XML. [read more ...]