Probabilistic analysis of recursive algorithms and data structures

• Applicant: Professor Dr. Ralph Neininger
• Subject Area: Mathematics
• Term: from 2000 to 2010
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 5286610

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.

• DFG Programme: Independent Junior Research Groups