Thema:
In diesem Bachelor-Seminar werden eine Reihe von zufälligen diskreten Strukturen, Probleme der kombinatorischen Optimierung sowie Zufallsvariable, die durch Algorithmen motiviert sind, aus Sicht der Stochastik diskutiert. Die Vorträge orientieren sich mehrheitlich an Originalarbeiten.
Veranstalter:
Prof. Dr. R. Neininger
MSc J.Straub
MSc S. Plomer
Module:
BaM-STO-gs (zusammen mit der Vorlesung Stochastische Prozesse)
BaM-STO-gks, d.h. Spezialisierung in Stochastik (zusammen mit den Vorlesungen Stochastische Prozesse und Stochastische Analyse von Algorithmen)
Termin:
Di 12-14, Raum 711 (klein), Robert-Mayer Str. 10
Abgabe des Thesenblatts:
Bis 1 Wochen vor dem Vortrag per Email als PDF-Datei an die Betreuerin des Vortrags.
Abgabe der Ausarbeitung:
Bis 3 Wochen nach dem Vortrag per Email als PDF-Datei an die Betreuerin des Vortrags.
Termine, Themen, Literatur
Der Termin 22.10.2019 entfällt
Der Termin 29.10.2019 entfällt
05.11.2019
de Finetti und scale free trees.
van der Hofstad, R. (2019)
Random Graphs and Complex Networks. Vol II
Lecture Notes Abschnitt 5.1
12.11.2019
Martingal für Quicksort
Régnier, M. (1989)
A limiting distribution for quicksort.
RAIRO Inform. Théor. Appl. 23, no. 3, 335–343.
Originalarbeit von Régnier
Mahmoud, H. (1991)
Limiting Distributions for Path Lengths in Recursive Trees.
Probability in the Engineering and Informational Sciences 5, 53-59.
Internetseite des Artikels.
19.11.2019
Grenzwertsatz für Quicksort
Rösler, U. (1991)
A limit theorem for "Quicksort".
RAIRO Inform. Théor. Appl. 25, no. 1, 85–100.
Originalarbeit von Rösler
Abschnitte 1-3 sollen besprochen werden.
Der Termin 26.11.2019 entfällt
03.12.2019
Trace reconstruction
Nazarov, F and Peres, Y. (2017)
Trace Reconstruction with exp(O(n^1/3)) Samples.
STOC’17, Montreal, Canada
Originalarbeit von Nazarov und Peres
Der Termin 10.12.2019 entfällt
17.12.2019
Yagloms exponentialer Grenzwertsatz
Geiger, J. (2000)
A new proof of Yaglom's exponential limit law.
Mathematics and computer science (Versailles, 2000), 245–249,
Trends Math., Birkhäuser, Basel.
Originalarbeit von Geiger
Der Termin 14.01.2020 entfällt
21.01.2020
Perfekte Simulation von Perpetuities
Fill, J.A. and Huber, M.L. (2010)
Perfect simulation of Vervaat perpetuities.
Electron. Commun. Probab. 15 (2010), 96–109.
Originalarbeit von Fill und Huber
Devroye, L. and Fawzi, O. (2010)
Simulating the Dickman distribution.
Statist. Probab. Lett. 80, no. 3-4, 242–247.
Originalarbeit von Devroye und Fawzi
28.01.2020
Zufällige Projektionen
Vempala, S.S. (2004)
The random projection method.
DIMACS Series in Discrete Mathematics and Theoretical Computer Science, 65.
American Mathematical Society, Providence, RI. x+105 pp.
ISBN: 0-8218-2018-4
Seiten 1-14
Der Termin 04.02.2020 entfällt