Ferdinand-von-Lindemann-Preis 2006

In der Diplomarbeit "Stochastische Fixpunktgleichungen, exponentielle tail Abschätzungen und large deviation für rekursive Algorithmen" werden neue Methoden (exponentielle tail Abschätzungen) entwickelt, mit denen sich das Verhalten von (z.B.) rekursiven Algorithmen genauer untersuchen lässt. Für einige wichtige Kenngrößen, die bei der Analyse von Algorithmen auftreten, werden präzise Grenzwertaussagen gemacht.

Stochastische rekursive Gleichungen treten bei einer Vielzahl von Problemen auf: verschiedene Baumstrukturen, die zur Organisation von Daten verwendet werden, Algorithmen zur Lösung von Such-, Sortier- und Auswahlproblemen, Algorithmen auf Graphen und Zeichenketten (DNA Sequenzen, Suche im Internet) und kombinatorische Probleme haben rekursive Struktur. Um sich gegen große Abweichungen der interessanten Kenngrößen vom Erwartungswert abzusichern, untersucht man das tail Verhalten dieser rekursiven Strukturen. Ausgehend von der Kontraktionsmethode, die ein effektives Werkzeug zur Analyse des asymptotischen Verhaltens dieser Rekursionen darstellt, werden in der Arbeit zahlreiche exponentielle tail Abschätzungen vorgenommen und Anwendungsbeispiele behandelt. Es werden sowohl Rekursionen vom additiven Typ untersucht, wie sie bei average-case Analysen auftreten, als auch max-rekursive Gleichungen, die bei worst-case Untersuchungen auftreten. Dazu werden sowohl klassische Konzentrationsungleichungen wie Abschätzungen aller Momente und der Laplacetransformierten genutzt. Die tails der Limiten der geeignet normierten Rekursionen, die mit der Kontraktionsmethode als Lösung einer Fixpunktgleichung charakterisiert werden können, werden mit analogen Methoden erfolgreich untersucht.

Im zweiten Teil der Arbeit wird ein allgemeiner b-närer Baum mit zufälligen Gewichten analysiert. Ein Resultat von N. Broutin und L. Devroye (2005) über die Konvergenz der gewichteten Höhe wird auf den Fall abhängiger Gewichte mittels des Gärtner-Ellis-Theorems verallgemeinert. Ein Grenzwertsatz für die interne Pfadlänge dieses Baumes wird gezeigt. Dabei wird die Kontraktionsmethode erstmals auf den Fall mit stetiger Zeit verallgemeinert.