• Syllabus

Print View

1. Vorlesung DienstagTue Apr 19, 2022 02:15 PM -  | 03:45 PM

  • Überblick
  • Der reflektierte binäre Gray-Code g(k)
  • Linealfolge ρ(k)
  • Chinesische Ringe

2. Vorlesung DonnerstagThu Apr 21, 2022 02:15 PM -  | 03:45 PM

  • Analog-zu-Digital-Umwandlung: Ablesen von einem Rad
  • Binäre Graycodes mit besonderen Eigenschaften
  • Algorithmus für den binären reflektierten Graycode
  • Schleifenfreier Algorithmus für den reflektierten Graycode mit gemischter Basis (Ausarbeitung, auf Englisch)

3. Vorlesung DienstagTue Apr 26, 2022 02:15 PM -  | 03:45 PM

  • binäre Graycodes und der Turm von Hanoi
  • ternäre Graycodes und der Turm von Budapest (siehe weitere Verallgemeinerungen)
  • monotone Graycodes
  • Größe der Ebenen, Binomialkoeffizienten
  • Zerlegung in Pfade zwischen aufeinanderfolgenden Wegen

4. Vorlesung DonnerstagThu Apr 28, 2022 02:15 PM -  | 03:45 PM

  • monotoner Graycode nach Carla Savage und Peter Winkler (1985)
  • zyklische Vertauschung von Wörtern: Halsketten
  • einfacher Algorithmus zum Testen der Halsketteneigenschaft

5. Vorlesung DienstagTue May 03, 2022 02:15 PM -  | 03:45 PM

6. Vorlesung DonnerstagThu May 05, 2022 02:15 PM -  | 03:45 PM

  • De-Bruijn-Kreise: rekursive Konstruktion nach Lempel (1970), Python-Programm
  • Schieberegisterfolgen und primitive Polynome

7. Vorlesung DienstagTue May 10, 2022 02:15 PM -  | 03:45 PM

  • Primwörter (Lyndon-Wörter) und lexikographisch kleinster de-Bruijn-Kreis
  • Halsketten, Halskettenstücke, und Primwörter
  • Algorithmus von Fredericksen und Maiorana

8. Vorlesung DonnerstagThu May 12, 2022 02:15 PM -  | 03:45 PM

  • Permutationen: lexikographische Erzeugung (gleiche Symbole sind erlaubt)
  • Erzeugung durch benachbarte Vertauschungen; der Johnson-Trotter-Algorithmus, plain changes

9. Vorlesung DienstagTue May 17, 2022 02:15 PM -  | 03:45 PM

  • Symmetrische Kettenzerlegung
  • Lernen einer monotonen Booleschen Funktion
  • ausgeglichene Klammerfolgen, Interpretation der Ketten als Klammerfolgen

10. Vorlesung Donnerstag (entfällt)Thu May 19, 2022 02:15 PM -  | 03:45 PM

  • Lineare Erweiterungen einer Halbordnung (topologische Sortierungen)
  • Kombinationen, kolexikographische Reihenfolge, Rangbestimmung
  • Kombinationen, Drehtürfolgen
  • cool-lex Erzeugung

11. Vorlesung DienstagTue May 24, 2022 02:15 PM -  | 03:45 PM

  • Kombinationen, kolexikographische Reihenfolge, Rangbestimmung
  • Kombinationen, Drehtürfolgen

Vorlesung DonnerstagThu May 26, 2022 02:15 PM -  | 03:45 PM

Vorlesung DienstagTue May 31, 2022 02:15 PM -  | 03:45 PM

  • cool-lex Erzeugung,
  • cooler-lex-Erzeugung für alle Bitfolgen, und coolest-lex-Erzeugung für Bitfolgen mit eingeschränktem Gewicht

Vorlesung DonnerstagThu Jun 02, 2022 02:15 PM -  | 03:45 PM

Vorlesung DienstagTue Jun 14, 2022 02:15 PM -  | 03:45 PM

  • Klammerfolgen, geordnete Bäume, und Binärbäume
  • Entsprechung mit Gitterpfaden und Dyckpfaden
  • Catalansche Zahlen Cn und ballot-Zahlen Cpq für 0≤p≤q
  • lexikographische Erzeugung
  • Rangbestimmung und inverse Rangbestimmung in einem gerichteten azyklischen Graphen
  • Erzeugung zufälliger dekorierter Binärbäume nach Rémy (1985)

Vorlesung DonnerstagThu Jun 16, 2022 02:15 PM -  | 03:45 PM

  • Hamiltonkreise in Leitern
  • die Transfermatrixmethode

Vorlesung DienstagTue Jul 05, 2022 02:15 PM -  | 03:45 PM

  • Spannbäume und Hamiltonkreise in Leitern
  • die Transfermatrixmethode (dynamische Programmierung)
  • Rekursionsgleichung, Satz von Cayley-Hamilton
  • Satz von Perron-Frobenius, Collatz-Wielandt-Ungleichungen

Vorlesung DonnerstagThu Jul 07, 2022 02:15 PM -  | 03:45 PM

  • teilweise Polyominos, Zustände
  • kreuzungsfreie Permutationen und Motzkinpfade

Vorlesung DonnerstagThu Jul 14, 2022 02:15 PM -  | 03:45 PM

  • Supermultiplikative Funktionen, Feketes Lemma
  • Kodierung von Polyominos, exponentielle obere Schranke
  • Klarners Konstante λ
  • Der Algorithmus von D. H. Redelmeier (1981). Zusammenhängende Teilgraphen mit einem gegebenen Startknoten

Vorlesung DienstagTue Jul 19, 2022 02:15 PM -  | 03:45 PM

  • Satz von Perron-Frobenius, Collatz-Wielandt-Ungleichungen: Beweise

Vorlesung DonnerstagThu Jul 21, 2022 02:15 PM -  | 03:45 PM

  • umgekehrte Suche (reverse search, Avis und Fukuda)
  • Beispiel: Triangulierungen einer ebenen Punktmenge
  • lexmax Gradfolge als Zieltriangulierung.