Hasso-Plattner-Institut
  
    • de
 

Vorlesungsankündigung

(Wintersemester 1997/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 ü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:

  • Mi 14-15:30 (Raum V 302)

Übung:

  • Mi 16-17:30 (Raum V 302)