Universität Leipzig |
Institut für Informatik
Vorlesungsverzeichnis SS 2000 (IfI)
Kombinatorik auf endlichen Strukturen
Waldmann, Johannes
Teilnehmerkreis:
Schwerpunktvorlesung in Theoretischer Informatik,
für Studenten der Informatik oder Mathematik.
Übersicht:
Wir beobachten bei verschiedensten Gelegenheiten,
daß es keine "beliebig große" Unordnung gibt.
Sei P eine Eigenschaft von Objekten,
und size(X) die Größe des Objekts X. Oft gilt:
Für jede Zahl n existiert eine Zahl m,
so daß jedes Objekt X mit size(X) >= m
wenigstens ein Unter-Objekt Y mit P(Y) und size (Y) >= n enthält.
Die Gültigkeit solcher Aussagen hängt natürlich
von P und von der Unter-Objekt-Relation ab.
Ein tatsächliches Y mit P(Y) ist im Allgemeinen schwer in X zu lokalisieren.
Oft finden wir für m nur Schranken, die meist nicht scharf sind.
Ich möchte das an verschiedenen Beispielen erläutern:
- Grundlagen der Ramsey-Theorie (auf Graphen)
- Anwendungen und Erweiterungen der Ramsey-Theorie
(in Arithmetik und Geometrie)
- Wohl-Quasi-Ordnungen (WQO) auf Bäumen (Satz von Kruskal)
- Anwendungen von WQOs in der Termersetzung (Pfadordnungen)
- WQOs auf Graphen (Arbeiten von Robertson/Seymour)
- Vermeidbare Muster in unendlichen Wörtern (Thue-Wörter)
- Endlichkeits- und Regularitätsbedingungen für Monoide (Burnside-Probleme)
Wir erhalten so, aus einem speziellen Blickwinkel,
Einsichten in einige wesentliche Entwicklungen der diskreten Mathematik
und Theoretischen Informatik in den letzten 100 Jahren.
Wir sehen dabei viele harte Probleme (gelöste und ungelöste)
sowie sinnreiche kombinatorische Beweistechniken.
Literatur:
- Aigner, Ziegler: Proofs from The Book,
Springer, 1998, (Kapitel 20 und 21)
- Baader, Nipkow: Term Rewriting and All That,
Cambridge University Press, 1998 (Kapitel 5)
- Bollobas: Graph Theory,
Springer, 1979, (Kapitel 6)
- Diestel: Graphentheorie,
Springer, 1996, (Kapitel 6, 7 und 10)
- Graham, Rothshild, Spencer: Ramsey Theory,
Verlag John Wiley & Sons, 1990
- Lothaire: Algebraic Combinatorics on Words,
http://www-igm.univ-mlv.fr/~berstel/Lothaire/
- Luca, Varricchio:
Finiteness and Regularity in Semigroups and Formal Languages,
Springer, 1998
- Rozenberg, Salomaa (Hrsg.): Handbook of Formal Languages,
Springer, 1997 (Band 1, Kapitel 6 und 11)
Erwartete Vorkenntnisse:
Grundlagen in (diskreter) Mathematik und formalen Sprachen
Scheinvergabe:
Für das Lösen einiger Übungsaufgaben.
Sonstiges:
Weiter Informationen zur Vorlesung:
http://www.informatik.uni-leipzig.de/~joe/edu/ss00/kombinat/
Beschreibung editieren
Diese Seite wird direkt aus einer objektorientierten SGML-Datenbank extrahiert.
Dabei wird das von Sergej Melnik
in Java geschriebenes SGML-Management-Tool eingesetzt, das an der Abteilung
Datenbanken
entwickelt worden ist.