Probabilistic analysis of recursive algorithms and data structures

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

Methoden zur stochastischen Analyse von Algorithmen und Datenstrukturen sollen entwickelt bzw. weiterentwickelt und auf die fundamentalen algorithmischen Aufgaben (Sortier-, Such- und Auswahlprobleme, Erzeugen von Zufallszahlen, ...) angewandt werden. Unter natürlichen Verteilungsannahmen an die Daten beschreiben charakteristische Kenngrößen wie Laufzeit und Speicherplatz das Verhalten eines Algorithmus. Asymptotische Entwicklungen für die Momente, schwache Konvergenz der Verteilungen und Eigenschaften - etwa die Existenz von Dichten, Unimodalität und Tail-Abschätzungen - der häufig nicht normalverteilten Limiten sollen zusammen mit Wahrscheinlichkeiten für große Abweichungen vom Erwartungswert ("large deviation") untersucht werden. Besonderer Wert soll auf die Entwicklung von Methoden zur probabilistischen worst-case Analyse gelegt werden. Hierbei treten Maxima von abhängigen Zufallsvariablen auf, für die bisher keine befriedigenden Analysen möglich sind.