Forschungsinstitut für Diskrete Mathematik

Vorlesung "Einführung in die Diskrete Mathematik"

Wintersemester 2013/14

Diese Vorlesung eignet sich für das 3. Semester im Rahmen des Bachelorstudiengangs Mathematik und ist als Einstieg in den Bereich C (Diskrete Mathematik) gedacht. Ferner kann die Vorlesung im Rahmen des Bachelorstudiengangs Informatik besucht werden. Nähere Informationen hier.

In dieser Vorlesung werden grundlegende Themen der Diskreten Mathematik behandelt. Der Schwerpunkt liegt dabei auf algorithmischen Problemen. Zu den Themen gehören Eulertouren und Hamiltonkreise, Bäume, Branchings, Netzwerkflüsse, minimale Schnitte, Zusammenhang, kostenminimale Flüsse, bipartites Matching und Anwendungen, Multicommodity flows und disjunkte Wege sowie NP-Vollständigkeit.

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

• B. Korte, J. Vygen : Kombinatorische Optimierung: Theorie und Algorithmen. Springer, 2. Auflage 2012

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

• R. Diestel : Graphentheorie. Springer, Vierte Auflage 2010
• T.H. Cormen, C.E. Leiserson, R.L. Rivest, C. Stein : Introduction to Algorithms. MIT Press, Third Edition 2009
• R. Ahuja, T. Magnanti, J. Orlin : Network Flows. Prentice-Hall 1993
• D. Jungnickel : Graphs, Networks and Algorithms. Springer, Fourth Edition 2013
• W. Cook, W. Cunningham, W. Pulleyblank, A. Schrijver : Combinatorial Optimization. Wiley 1997
• A. Schrijver : Combinatorial Optimization: Polyhedra and Efficiency. Springer 2003

Die Vorlesung setzt mathematische Grundbegriffe sowie Grundlagen aus "Algorithmische Mathematik I" voraus (siehe insbesondere die Kapitel 6 und 7, aber auch Kapitel 9 und 10 meines Vorlesungsskripts zu dieser Vorlesung im Wintersemester 2012/13). Auf einigen Übungszetteln werden auch Programmieraufgaben sein. Hierbei sollen die in meiner o.g. Vorlesung vorgestellten C++-Programme (insbesondere die Klassen Graph bzw. Weighted_Graph, aber evtl. auch z.B. BFS, Dijkstra) benutzt werden. Hier ist die Webseite der genannten Vorlesung samt Skript und Programmen. Wer meine Vorlesung im letzten Wintersemester nicht besucht hat, macht sich am besten vorab mit den genannten Themen und Programmen vertraut.

Zeit und Ort:	Dienstags 16-18 großer Hörsaal und donnerstags 16-18 Uhr kleiner Hörsaal, jeweils c.t., Wegelerstr. 10
Übungen:	siehe hier

Modulprüfung:	Die beiden Klausuren finden am 11.2. ab 9:30 Uhr und am 26.3. ab 14:30 Uhr statt.
	Die erste Klausur findet im Alfred-Philippson-Hörsaal, Geographie, Meckenheimer Allee 166/Wolfgang-Paul-Allee (A-H), im Kleinen Hörsaal Wegelerstr. 10 (J-P) und im Großen Hörsaal Wegelerstr. 10 (R-Z) statt. Die zweite Klausur findet im großen Hörsaal Wegelerstr. 10 statt. Finden Sie sich zu den genannten Zeiten (s.t.) am dem Anfangsbuchstaben Ihres Nachnamens entsprechenden Hörsaal ein; die Klausur beginnt ca. 10 Minuten später.
	Die Bearbeitungszeit beträgt 120 Minuten. Es sind keine Hilfsmittel erlaubt. Mitzubringen sind Schreibgeräte, Studentenausweis und Personalausweis/Reisepass. Papier wird gestellt.
Klausureinsicht:	Hier ist die erste Klausur samt Lösungen. Die Ergebnisse sind auf BASIS eingetragen und so ausgefallen.
	Am 21.2. von 16:00 bis 17:30 Uhr (A-G: 16:00-16:30, H-O: 16:30-17:00, P-Z: 17:00-17:30) bzw. am 31.3. von 16:00 bis 17:00 Uhr besteht im Konferenzraum des Forschungsinstituts für Diskrete Mathematik die Gelegenheit zur Klausureinsicht; bringen Sie bitte Ausweise und ggfs. Vollmacht mit.