Average-Case Analyse von Algorithmen auf der Basis von Spursprachen

• Antragsteller: Professor Dr. Markus Nebel
• Fachliche Zuordnung: Theoretische Informatik
• Förderung: Förderung von 2010 bis 2013
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 166567075

Die Ressourcen (Speicherplatz, Rechenzeit, ...), die ein Programm (Algorithmus) zur Lösung seiner Aufgaben benötigt, werden in der Informatik zu verschiedenen Zwecken untersucht. Betrachtet man beispielsweise die Rechenzeit, die ein Algorithmus zur Lösung eines Problems für die schwierigste aller Eingaben benötigt (Worst-Case), so lässt dies Rückschlüsse auf die Komplexität des behandelten Problems zu, vor allem dann, wenn man hierbei die effizientesten Algorithmen betrachtet. Bestimmt man den Erwartungswert des Ressourcenverbrauchs (Average-Case), so kann man unter der Annahme typischer Eingaben eine Empfehlung aussprechen, welcher Algorithmus seine Aufgabe im Durchschnitt (beispielsweise hinsichtlich der benötigten Zeit) am billigsten löst und von daher bevorzugt eingesetzt werden sollte. Analysen, die solche Erwartungswerte bestimmen, sind jedoch mathematisch anspruchsvoll und sehr aufwendig und gelten nur für die bei der Analyse gemachten Annahmen hinsichtlich der Eingabeverteilung. Für die praktische Anwendbarkeit der erzielten Ergebnisse müssen die realen Eingaben diese Annahmen widerspiegeln, was selten der Fall bzw. oft auch einfach nur unbekannt ist. Das hier beschriebene Vorhaben möchte deshalb zwei Nachteile der Average-Case Analyse mindern helfen: 1. Durch die Bereitstellung eines Analysewerkzeuges soll ein Großteil der für eine Average-Case Analyse notwendigen Schritte automatisiert durchgeführt werden können, 2. wobei die zur Analyse herangezogene Verteilung der Eingabedaten aus den Daten der praktischen Anwendung extrahiert werden, wodurch ein Anwendungsbezug der Ergebnisse garantiert wird. Wir greifen dabei auf einen neuen Ansatz für die Analyse von Algorithmen zurück, der in Einzelfällen bereits erfolgreich zum Einsatz kam. Im hier beantragten Projekt sollen nun die Grundlagen vorangetrieben werden, auf deren Basis später ein entsprechendes Werkzeug aufgebaut werden kann.

• DFG-Verfahren: Sachbeihilfen