/ fb6 / tcs / research /

 

Forschungsinteressen

• Berechenbarkeitstheorie, insbesondere Berechenbarkeit auf topologischen Strukturen
• Bereichstheorie
• Komplexitätstheorie, insbesondere implizite Berechnungskomplexität
• Logik

Im Mittelpunkt der theoretischen Informatik, wenn nicht der Informatik überhaupt, steht der Begriff des Algorithmus. Es herrscht Übereinstimmung, dass ein Algorithmus zur Lösung eines Problems oder zur Berechnung einer Funktion eine endliche eindeutige Vorschrift zur Ausführung von einfachen endlichen Operationen auf einer Maschine ist, die für jeden Spezialfall der gegebenen Problemklasse bzw. für jedes Argument der vorliegenden Funktion nach endlich vielen Schritten eine Lösung liefert.

Die ist natürlich keine präzise mathematische Definition. Die Formalisierung des gerade beschriebenen intuitiven Algorithmenbegriffs gehört zu den großen intellektuellen Leistungen des vergangenen Jahrhunderts. Der Algorithmenbegriff wurde eingehend analysiert und zahlreiche, zum Teil äußerst verschiedene Formalismen wurden vorgeschlagen. Wie sich herausstellte, führen sie alle zum gleichen Begriff der berechenbaren Funktion. Dies führte zu der heute allgemein akzeptierten Auffassung, dass es sich hierbei um eine adäquate, mathematisch präzise Beschreibung des intuitiven Algorithmenbegriffs handelt (Church-Turing-These).

Wichtige Fragen, die sich in diesem Zusammenhang stellen sind:

• Was ist algorithmisch machbar, d.h., welche Probleme sind maschinell entscheidbar, welche Funktionen sind mittels eines Algorithmus berechenbar?
• Mit welchem Ressourcenverbrauch (Zeit, Platz) ist ein Problem entscheidbar bzw. eine Funktion berechenbar?
• Leistet ein Programm das Verlangte? Berechnet es z.B. eine vorgegebene Funktion?

Diese Fragestellungen sind Gegenstand folgender Teilgebiete: Berechenbarkeitstheorie, Komplexitätstheorie, Theorie der Programmierung.

In Untersuchungen zur Berechenbarkeit und Komplexität wurden meistens Funktionen und Probleme betrachtet, die auf endlichen Daten wie den natürlichen Zahlen oder endlichen Wörtern definiert sind. Es gab allerdings auch schon Untersuchungen zur Berechenbarkeit auf den reellen Zahlen oder anderer in der Analysis betrachteten Objekten. Das Interesse hieran hat in den letzten Jahren stark zugenommen. Die Gründe hierfür sind vielfach. Natürlich geht es um die Beantwortung der obigen Fragen im Bereich des wissenschaftlichen Rechnens. Im Gegensatz zur dort üblichen Approximation von reellen Zahlen durch Gleitkommazahlen mit der damit verbundenen Rundungsfehlerproblematik werden in diesen Untersuchungen Formalismen benutzt, die mit mathematisch treuen Darstellungen der reellen Zahlen arbeiten. Über die Beantwortung der obigen Fragestellungen hinaus sind diese Arbeiten Teil eines groß angelegten Projekts der algorithmischen und konstruktiven Durchdringung und Neubegründung der Analysis.

In der mathematischen Semantik von Programmiersprachen benutzt man vorzugsweise die von Dana Scott eingeführten Bereiche bzw. Verallgemeinerungen davon. Es handelt sich hierbei um verbandsähnliche Strukturen, auf denen eine kanonische Topologie erklärt ist, die wesentliche Eigenschaften von Berechnungen widerspiegelt. Topologische Struktur und Ordnungsstruktur bestimmen sich hier gegenseitig. Die Ordnung läßt sich als Relation "ist besser definiert als" oder "enthält mehr Information als" interpretieren. Als Folge lassen sich in der Sprache dieser Strukturen im Wesentlichen nur qualitative Approximationsaussagen machen. Aus der Analysis hingegen sind wir quantitative Aussagen gewöhnt. Die benutzten Räume besitzen eine metrische Struktur. Es hat sich nun herausgestellt, dass auch Bereiche abgeschwächte Distanzbegriffe zulassen. Dies hat zu zahlreichen neuen Fragestellungen geführt.

Komplexitätstheoretische Untersuchungen basieren größtenteils auf einem sehr einfachen Maschinenmodell, der Turing-Maschine. Es wird der Zeit- bzw. Platzverbrauch von Rechnungen auf dieser Maschine studiert. Der Programmierer kann sich dann an diesen Ergebnissen orientieren und den für seine Bedürfnisse besten Algorithmus auswählen. Die Struktur der Turing-Programme korrespondiert allerdings nur sehr schlecht mit der Struktur von Programmen in modernen Programmiersprachen. Wünschenswert sind Ergebnisse, die es ihm erlauben, aus der Struktur des Programms und der hierbei benutzten Kontrollstrukturen den Ressourcenverbrauch abschätzen zu können. Die Klärung dieses Sachverhalts ist das Ziel eines neu etablierten Forschungsgebiets, der impliziten (d.h. maschinenunabhängigen) Komplexitätstheorie.