Forschungsinstitut für Diskrete Mathematik

Vorlesung "Einführung in die Diskrete Mathematik"

Wintersemester 2008/09

Diese Vorlesung eignet sich sowohl für den Einstieg in den Bereich C im Rahmen des Bachelorstudiengangs Mathematik (3. Semester) als auch für das 5. Semester des Diplomstudiengangs Mathematik. Ferner kann die Vorlesung im Rahmen der Studiengänge Informatik besucht werden. Nähere Informationen hier.

In dieser Vorlesung werden grundlegende Themen der diskreten Mathematik behandelt. Der Schwerpunkt liegt dabei auf Netzwerkproblemen. Nach einer kurzen Einführung in Graphen und elementare Algorithmen werden die Themen Bäume, Branchings, Netzwerkflüsse, minimale Schnitte, Zusammenhang, kostenminimale Flüsse, Anwendungen von Netzwerkflüssen, bipartites Matching, Multicommodity flows und disjunkte Wege sowie NP-Vollständigkeit behandelt.

Die Vorlesung findet in deutscher Sprache statt und basiert zum großen Teil auf folgendem Buch:

• B. Korte, J. Vygen : Combinatorial Optimization: Theory and Algorithms. Springer, Fourth edition 2008

Weitere empfehlenswerte Bücher für Teile der Vorlesung:

• R. Diestel : Graphentheorie. Springer, Dritte Auflage 2006
• R. Ahuja, T. Magnanti, J. Orlin : Network Flows. Prentice-Hall 1993
• T.H. Cormen, C.E. Leiserson, R.L. Rivest, C. Stein : Introduction to Algorithms. McGraw-Hill 2002
• D. Jungnickel : Graphs, Networks and Algorithms. Springer 1999
• W. Cook, W. Cunningham, W. Pulleyblank, A. Schrijver : Combinatorial Optimization. Wiley 1997
• A. Schrijver : Combinatorial Optimization: Polyhedra and Efficiency. Springer 2003

Zeit:	Dienstags und donnerstags 16-18 Uhr (c.t.)
Ort:	Großer Hörsaal der Mathematik, Wegelerstr. 10
Übungen:	2st, n.V. Weitere Informationen auf der Webseite der Übungen

Modulprüfung: Die Klausur fand am Mittwoch, den 25. Februar 2009 um 9 Uhr c.t. im Großen und Kleinen Hörsaal der Wegelerstraße 10 statt. Hier sind die Aufgaben und Lösungen. Die Ergebnisse stehen fest und wurden von den Prüfungsämtern bekannt gegeben. Eine Einsicht in die Klausuren war am 5. März 2009 von 9 Uhr 30 bis 12 Uhr in meinem Büro möglich. Der zweite Prüfungstermin besteht aus mündlichen Prüfungen im Zeitraum 12. bis 24. März 2009.