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 umgekehrt2. 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äufe3. 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 α-Sequenzen4. Vorlesung, Do. 27.04.2006
Obere Schranke für die Länge von α-Sequenzen α-Sequenzen und monotone Gray-Codes Konstruktion monotoner Gray-Codes5. 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 Graphen6. 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 Cayley7. 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 Polynome8. 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 &Omega9. Vorlesung, Di. 16.05.2006
Eindeutige Zerlegung von Strings in Primstrings Preprime Strings und Primstrings, Charakterisierung über n-Erweiterungen10. Vorlesung, Do. 18.05.2006
Erzeugen von Primstrings in lex-Ordnung Der de Bruijn Kreis der Primstrings Erzeugen von Permutationen Lexikographische Ordnung11. 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 unrank12. 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 P13. Vorlesung, Do. 01.06.2006
G(P) x K2 ist hamiltonsch G(P)2 ist hamiltonsch14. Vorlesung, Di. 06.06.2006
Randomisierte Algorithmen - Einleitung Diskrete Wahrscheinlichkeiten Beispiele15. 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 QuickSort17. Vorlesung, D0. 15.06.2006
Analyse von Randomisiertem QuickSort Aufbau eines Suchbaumes und Quicksort (Deferred Decissions) Anzahl der Einfügefolgen die einen gegebenen Suchbaum erzeugen18. Vorlesung, Di. 20.06.2006
Selection - Auswahl Deterministisch: Median of 5 Randomisiert - Pfad im Suchbaum Randomisiert - Sampling19. Vorlesung, Do. 22.06.2006
Randomisierte Suchbäume Erwartete Tiefe eines Elements Rotationen Heaps Treaps20. 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ädikat21. Vorlesung, Do. 29.06.2006
Inkrementelle Konstruktion der konvexen Hülle Generisch Vorsortiert: von links nach rechts Randomisiert: kanonische Kante22. 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 Sampling24. Vorlesung, Di. 18.07.2006
String Matching Einführung Problem und naive Methode Ideen zur Beschleunigung Der Z-Box Algorithmus Berechnung der Z-Boxen25. Vorlesung, Do. 20.07.2006
Anwendung der Z-Boxen auf allgemeines String Matching Randomisiertes Pattern Matching