Average-Case Analyse von Algorithmen

• Applicant: Professorin Dr. Angelika Steger
• Subject Area: Theoretical Computer Science
• Term: from 2003 to 2006
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 5415734

Eine der zentralen Fragestellungen in der theoretischen Informatik ist die der Analyse von Algorithmen. Hierbei unterscheidet man zwischen Worst-Case Analyse, bei der Aussagen über den schlechtesten Fall getroffen werden und der Average-Case Analyse, bei der das durchschnittliche Verhalten des Algorithmus betrachtet wird. Aus praktischer Sicht ist letztere insbesondere dann wichtig, wenn die Worst-Case Analyse keine befriedigenden Qualitätsmerkmale des Algorithmus ergibt: es kann durchaus sein, dass der Algorithmus empirisch gute Ergebnisse liefert, obwohl er ein schlechtes Worst-Case Verhalten hat. Der Sortieralgorithmus QuickSort ist ein typisches Beispiel für dieses Phänomen. Leider stellt er jedoch auch eines der wenigen Beispiele dar, für die man bislang überhaupt in der Lage war, eine Average-Case Analyse erfolgreich durchzuführen. An diesem Punkt soll das beantragte Projekt ansetzen. Es sollen neue Modelle und Analysemethoden für die Average-Case Analyse von Algorithmen entwickelt werden.

• DFG Programme: Research Grants