Randomisierte Algorithmen 2009 (Prof. Bandt / Prof. Funke)

Vorlesungen

Teilnehmer

Voraussetzungen

Literatur

Inhalte

• 1. Monte Carlo und Las Vegas Algorithmen (Funke 8./9.4.)
  A Kürzester Abstand in einer ebenen Punktmenge, B Einfacher min-cut Algorithmus
• 2. Abweichungen von der mittleren Laufzeit (Bandt 14./15.4.)
  A Heirats- und Zuordnungsprobleme, B Das Sammlerproblem
• 3. Neustart-Algorithmen und rekursiver Aufruf (Funke 21./22.4.)
  A Neustart vermeidet lange Laufzeiten, B Vergleich von Matrizen, C Median-Algorithmus, D Bestimmung des Elements vom Rang k, E Quicksort
• 4. Spieltheorie und untere Laufzeitabschätzung (Bandt 28.4.-5.5.)
  A Berechnung von Spielbäumen, B Das Minimax-Theorem für Nullsummenspiele, C Untere Schranken für zufällige Algorithmen
• 5. Randomisierung in der algorithmischen Geometrie (Funke 5.-27.5.)
  A Berechnung der konvexen Hülle, B Delaunay-Triangulierung, C Polygon-Triangulierung, D Minimal enclosing disk, E LP-Typ Probleme
• 6. Die probabilistische Methode (Bandt 9.6.-16.6.)
  A Prinzip und einfache Beispiele, B Kombinatorische Anwendungen, C Lovasz Local Lemma
• 7. Irrfahrten (Bandt 17.6.-30.6.)
  A Eindimensionale Irrfahrt und 2-SAT, B Irrfahrt auf Graphen und der Page-Rank-Algorithmus, C Irrfahrten und elektrische Netzwerke, D Expander-Graphen
• 8. Sublineare Algorithmen/Streaming Algorithmen/Property Testing (Funke 01.07.-14.07.)
  A Zählen von Zusammenhangskomponenten, Schätzen des Gewichts eines minimalen Spannbaums, B Streaming Algorithmus: Verschiedene Elemente zählen, C Property Testing: CLIQUE, Zusammenhang eines Graphen
• 9. Zero Knowledge Proofs (Funke 14.07.)
  A Graph Isomorphie