Spezialvorlesung

Randomisierte Algorithmen

Wintersemester 2005/2006

Veranstalter:	Dr. Friedrich Eisenbrand
Vorlesung:	Mo 10:15-12:00, 304 OH 14
	Di 12:15-14, 104 OH14
Übung:	Mi 12:15-14:00, 304 OH 14
Beginn:	17. Oktober 2005
DPO 1996:	Die Vorlesung kann als Teil verschiedener Vertiefungsgebiete geprüft werden.
DPO 2001:	Die Vorlesung kann als Teil des Schwerpunktgebietes "Algorithmen, Komplexität und formale Modelle" geprüft werden.

Inhalt

Oft können algorithmische Probleme besonders einfach, elegant und effizient durch einen randomisierten Algorithmus gelöst werden. Im Gegensatz zu deterministischen Algorithmen hängt das Verhalten eines randomisierten Algorithmus nicht nur von seiner Eingabe ab, sondern auch von unabhängigen Münzwürfen oder Zufallszahlen. In der Vorlesung behandeln wir den Entwurf und die Analyse randomisierter Algorithmen anhand spezieller algorithmischer Probleme.
Es werden keine tieferen Kenntnisse in Wahrscheinlichkeitstheorie vorausgesetzt. Stattdessen werden wir die notwendige Theorie in Begleitung zu den behandelten Algorithmen entwickeln. Thematisch orientiert sich die Vorlesung stark an [1,2] und an Originalliteratur. Es wird ein vorlesungsbegleitendes, stichwortartiges Skript geben welches jedoch [1,2] nicht ersetzten soll.

Literatur

[1] R. Motwani und P. Raghavan Randomized Algorithms. Cambridge University Press, 1995.

[2] M. Mitzenmacher und E. Upfal Probability and Computing. Cambridge University Press, 2005.

Was wurde bisher gemacht

17. Oktober: MinCut, deterministische Algorithmen
19. Oktober:Randomized MinCut, Grundlagen, s-Algebra, W-Mass, …
24. Oktober: Zufallsvariable, Erwartungswert, Quicksort, MaxSat, Geometrische Verteilung, Coupon Sammler
26. Oktober: Markov Ungleichung, Definition lineares Programm
31. Oktober: Random Sampling, Clarkson's Algorithmus
7. November: Abstrakte Optimierungsprobleme, Kleinster umschliessender Kreis, Matousek, Sharir, Welzl
9. November: Subex LP
14. November: Varianz, Standardaweichung
15. November: Randomizierte Medianberechnung, Momenterzeugendenfunktion
21. November: Chernoff Schranken, Permutationsrouten auf dem Hypercube
28. November: Minimum Congestion Routing (Randomisiertes Runden)
29. November: Max-SAT, Set Cover (Randomisiertes Runden)
5. Dezember: Packungsprobleme, Nichtapproximierbarkeit von Clique, Independent Set und Packen
6. Dezember: Geburtstagsparadoxon, Balls in Bins, Bucket Sort
12. Dezember (Tobias Storch): Markov Ketten, 2-SAT, 3-SAT
13. Dezember (Tobias Storch): Klassifikation von Zustaenden und Markov-Ketten, Fundamentales Theorem ueber Markov-Ketten (ohne Beweis), Random Walks auf ungerichteten Graphen, s-t connectivity
2. Januar: Fingerprinting, randomisierter Algorithmus zum Test auf perfekte Matchings in allgemeinen Graphen
3. Januar: Primzahlen, Fermats kleiner Satz, Fermat Test
16. Januar: Primzahlen: Der starke Primzahltest (Miller Rabin)
17. Januar: Network Design, Steiner Baum, Connected Facility Location
23. Januar: Weiter mit Connected Facility Location und Virtual Private Network Design
24. Januar: Weiter mit Virtual Private Network Design
30. Januar: Min Conjestion im VPN Setting lösbar? Probabilistische Methode
31. Januar: Lovasz Local Lemma, Kantendisjunkte Wege, k-SAT
6. Januar: Verbesserte Approximationsalgorithme für VPND
7. Januar: Symmetrisches VPND, beste Baumlösungen, 2-Approximation und Diskussion von Forschungsfragen
Stichwortskript