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

 

Die Klausur "Zufallsmethoden in der Informatik" findet am 12.02.2020 ab 12:00 Uhr in Hörsaal 13 statt, Dauer: 90 Minuten.

Die Nachklausur findet am 01.04.2020 ab 10:00 Uhr in Hörsaal 9 statt, Dauer: 90 Minuten.

Erlaubte Hilfsmittel an beiden Terminen sind ein beidseitig beschriebenes DIN A4-Blatt sowie ein Taschenrechner.

Zur Verfügung gestellt wird ein Blatt mit der Tabelle der Standardnormalverteilung.