Algorithmische Kombinatorik |
Peter Paule
326.246, WS 2000/2001
Mi 8:30-10:00, T 711,
Analysis I & II, Lineare Algebra I & II
Vermittlung der algorithmischen Grundwerkzeuge für das Lösen von Abzählproblemen.
Enumerative Kombinatorik zerfällt i.w. in zwei Problemkreise: in Abzähltheorie (liefert Anzahlformeln, z.B. kompliziert gebaute Summationen) und in Techniken zur Formel-Manipulation (z.B. zur Vereinfachung von Summen über Binomialkoeffizienten).
Der Schwerpunkt der Vorlesung liegt auf Abzähltechniken im allgemeinen, unter Berücksichtigung von konstruktiven Techniken (Computeralgebra). Im ersten Teil der Vorlesung wird in die wichtigsten Grundbegriffe der Kombinatorik eingeführt (erzeugende Funktionen, spezielle Zahlfolgen wie etwa Stirlingzahlen, Rekursionen, u.s.w.).
Im zweiten Teil der Vorlesung wird auf verschiedene Probleme der algebraischen Abzähltheorie eingegangen, z.B. Konstruktion bzw. Auflistung kombinatorischer Objekte wie etwa Permutationen, Partitionen oder Graphen. Insbesondere wird in Grundlagen der sog. Polya-Theorie eingeführt. (Typische Anwendungen behandeln z.B. verschiedene Färbungen geometrischer Objekte oder das Abzählen von chemischen Molekülen.)
Neben Originalarbeiten werden Abschnitte aus folgenden Büchern diskutiert: