Inhaltsverzeichnis

Graphen, Zufall, Algorithmen

Sommersemester 2004
Stefan Felsner

Vorlesungsdetails: 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 , 10 , 11 , 12 , 13 , 14 , 15 , 16 , 17 , 18 , 19 , 20 , 21 , 22 , 23 , 24 , 25 ,

1. Vorlesung, Mi. 14.4.2004 

   Einleitung
      Wozu Zufall gut ist, einige Beispiele
      Der Fahrplan für die Vorlesung
   Diskrete Wahrscheinlichkeit
      Wahrscheinlichkeitsraum
      Zufallsvariable
2. Vorlesung, Fr. 16.4.2004 
      Erwartungswert
   Linearität des Erwartungswerts
      Turniere mit vielen Hamilton-Pfaden
   Max-Cut
      Monte Carlo und Las Vegas Algorithmen
3. Vorlesung, Mi. 21.4.2004 
      Bedingte Wahrscheinlichkeit
      Derandomisierung (Methode der bedingten Wahrscheinlichkeiten)
         - am Beispiel Max-Cut
      Max-Cut Algo. von Goemans-Willamson (Skizze)
4. Vorlesung, Fr. 23.4.2004 
   Min-Cut
     Problembeschreibung und Flüsse
     Randomisierte Kantenkontraktionen
     Laufseit und Erfolgswahrscheinlichkeit
     Deterministisches Min-Cut ohne Flüsse
         MA-Ordnungen
5. Vorlesung, Mi. 28.4.2004 
   Markov Ungleichung
   Links-Rechts Minima von Permutationen
     Chebyshev Ungleichung
     Eine Chernoff Abschätzung
6. Vorlesung, Fr. 30.4.2004 
     Stirling Zahlen
     Erzeugende Funktion
   Grosse Abweichungen
     Höhere Momentungleichungen
     Die/eine Chernoff-Schranke
7. Vorlesung, Mi. 5.5.2004 
   Cupon Collector

     Präsentation der Fak. II zum Feier
     125 Jahre Königliche Technische Hochschule
8. Vorlesung, Fr. 7.5.2004 
   Stabile Hochzeiten
     Der Gale-Shapley Algorithmus
     Average case Analyse
   Ramsey Zahlen
9. Vorlesung, Mi. 12.5.2004 
   Ramsey Zahlen
     obere Schranke: induzierte Färbung
     untere Schranke: probabilistische Methode
     leichte verbesserung: deletion method
   Graphen mit grosser Färbungszahl und grosser Taillienweite
10. Vorlesung, Fr. 14.5.2004 
   Evolution und Schrankenfunktionen
   - Methode der 2ten Momente
     Dreiecke
     balancierte Subgraphen
     Cliquen
11. Vorlesung, Mi. 19.5.2004 
Datenstrukturen und Algorithmen 
   Sortieren und suchen
     R-Quicksort
     R-SearchTreeSort
12. Vorlesung, Fr. 21.5.2004 
     R-Selection
     LazySelect
   Suchbäume
13. Vorlesung, Mi. 26.5.2004 
     Erwartete Knotentiefe
     Heaps
   Treaps
     Die fundamentalen Operationen
14. Vorlesung, Fr. 28.5.2004 
     Erwartete Anzahl von Rotationen
 Geometrische Algorithmen
   Konvexe Hülle
     Das cco Prädikat
     Jarvis wrap
     Inkrementelle Konstruktion
15. Vorlesung, Mi. 2.6.2004 
     Varianten der inkrementellen Konstruktion
     - vorsortieren
     - kanonische Kanten verwalten
     - Verzweigungsstruktur
     Output sensitive Methoden
     - Chans Methode
16. Vorlesung, Fr. 4.6.2004 
   
     - Chans Methode
     - Marriage before Conquest 
     Das Brückenproblem und Lineares Programmieren
     - Sampling LP (2 dim)
17. Vorlesung, Mi. 9.6.2004 
   
     - Incremental LP (2 dim)
     LP-Type Problems
     MiniBall in d-dim
18. Vorlesung, Mi. 23.6.2004 
   
 On-Line Algorithmen
      On-Line chromatische Zahl von Wäldern
         von bipartiten Graphen
      On-Line Antikettenzerlegung von Ordnungen
19. Vorlesung, Fr. 25.6.2004 
   
      On-Line Kettenzerlegung von Ordnungen
         Ordnungen die on-line up-growing präsentiert werden
      On-Line Kettenzerlegung von Intervallordnungen
         3ω -2 als obere und untere Schranke
20. Vorlesung, Mi. 30.6.2004 
   
      First-Fit benötigt für Intervallgraphen höchstens 8ω Farben
 Markov-Ketten und Zufallsspaziergänge
      Ein Algorithmus für 2-SAT
21. Vorlesung, Fr. 1.7.2004 
   
      Markov-Ketten: Definitionen
      Hauptsatz
      Random Walks auf ungerichteten Graphen
      Der Lollipop-Graph
22. Vorlesung, Mi. 7.7.2004 
  
      Random Walks
         Trefferzeit (hitting time)
         Pendelzeit  (commute time)
         Überdeckungszeit (cover time)
23. Vorlesung, Fr. 9.7.2004 
   
     Elektrischen Netze
     Pendelzeit und effektiver Widerstand in elektrischen Netzen
     Cover time und Bäume
     Cover time und max/min hitting time
24. Vorlesung, Mi. 14.7.2004 
   
     Markov Chain Monte Carlo
     (Erzeugen zufälliger Objekte)
     Mischzeit und Variationsdistanz 
     Methoden zur Abschätzung der Variationsdistanz
     λ_2, conductance, congestion, coupling, stopping time
25. Vorlesung, Fr. 16.7.2004 
   
     Die Methoden im Einsatz:
         Random walk auf dem Hyperwürfel
     Das Markov Chain Tree Theorem
     Zufällige aufspannende Bäume

Zurück zur Vorlesungsseite.