Average-Case Analyse von Algorithmen

点击翻译按钮获取中文摘要

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.