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 'aklenke' gefolgt von einem Punkt und 'de'


Seminar: Diskrete Mathematik
Winter 2011/12                    

Zeit: 

Fr 10-12

Ort:

05-136

Beginn:

28.10.2011

Besprechung: 

Fr, 15.07.2011, 11:00 Uhr, Raum 04-522



Das wendet sich an Studierende der Mathematik 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 positionieren, so dass keine zwei auf derselben 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 derselben 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 Einführung in die diskrete Mathematik von Martin Aigner.

Literatur

Ablauf

Die Abgabe des Vortragsmanuskriptes erfolgt 14 Tage vor dem Vortrag. Die Vorbesprechung des Vortrags erfolgt jeweils 10 Tage vor dem Vortrag, am Dienstag um 13:00 Uhr. Für den ersten Vortrag wird eine individuelle Vereinbarung getroffen.