Seminar über zufällige Bäume: Termine, Vortragende und Literatur

Kontakt: Tämur Ali Khan

Eine Einführung in Martingale in diskreten Räumen:

Motwani, R., Raghavan, P. (1995) Randomized algorithms. Cambridge University Press, Cambridge, 1995. xiv+476 pp.
[Seiten 83-91]

19.04.: Modelle zufälliger Bäume
Daniel Malek

Die im Seminar auftretenden Bäume sollen eingeführt werden mit ihren stochastischen Modellen und elementaren Eigenschaften: Binärsuchbaum, rekursiver Baum, digitale Baumstrukturen (Tries, digitaler Suchbaum, PATRICIA Trie).

26.04.: Höhe zufälliger Binärsuchbäume
Simon Kesselmann

Schwaches Gesetz großer Zahlen für die Höhe zufälliger Binärsuchbäume.

Devroye, L. (1998) Branching processes and their applications in the analysis of tree structures and tree algorithms. Probabilistic methods for algorithmic discrete mathematics, 249-314, Algorithms Combin., 16, Springer, Berlin, 1998.
[ Abschnitte 1.1 und 2.1.]

03.05.: Pfadlänge zufälliger Binärsuchbäume I
Elisabeth König

Grenzwertsatz für die Pfadlänge zufälliger Binärsuchbäume mit Martingalkonvergenzsatz. Kann analog auch gleich für den zufälligen rekursiven Baum mitgemacht werden.

Regnier, M. (1989) A limiting distribution for quicksort. RAIRO Inform. Theor. Appl. 23, 335-343.
Mahmoud, H.M. (1991) Limiting distributions for path lengths in recursive trees. Probab. Engrg. Inform. Sci. 5, 53-59.

10. und 17.05: Pfadlänge zufälliger Binärsuchbäume II
Frank Bocek und Michael Morchutt

10.05. Vortrag 1 (Frank Bocek): Azuma-Hoeffding-Ungleichung mit Anwendung auf das traveling salesman problem.

Steele, J. M. (1997) Probability theory and combinatorial optimization. CBMS-NSF Regional Conference Series in Applied Mathematics, 69. Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 1997
[Seiten 4-5, 27-29.]

17.05. Vortrag 2 (Michael Morchutt): Tails der Pfadlänge zufälliger Binärsuchbäume mit Azuma-Hoeffding-Ungleichung.

McDiarmid, C.J.H., Hayward, R.B. (1996) Large deviations for Quicksort. J. Algorithms 21, 476-507.
[Bis einschließlich Abschnitt 2.3.]

24.05.: Pfadlänge zufälliger Binärsuchbäume III
Philipp Hoechst

Charakterisierung der Grenzverteilung der internen Pfadlänge zufälliger Binärsuchbäume durch eine stochastische Fixpunktgleichung.

Rösler, U. (1991) A limit theorem for "Quicksort". RAIRO Inform. Theor. Appl. 25, 85-100.

31.05.: Pfadlänge zufälliger Binärsuchbäume IV
Margret Knape

Eigenschaften des Grenzwerts der internen Pfadlänge zufälliger Binärsuchbäume. Existenz und Schranken für der Dichte. Verwendet charakteristische Funktionen.

Fill, J.A., Janson, S. (2000) Smoothness and decay properties of the limiting Quicksort density function. Mathematics and computer science (Versailles, 2000), 53-64, Trends Math., Birkhäuser, Basel.

07. und 16.6.: Lempel-Ziv Kodierung
Yi Xu und Chuan Wang

07.06.Vortrag 1 (Yi Xu): Entropie und Knotentiefen in digitalen Suchbäumen.

16.06.Vortrag 2 (Chuan Wang): Analyse der Anzahl benötigter Bits bei Lempel-Ziv Kodierung für Quelle, die i.i.d. Symbole generiert.

Für beide Vorträge:
Devroye, L. Lecture Notes zum Kurs CS690 der McGill University, Montreal. [Vorsicht beim Herunterladen: >3MB]

21.06.: Profil zufälliger Binärsuchbäume
Henning Sulzbach

Asymptotische Aussagen über das Profil zufälliger Binärsuchbäume.

Chauvin, B., Klein, T., Marckert, J.-F., Rouault, A. (2005) Martingales and profile of binary search trees. Electron. J. Probab. 10, 420-435.

Diese Arbeit benutzt Auszüge aus:
Biggins, J. D. (1992) Uniform convergence of martingales in the branching random walk. Ann. Probab. 20, 137-151.
Jabbour-Hattab, J. (2001) Martingales and large deviations for binary search trees. Random Structures Algorithms 19, 112-127.


28.06.: Binärsuchbäume: Local Counters
Johannes Bufe

Einige Grenzwertsätze für zufällige Binärsuchbäume mit kombinatorischen Beobachtungen und klassischen Grenzwertsätzen.

Devroye (1991) Limit laws for local counters in random binary search trees. Random Structures Algorithms 2, 303-315.

05.07.: Funktionale zufälliger Binärsuchbäume
Julia Fey

Grenzwertsatz allgemeiner Funktionale zufälliger Binärsuchbäume mit Steinscher Methode.

Devroye (2002) Limit laws for sums of functions of subtrees of random binary search trees. SIAM J. Comput., 32, 152-171.

12.07.: Tiefen in zufälligen Bäumen
Heidrun Semmler

Universeller Grenzwertsatz für die Tiefen in allgemeinen Modellen zufälliger Bäume.

Devroye (1999) Universal limit laws for depths in random trees. SIAM J. Comput., 28, 409-432.

19.07.: Höhe in Tries und digitalen Suchbäumen
Shpetim Fejzulai

Gesetz großer Zahlen und Tail-Ungleichungen der Höhe in Tries und digitalen Suchbäumen.

Devroye (2002) Laws of large numbers and tail inequalities for random tries and PATRICIA trees. J. Comput. Appl. Math., 142, 27-37.