Vorlesungsankündigung

(Wintersemester 97/98)

Probabilistische Methoden in der Informatik

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 üuber die wichtigsten Ideen des Probabilistichen Methods zu bekommen:
  1. Basic Probabilistic Tools
    counting sieve, linearity of expectation, the deletion method, Lovasz Local lemma, etc.
  2. Randomness in Computations
    how and why coin tossing makes algoritms more efficient
  3. 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, Combinatorial Methods, 1996.

Die Vorlesung richtet sich an Informatik-Studenten und Mathematik-Studenten im Hauptstudium.

Vorlesung:
Mi 14-15:30 (Raum V 302)
Übung:
Mi 16-17:30 (Raum V 302)