Logo Leibniz Universität Hannover
Logo:Institut für Theoretische Informatik
Logo Leibniz Universität Hannover
Logo:Institut für Theoretische Informatik
  • Zielgruppen
  • Suche
 

Enumerations Probleme

Enumeration:
In diesem Projekt arbeiten wir mit Algorithmen für die Enumeration aller Lösungen und untersuchen dabei die Komplexität solcher Enumerationprobleme mit dem Ziel alle möglichen Lösungen eines gegebenen Berechnungsproblems zu generieren.

Im letzten Jahrzehnt wuchs das Forschungsgebiet der Enumerationsalgorithmen enorm, was auf die stetig zunehmende Datenmenge, die die Algorithmen im Alltag verarbeiten müssen zurückzuführen ist.

Die Hauptanwendung stellt sicherlich die Abfrage einer Datenbank, wo eine große Menge an Daten verarbeitet werden muss. Deshalb ist die inkrementelle und effiziente Berechnung der Anfragen zunehmend ein immer wichtiger werdendes Thema. So möchten zum Beispiel die Nutzer einer Web-Suchmaschine möglichst schnell eine Antwort auf eine Schlüsselwortabfrage bekommen. Des Weiteren findet die Enumeration in Operation Research, Data Mining, Bioinformatik, Computerlinguistik, sowie in Lösung von Constraints Anwendung.

Parametrisierte Komplexität:
Viele Probleme der Enumeration sind bereits als Entscheidungsprobleme schwer im Sinne von nur ineffizient zu berechnen.

Parametrisierte Komplexitätstheorie bietet die Möglichkeit einer eleganten Analyse schwerer algorithmischer Probleme, die sehr sinnvoll in Hinblick auf die Enumeration sind. Hierbei wird die Komplexität nicht nur in Bezug auf die Eingabegröße, sondern darüber hinaus noch in Bezug auf ein Parameter betrachtet. Die Komplexität der Probleme wird bestimmt, erst wenn der Parameter festgelegt ist.

In der letzten Dekade stieg zunehmend das Interesse an der parametrisierten Komplexitätstheorie. Das Untersuchen von Enumerationproblemen in diesem Kontext könnte beim Entwurf effizienter Algorithmen, sowie zu einem besseren Verständnis der inhärenten Komplexitätsfacetten der Enumerationprobleme helfen.

Wissenschaftliche Ziele:
Unser Hauptziel ist es die Untersuchung von Enumerationproblemen aus der Sicht der parametrisierten Komplexität und insbesondere Parameter-effiziente Enumerationsalgorithmen zu entwerfen. Nach heutigem Wissensstand wurde solch eine Untersuchung noch nicht gemacht. (In der Veröffentlichung von Fernau im Jahre 2002 wurde die Untersuchung in einem sehr frühen Stadium präsentiert).

Wir werden den Fokus auf die Entwicklung der algorithmischen Techniken für die Enumerationprobleme, mit besonderen Interesse an nichtmonotonen Logiken als Testumgebung legen.