Diskrete Mathematik beschäftigt sich vor allem mit endlichen, höchstens
abzählbar unendlichen Mengen. Sie ist ein recht junges Gebiet, das durch
die Entwicklung der Computer stark befördert wurde. Einen einheitlichen
Kanon eines Kurses Diskrete Mathematik gibt es nicht. Das mag daran
liegen, dass es mehr um konkrete Probleme, die sich mit geringen
Vorbereitungen formulieren lassen, als um die Entwicklung einer
ausgefeilten Theorie geht.
Im Laufe des Kurses werden wir uns mit verschiedenen Objekten
beschäftigen, diese zählen und miteinander in Verbindung bringen. Diese
Objekte stammen aus der Graphentheorie, Zähltheorie, projektiven
Geometrie, sind Designs, Färbungen oder Codes. Dabei werden Ansätze aus
der Geometrie, Algebra aber auch aus der Analysis verwendet. Darüber
hinaus werden Anwendungen unter anderem in der Codierung, im
Schaltungsdesign oder in der Komplexitätsanalyse betrachtet.
Als Basistext benutzen wir ausgewählte Kapitel des Buches "A course in
combinatorics" von J.H. van Lint und R.M. Wilson (2. Auflage). Themen
werden sein:
1.Systeme verschiedener Repräsentanten, der Satz von Dilworth und extremale Mengentheorie (Kapitel 5-6)
2.Das Prinzip der Inklusion und Exklusion; Inversionsformeln, Permanenten (Kapitel 10-11)
3.Elementare Abzählprobleme; Stirling Zahlen, Rekursionen und erzeugende Funktionen (Kapitel 13-14)
4.Partitionen, (0,1)-Matrizen (Kapitel 15-16)
5.Lateinische Quadrate, Hadamard Matrizen, Reed-Muller Codes (Kapitel 17-18)
6.Designs, stark reguläre Graphen und Teilgeometrien (Kapitel 19,21)
7.Orthogonale Lateinische Quadrate, projektive und kombinatorische Geometrien (Kapitel 22-23)