Inhaltsverzeichnis

Kombinatorische Algorithmen

Sommersemester 2006
Stefan Felsner

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, Di. 18.04.2006 

  Einleitung
     Was sind kombinatorische Algorithmen?
  Erzeugen von n-Tupeln
     Binäre n-Tupel und binäres Zählen
     Verallgemeinerte Erzeugung durch Zählen
     Der standard Gray Code
     Berechnung von g(k) aus k und umgekehrt
2. Vorlesung, Do. 20.04.2006 
     Ein erster Gray-Code Algorithmus
     Ein `Loopless' Algorithmus für den standard Gray-Code
     Gray-Codes und Hamiltonkreise im Hyperwürfel
     Spezielle Bedingungen: Balanciertheit, Lange Läufe
3. Vorlesung, Di. 25.04.2006 
     Chromatische Zahl von Diagrammen
     Diagramme von kanonischen Intervall-Ordnungen
     α-Sequenzen und Färbungen von Diagrammen von Intervall-Ordnungen
     Konstruktion von langen α-Sequenzen
4. Vorlesung, Do. 27.04.2006 
     Obere Schranke für die Länge von α-Sequenzen
     α-Sequenzen und monotone Gray-Codes
     Konstruktion monotoner Gray-Codes
5. Vorlesung, Di. 02.05.2006 
     Lange Kreise zwischen benachbarten Rängen in Bn
     De Bruijn Kreise 
       Existenz von de Bruijn Kreisen
       Hamiltonkreise und Eulerkreise in de Bruijn Graphen
6. Vorlesung, Do. 04.05.2006 
     Anzahl von de Bruijn Kreisen
       Die Anzahl der Euler-Kreise in gerichteten Graphen
       Die Laplace Matrix eines gerichteten Graphen
       Die Anzahl der gewurzelten aufspannenden Bäume in gerichteten Graphen
       Matrix-Tree-Theorem und Satz von Cayley
7. Vorlesung, Di. 09.05.2006 
       Die Eigenwerte der Laplace Matrix von de Bruijn Graphen
       Die Anzahl von de Bruijn Kreisen
     Algorithmen für  de Bruijn Kreise
       Algebraisch
         Lineare Schieberegisterfolgen
         Primitive Polynome
8. Vorlesung, Do. 11.05.2006 
       Rekursiv
         Der Lempel Homomorphismus D: Bn --> Bn-1
         Liften von Wegen und Kreisen über den Lempel Homomorphismus
         Konkretes berechnen des Lifts
         Verknüpfen der beiden Lifts eines Euler Kreises in Bn-1
       Verketten von Primstrings
         Definition und erste Eigenschaften von Primstrings
         Die Anzahl der Primstrings der Länge n über &Omega
9. Vorlesung, Di. 16.05.2006 
         Eindeutige Zerlegung von Strings in Primstrings
         Preprime Strings und Primstrings,
           Charakterisierung über n-Erweiterungen
10. Vorlesung, Do. 18.05.2006 
           Erzeugen von Primstrings in lex-Ordnung
         Der de Bruijn Kreis der Primstrings
  Erzeugen von Permutationen
     Lexikographische Ordnung
11. Vorlesung, Di. 23.05.2006 
     Lexikographische Ordnung - Die Laufzeit
     MultiPermutationen erzeugen und Anwendungen
     Plain Changes, ein Gray-Code für Permutationen
        Der Permutaedergraph und die schwache Bruhat-Ordnung
        Rekursiver und iterativer Algorithmus
        Rank Und unrank
12. Vorlesung, Di. 30.05.2006 
     Lineare Erweiterungen und topologische Sorierungen
        Rekursives Erzeugen
        Iteratives Erzeugen
        Anwendung auf die Erzeugung anderer kombinatorischer Familien
     Der Graph G(P) der linearen Erweiterungen von P
13. Vorlesung, Do. 01.06.2006 
        G(P) x K2 ist hamiltonsch
        G(P)2 ist hamiltonsch
14. Vorlesung, Di. 06.06.2006 
  Randomisierte Algorithmen - Einleitung
     Diskrete Wahrscheinlichkeiten
        Beispiele
15. Vorlesung, Do. 08.06.2006 
        Erwartungswerte
        Unabhängigkeit
        Markov Ungleichung
     Links-Rechts Minima in Permutationen
        Erwartete Anzahl - Rückwärtsanalyse
        Abschätzungen für Abweichung
        (Markov, Chebyshev)
16. Vorlesung, Di. 13.06.2006 
       Höhere Momente
       Eine Abschätzung vom Chernoff Typ
     Links-Rechts Minima und Anzahl Zyklen
       Sterling Zahlen und deren erzeugende Funktion
   Randomisiertes Suchen und Sortieren
       Die Grundprobleme
       Randomisiertes QuickSort
17. Vorlesung, D0. 15.06.2006 
       Analyse von Randomisiertem QuickSort
       Aufbau eines Suchbaumes und Quicksort (Deferred Decissions)
       Anzahl der Einfügefolgen die einen gegebenen Suchbaum erzeugen
18. Vorlesung, Di. 20.06.2006 
     Selection - Auswahl
       Deterministisch: Median of 5
       Randomisiert - Pfad im Suchbaum
       Randomisiert - Sampling
19. Vorlesung, Do. 22.06.2006 
     Randomisierte Suchbäume
       Erwartete Tiefe eines Elements
       Rotationen
       Heaps
       Treaps
20. Vorlesung, Di. 27.06.2006 
       Erwartete Anzahl Rotationen je insert oder delete
       Erwartete Höhe randomisierter Suchbäume
   Geometrische Algorithmen
     Konvexe Hülle
       Das ccw Prädikat
21. Vorlesung, Do. 29.06.2006 
     Inkrementelle Konstruktion der konvexen Hülle
       Generisch
       Vorsortiert: von links nach rechts
       Randomisiert: kanonische Kante
22. Vorlesung, Di. 04.07.2006 
       Randomisiert: Verzweigungsstruktur
     Outputsensitive Methoden
       Chans Algorithmus
       Kirkpatrick und Seidel (Marriage before Conquest)
23. Vorlesung, Do. 06.07.2006 
     Brücke, ein LP in 2-Dimensionen
       Prune and Search
       Random Sampling
24. Vorlesung, Di. 18.07.2006 
   String Matching
     Einführung
       Problem und naive Methode
       Ideen zur Beschleunigung
     Der Z-Box Algorithmus
       Berechnung der Z-Boxen
25. Vorlesung, Do. 20.07.2006 
       Anwendung der Z-Boxen auf allgemeines String Matching
     Randomisiertes Pattern Matching

Zurück zur Vorlesungsseite.