Vorlesung Randomisierte Algorithmen
Informatik-Vorlesung für das Diplom-Haupt- und Masterstudium im Wintersemester. Sie ist prüfbar im Rahmen der Vertiefungsgebiete Parallelverarbeitung und Algorithmentechnik, aber auch für Mathematiker etc.
Seit Wintersemester 2011/2012 wird diese Vorlesung mit Übung angeboten und es sind 5 Leistungspunkte zu erwerben.
Aktuell
Achtung: Wegen Krankheit muss die Vorlesung am 24. Januar entfallen
Die nächste Übung findet nicht am 28.1. statt, sondern wird verschoben auf 4. Februar 2013.
Achtung: Die Vorlesung am 31. Januar findet in Raum -108 statt.
Termine im Wintersemester 2012/2013
Die Vorlesungstermine sind:
- Vorlesung: donnerstags, 11:30 - 13:00 im Hörsaal -101 (Geb. 50.34).
Beginn ist am 18. Oktober 2012. - Übung: montags, 11:30 - 13:00 im Hörsaal -101 (Geb. 50.34) etwa vierzehntätig
Die nächste Übung ist am 28. Januar 2013.
Überblick über den Inhalt
Randomisierte Algorithmen sind nicht deterministisch. Ihr Verhalten hängt vom Ausgang von Zufallsexperimenten ab. Diese Idee wurde erstmals von Rabin durch einen randomisierten Primzahltest bekannt. Inzwischen gibt es für eine Vielzahl von Problemen randomisierte Algorithmen, die (in dem einen oder anderen Sinne) schneller sind als deterministische Verfahren. Außerdem sind randomisierte Algorithmen mitunter einfacher zu verstehen und zu implementieren als "normale" (deterministische) Algorithmen.
Im Rahmen der Vorlesung werden nicht nur verschiedene "Arten" randomisierter Algorithmen (Las Vegas, Monte Carlo, …) vorgestellt, sondern auch die für die Analyse ihrer Laufzeit notwendigen wahrscheinlichkeitstheoretischen Grundlagen weitgehend erarbeitet und grundlegende Konzepte wie Markov-Ketten behandelt. Da stochastische Methoden in immer mehr Informatikbereichen von Bedeutung sind, ist diese Vorlesung daher auch über das eigentliche Thema hinaus von Nutzen.
Hier ein kurzer Überblick über den voraussichtlich in der Vorlesung behandelten Stoff.
- Einleitung
- Erste Beispiele
- probabilistische Komplexitätsklassen
- Routing in Hyperwürfeln
- zwei spieltheoretische Aspekte
- randomisierte Graph-Algorithmen
- Random Walks
- Markov-Ketten
- randomisiertes Approximieren
- schnell mischende Markov-Ketten
- Hashing
- randomisierte Online-Algorithmen
- Erzeugung von Pseudozufallszahlen
Elektronische Kurswaren
Es gibt auch alle Kapitel zusammen in einer Pdf-Datei.
Im Laufe der kommenden Wochen wird es hier auch Hinweise zu den Lösungen der Aufgaben geben.
| Kap. 1 | Kap. 2 | Kap. 3 | Kap. 4 | Kap. 5 | Kap. 6 | |
| Folien | Folien | Folien | Folien | Folien | Folien | |
| Skript | Skript | Skript | Skript | Skript | Skript | |
| Aufgabe | Aufgaben | Aufgaben | Aufgaben | Aufgaben | Aufgaben | |
| Lösungen | ||||||
| Kap. 7 | Kap. 8 | Kap. 9 | Kap.10 | Kap.11 | Kap.12 | Kap.13 |
| Folien | Folien | Folien | Folien | Folien | Folien | Folien |
| Skript | Skript | Skript | Skript | Skript | Skript | Skript |
| Aufgaben | Aufgaben | Aufgaben | Aufgaben | Aufgaben | ||
| Lösungen | Lösungen | Lösungen | Lösungen | Lösungen |