Proseminar Zufallsgesteuerte Algorithmen

WS 1996/97

Prof. Dr. Gerhard Goos

Dr. Welf Löwe

Dr. Wolf Zimmermann

Sabine Glesner

Weitere Informationen können hier gefunden werden. Allgemeine Fragen bitte an Sabine Glesner richten.

Übersicht über Termine und Vorträge

1. Einleitungsvortrag
   Quicksort randomisiert, Minimaler-Schnitt-Algorithmus randomisiert, Las-Vegas- versus Monte-Carlo-Algorithmen, Beispiele
   Termin: 22.10.1996
   Vortragende: Sabine Glesner
2. Spieltheoretische Techniken
   Spielbaumauswertung, Minimax-Prinzip (Spieltheorie, Yao's Technik, Anwendung auf Zufallsalgorithmen, untere Schranke für Spielbaumauswertung)
   Termin: 5.11.1996
   Vortragender: Rubino Geiß
3. Momente und Abweichungen
   Berechnung von Abweichungswahrscheinlichkeiten (Belegungsprobleme, Markov- und Cebyshev-Ungleichung, randomisierte Auswahl, Zwei-Urnen-Ziehung, Coupon-Collector)
   Termin: 12.11.1996
   Vortragender: Michael Wenz
4. Randungleichungen
   Verteilung der Summe unabhängiger Zufallsvariablen, Chernoff-Schranke, Wegplanung in einem Parallelrechner, Verdrahtungsproblem
   Termin: 19.11.1996
   Vortragender: Andreas Lohr
5. Datenstrukturen I
   Kurze Wiederholung der deterministischen Datenstrukturen, Treaps, Skip Lists
   Termin: 26.11.1996
   Vortragender: Hans Kratz
6. Datenstrukturen II
   Hash Tabellen
   Termin: 3.12.1996
   Vortragender: Sebastian Klapp
7. Geometrische Algorithmen und Lineares Progammieren I
   Randomisierte inkrementelle Konstruktion, konvexe Hülle, Dualität, Halbraum-Schnitte, Delaunay-Triangulierung, Trapez-Dekomposition
   Termin: 10.12.1996
   Vortragender: Vesztergombi Gyorgy
8. Geometrische Algorithmen und Lineares Programmieren II
   Zufällige Ziehung, lineares Programmieren
   Termin: 17.12.1996
   Vortragender: Dan Gyorgy
9. Graphenalgorithmen
   Alle kürzesten Pfade, minimaler Schnitt, minimal spannende Bäume
   Termin: 7.1.1997
   Vortragender: Karsten Krutz
10. Parallele und verteilte Algorithmen
    PRAM-Modell, Sortieren auf einer PRAM, maximal unabhängige Mengen, perfekte Paarungen
    Termin: 14.1.1997
    Vortragender: Dennis Strein
11. Online Algorithmen
    Online Seitenverwaltung, Gegner-Modelle, Seitenverwaltung gegen fairen Gegner, adaptiver online Gegner, k-Server Problem
    Termin: 21.1.1997
    Vortragende: Daniela Genius
12. Markov-Ketten
    Einführung in die Theorie von Markov-Ketten, Anwendung an Beispielen
    Termin: 4.2.1997
    Vortragender: Robert-Michael Zeier