Dr. Stasys Jukna
FB IV - Informatik
Zufall und Wahrscheinlichkeit spielen eine besondere Rolle in der Diskreten Mathematik und der Theoretischen Informatik. Das Ziel dieser Vorlesung ist eine Vorstellung über die wichtigsten Ideen der Probabilistischen Methode zu bekommen:
- Basic Probabilistic Tools
- counting sieve, linearity of expectation, the deletion method, Lovasz Local lemma, etc.
- Randomness in Computations
- how and why coin tossing makes algoritms more efficient
- Derandomization
- how probabilistic existence proofs can be tranformed to deterministic algorithms
Literatur:
N. Alon and J. Spencer: The Probabilistic Method (Wiley) 1992.
S. Noar, Probabilistic Methods in Computer Science, 1992.
S. Jukna, A First Course in Combinatorcs of Finite Sets, 1996 (Teil III)
Die Vorlesung richtet sich an Informatik-Studenten und Mathematik-Studenten im Hauptstudium.
Vorlesung:Übung:
