Termine
Beginn der Vorlesung:
17.10.2000
| VL |
Dienstag |
11:00 - 12:30 |
(RUD 25, 3.101) |
| Dienstag |
13:30 - 15:00 |
(RUD 25, 3.111) |
Zu dieser Vorlesung gibt es ein
Skript (.ps.gz)
Zuordnung
- Hauptstudium, Halbkurs
- Theoretische Informatik
Voraussetzungen
- Vorkenntnisse aus Vorlesungen wie mathematische Grundlagen, Stochastik oder Graphen und Algorithmen sind hilfreich, aber nicht zwingend erforderlich.
Inhalte und Lernziele
Die Nutzung des Zufalls hat sich in vielen Bereichen der Informatik als ein unersätzliches Werkzeug erwiesen.
Die folgenden Themen sind eindrucksvolle Beispiele dafür und stehen im Mittelpunkt dieser Vorlesung:
- Randomisierte Algorithmen
- Average-Case Analyse von Algorithmen
- Quasi-zufällige Strukturen und Probabilistische Existenzbeweise
- Algorithmische Lerntheorie
Empfohlene Literatur
-
Alon, Spencer,
The Probabilistic Method,
John Wiley, 1992
-
Anthony, Biggs,
Computational Learning Theory,
Cambridge University Press, 1992
-
Bollobas,
Random Graphs,
Academic Press, 1985
-
Janson, Luczak, Rucinski,
Random Graphs,
John Wiley, 2000
-
Motwani, Raghavan,
Randomized Algorithms,
Cambridge University Press, 1995
English