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.