Stochastische Analyse rekursiver Algorithmen und Datenstrukturen

• Antragsteller: Professor Dr. Ralph Neininger
• Fachliche Zuordnung: Mathematik
• Förderung: Förderung von 2000 bis 2010
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 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-Verfahren: Emmy Noether-Nachwuchsgruppen