Probabilistische Algorithmen
CITS » Lehre » Sommersemester 2016

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)

Vorlesung
Dozent Zeit Raum Erstmals am
Prof. A. May dienstags, 10:00 - 12:00 NAFOF 02/257
Übungen
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