Zufallsmethoden in der Informatik

Inhalt

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.

Literatur

  • 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.
  • Brémaud, Pierre: Discrete Probability Models and Methods, 2017.

Vorlesungszeiten

Dienstag 12-14 Uhr
in O27/121

Mittwoch 12-14 Uhr
in O27/2201

Sonstiges

Modulbeschreibung

LSF-Eintrag