Algorithmen und Komplexität - Hauptseite Algorithmen und Komplexität

Vorlesung: Probabilistische Methoden

Dozentin: PD Dr. Mihyun Kang

Termine

Beginn der Vorlesung: 16.10.2007.
VL Dienstag 09:00 - 11:00 (RUD 26, 1'307)
Donnerstag 09:00 - 11:00 (RUD 26, 1'307)
Sprechstunde Mittwoch 14:00 - 15:00 (RUD 25, 3.417)

Zuordnung

  • Hauptstudium, Halbkurs
  • Theoretische Informatik

Inhalte und Lernziele

Schwerpunkte der Vorlesung sind die Erste- und Zweite-Moment-Methode, das Lovasz-Local-Lemma und die Janson-Ungleichung. Im Mittelpunkt stehen Anwendungen dieser Techniken im Gebiet der Kombinatorik, der zufallige Graphen und der randomisierte Algorithmen.

Literatur

  • N. Alon und J.H. Spencer, The Probabilistic Method, 2nd Edition, Wiley-Interscience, 2000
  • S. Janson, T. Luczak und A. Rucinski, Random Graphs, John Wiley & Sons, Inc., 2000
  • J. Matousek und J. Vondrak, The Probabilistic Method
zuletzt geändert am 14.02.2008 (alkox-www)