Probabilistische Algorithmen
Mit einer anderen 2-stündigen Vorlesung zu kombinieren.
BSc Mod 9c: BSc Modul 9c; BSc NF 4: BSc NF Modul 4;
Modul1(G3); MSc Mod 2: Modul2(G3); MSc Mod 3:
Modul3(G3); MSc Mod 5: Modul 5, MSc NF 6 (4.5 CP)
| Dozent | Zeit | Raum | Erstmals am |
|---|---|---|---|
| Prof. A. May | dienstags, 10:00 - 12:00 | NAFOF 02/257 |
| Dozent | Zeit | Raum | Erstmals am |
|---|---|---|---|
| Robert Kübler | Di 16-18 | NA 5/64 | 19.04. |
Skript
Vollständiges Skript (19.07.2016)
| 01 PDF (11.04.) | Elementare Ws-Theorie, Unabhängigkeit, Probabilistische Gleichheitstests |
| 02 PDF (19.04.) | Matrix-Test, Mincut, Amplifikation, Zufallsvariable |
| 03 PDF (26.04.) | Linearität des Erwartungswerts, Jensen Ungleichung, Binomial- und geometrische Verteilung |
| 04 PDF (03.05.) | Coupon Collector, Quicksort, Markov, Varianz und Kovarianz, Chebyshev |
| 05 PDF (10.05.) | Randomisierter Median, Monte Carlo und Las Vegas |
| 06 PDF (24.05.) | Moment Erzeugendenfunktion, Poisson Probe, Chernoff Schranken |
| 07 PDF (25.05.) | Mengen Balancierung, Bälle-Urnen Modell, Bucket Sort, Poisson Verteilung |
| 08 PDF (07.06.) | Poisson Approximation für Bälle und Urnen, Anwendung Hashfunktion | 09 PDF (14.06.) | Probabilistische Methode, Cut-Berechnung, Derandomisierung, Sample & Modify | 10 PDF (21.06.) | Zufällige Graphen, 2. Moment Methode, Lovasz Local Lemma | 11 PDF (28.06.) | Markov Kette, Random Walk für 2-SAT und 3-SAT | 12 PDF (05.07.) | 3-SAT mit Reset, Gambler's Ruin, Random Walk auf Graphen, Überdeckungszeit | 13 PDF (12.07.) | Pfadsuche, Monte Carlo Methode, Approximationsschema FPRAS, DNF Counting | 14 PDF (19.07.) | Samplen aus Mengen, Markov Ketten Monte Carlo, uniforme unabhängige Mengen |
Voraussetzung
Einführung in die Wahrscheinlichkeitstheorie
Kommentar
Inhalt:
- Diskrete Zufallsvariablen und Momente
- Chernoff Schranken
- Bälle, Urnen und zufällige Graphen
- Probabilistische Methode
- Markovketten und Random Walks
- Entropie
- Monte Carlo Methode
- Universelle Hashfunktionen