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

• Erstellungsjahr: 2013

Zusammenfassung der Projektergebnisse

Im Projekt Average-Case Analyse von Algorithmen auf der Basis von Spursprachen wurden Detailfragen zu einer neuen Methode der Algorithmenanalyse untersucht, die darauf angelegt waren, diese (ggf. teilweise) zu automatisieren. Im Detail zielte das Arbeitsprogramm auf die verlässliche Extrapolation des in Simulationen beobachteten Verhaltens auf beliebige – d.h. in einer Variablen n symbolische – Eingabegrößen sowie auf die Erfassung höherer Momente der betrachteten Güteparameter und die Methodik zur Erfassung der Eingabegröße ab. Die meisten dabei zu lösenden Herausforderungen konnten derart bewältigt werden, dass unsere Methode in einem Tool namens MaLiJAn (Maximum Likelihood Java Bytecode Analyzer) implementiert werden konnte. Lediglich die Erfassung höherer Momente der Güteparameter ist bisher nicht gelungen. Die Arbeit an diesem Problem brachte jedoch eine neue Methode zur quantitativen Untersuchung schwach kontext-sensitiv kodierbarer kombinatorischer Strukturen hervor, die wir nutzen konnten, um eine über 10 Jahre offene Frage im Bereich der theoretischen Bioinformatik zu lösen (Analyse des Suchraums des Algorithmus von Rivas & Eddy zur Vorhersage pseudokontenbehafteter RNA Sekundärstrukturen). Fallstudien haben gezeigt, dass unsere Methode/unser Werkzeug in der Lage ist, neue und interessante Ergebnisse zum mittleren Verhalten von Algorithmen zu generieren. Dies konnte durch zwei Publikationen im Kontext der Analyse des Java 7 Dual Pivot Quicksorts sowie durch eine Untersuchung verschiedener Varianten des Ford Fulkerson Algorithmus belegt werden.

Projektbezogene Publikationen (Auswahl)

• Algebraic and Combinatorial Properties of Common RNA Pseudoknot Classes with Applications, Journal of Computational Biology (2012) 19(10): 1134-1150
  Markus E. Nebel and Frank Weinberg
  
• Average Case Analysis of Java 7’s Dual Pivot Quicksort, in L. Epstein and P. Ferragina (Eds.): ESA 2012, LNCS 7501, Springer, 2012, 825-836 [Best paper award]
  Sebastian Wild and Markus E. Nebel
  
• Engineering Java 7’s Dual Pivot Quicksort Using MaLiJAn, SIAM Meeting on Algorithm Engineering & Experiments 2013 (ALENEX13)
  Sebastian Wild, Markus E. Nebel, Raphael Reitzig and Ulrich Laube