Average-Case Analyse von Algorithmen auf der Basis von Spursprachen

• Applicant: Professor Dr. Markus Nebel
• Subject Area: Theoretical Computer Science
• Term: from 2010 to 2013
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 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 Programme: Research Grants