Prof. Dr. Achim Klenke
Institut für Mathematik
Fachbereich Physik, Mathematik und Informatik
Johannes Gutenberg-Universität
Staudingerweg 9
55099 Mainz
Tel. 06131 39-22829
Fax 06131 39-20916
E-Mail "math" dann "at" und "klenke" gefolgt von einem Punkt und "de".


Seminar: Diskrete Mathematik
(in manchen Ankündigungen: "Seminar Stochastik")

Winter 2006/07

Zeit:  Do 10-12
Ort:
05-136
Beginn: 26.10.06
Besprechung:  Mi, 26.07.06, 12:15 Uhr, Raum 04-426


Das Seminar (Proseminar nach alter Nomenklatur) wendet sich an Studierende der Mathematik im Grundstudium bzw. im Bachelorstudiengang, die bereits die Einführung in die Höhere Mathematik gehört haben, sowie Kenntnisse in Analysis und linearer Algebra im Umfange einer weiteren Veranstaltung erworben haben. Das Schulwissen Stochastik kann hier und da nützlich sein, jedoch werden keine Vorlesungen zu diesem Thema vorausgesetzt.

Diskrete Mathematik beschäftigt sich unter anderem mit folgenden Fragen: Wie viele Stereoisomere des Pentanols gibt es? Auf wie viele Arten lassen sich auf einem Schachbrett acht ununterscheidbare Figuren postionieren, so dass keine zwei auf der selben Diagonalen, Waagerechten oder Senkrechten stehen (Acht-Damen-Problem)? Wie viele Möglichkeiten gibt es, vier rote, drei blaue und zwei grüne Perlen auf eine Kette zu ziehen? Unter welchen Bedingungen an einen endlichen bipartiten Graphen (ein Teil der Punkte ist rot gefärbt, die anderen blau; es gibt keine Kanten zwischen Punkten der selben Farbe, Beispiel: kubisches Gitter) gibt es ein "Matching", das heißt einen Teilgraphen, in dem  von jedem Punkt exakt eine Kante ausgeht (Heiratsproblem)? Und wie kann man mit einem Computer effizient ein solches Matching finden?

Wir werden in diesem Seminar die mathematischen Werkzeuge kennenlernen, die zur Beantwortung dieser Fragen gebraucht werden. Dazu gehören etwa: Abzählschemata, elementare Erzeugendenfunktionen, Rekursionen und Differenzengleichungen, Inklusions- Exklusionsformeln, Symmetriegruppen, Spannbäume von Graphen.

Das Seminar hält sich inhaltlich an die ersten Kapitel der sehr gut geschriebenen Einführung in die diskrete Mathematik von Martin Aigner.

Literatur