Zufallsmethoden in der Informatik

Methoden der Wahrscheinlichkeitstheorie und Statistik: Zufallsvariablen, Verteilungen, erzeugende Funktionen, Abschätzungen, Zentraler Grenzwertsatz, statistische Tests, stochastische Prozesse. Randomisierte Datenstrukturen und Algorithmen, Markovketten und Zufallsirrfahrten, Entropie und Information, Monte Carlo Methode, paarweise Unabhängigkeit und Hashing, Zufallsgraphen, probabilistischer Existenznachweis. Simulated Annealing und Ising-Modell. Pseudozufallszahlengeneratoren.

• Ross: Probability Models for Computer Science. Academic Press, 2002.
• Mitzenmacher, Upfal: Probability and Computing. Cambridge, 2005.
• Schickinger, Steger: Diskrete Strukturen, Band 2. Springer, 2001.
• Häggström: Finite Markov Chains and Algorithmic Applications. Cambridge, 2002.
• Alon, Spencer: The Probabilistic Method. Wiley, 2015.
• Durrett: Random Graph Dynamics. Cambridge, 2007.
• Luby, Wigderson: Pairwise Independence and Derandomization. now Publ., 2006.
• Givens, Hoeting: Computational Statistics. Wiley, 2005.
• Mari, Schott: Probabilistic and Statistical Methods in Computer Science. Springer, 2001.

Weitere Informationen zur Vorlesung finden Sie im Moodle.