Zufallsgesteuerte Algorithmen WS 11/12

Achtung: Die ist eine Veranstaltung des Masterstudiengangs mit relativ hohem Mathematik-Anteil. Vorkenntnisse im Bereich der Wahrscheinlichkeitsrechnung sind von Nutzen, aber keine Bedingung, Spass an Mathematik mit Saetzen und Beweisen aber schon.

Themen

1. Einleitung
2. Grundlagen
3. Ueberlisten des Gegners
4. Die Methode der Fingerabdruecke
5. Wahrscheinlichkeitsverstaerkung
6. Die Methode der haeufigen Zeugen
7. Optimierung und zufaelliges Runden

Literatur

J. Hromkovic: Randomisierte Algorithmen, Teubner, 2004
R. Motwani, P. Raghavan: Randomized Algorithms, Cambridge, 2007