Maximum Likelihood Analyse von Algorithmen und Datenstrukturen

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

In der Theoretischen Informatik wird ein Algorithmus traditionell auf der Basis seines Worst- Case Verhaltens im Bezug auf seine Rechenzeit, seinen Speicherplatzbedarf usw. beurteilt, d.h. man betrachtet die jeweils schwerste Eingabe, wodurch Rückschlüsse auf die Komplexität des gelösten Problems möglich werden. Die dabei erzielten Ergebnisse sind aus praktischer Sicht oft irreführend, da eine solche Eingabe nur mit verschwindend geringer Wahrscheinlichkeit tatsächlich vorkommen und die Güte des Algorithmus für andere Eingaben eine ganz andere sein kann. Für die immer bedeutsamer werdenden randomisierten Algorithmen und Datenstrukturen ist eine Worst-Case Betrachtung unmöglich; hier müssen Erwartungswerte der Güteparameter herangezogen werden. Die Untersuchung des Average-Case Verhaltens, d.h. die Bestimmung des mittleren Verhaltens (Erwartungswert) der Güteparameter bei Betrachtung zufälliger Eingaben oder randomisierter Algorithmen, ist aufwendig und für den Praktiker nur dann hilfreich, wenn das Zufallsmodell der Analyse die Realität hinreichend präzise widerspiegelt. Letzteres ist aus verschiedenen Gründen für viele Average-Case Analysen nicht der Fall. In der ersten Phase des hier zur Verlängerung stehenden Vorhabens haben wir einen Weg aufgezeigt, der eine Average-Case Analyse auf einem aus Daten der praktischen Anwendung/Simulation abgeleiteten Zufallsmodell ermöglicht, und gleichzeitig gestattet, einen Großteil der dazu notwendigen Berechnungen auf Basis eines Computeralgebra-Systems zu automatisieren. Im Vergleich zu traditionellen Simulationsergebnissen hat die neue Methodik den Vorteil, daß zum einen im nachhinein auch solche Eigenschaften der Algorithmen untersucht werden können, an deren Betrachtung im vorhinein nicht gedacht wurde – und dies ohne Simulationsläufe zu wiederholen – und daß die Ergebnisse als Funktion in der Eingabegröße vorliegen, so daß auch präzise Aussagen zu in der praktischen Anwendung/Simulation nicht betrachtete Eingabegrößen möglich sind. In der ersten Phase des Projektes konnten wir positive Ergebnisse hinsichtlich der prinzipiellen Machbarkeit einer automatisierten Average- Case Analyse vieler praxisrelevanter Algorithmen und Datenstrukturen zeigen. In der hier beantragten Fortsetzung des Projektes geht es nun im wesentlichen darum, die Möglichkeiten der neuen Methode zu erweitern sowie das Wissen um ihre Automatisierung zu vertiefen.

• DFG-Verfahren: Sachbeihilfen