Forschungsinstitut für Diskrete Mathematik

Vorlesung "Einführung in die Diskrete Mathematik"

Wintersemester 2016/17

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 und des Lehramtstudiums 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 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:

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

Die Vorlesung setzt mathematische Grundbegriffe sowie Grundlagen aus "Algorithmische Mathematik I" voraus; insbesondere zu Graphen und elementaren Algorithmen.

Zeit und Ort:	Dienstags und donnerstags 16-18, jeweils c.t., Gerhard-Konow-Hörsaal (im Arithmeum, Lennéstr. 2)
Übungen:	zweistündig, nach Vereinbarung

• Die Analyse der Union-Find Datenstruktur findet sich hier: Raimund Seidel and Micha Sharir: "Top-Down Analysis of Path Compression", SIAM J. Comput., 34(3), 515–525., siehe auch das Vorlesungsskript von Jeff Erickson
• Minimum Ratio Cycle Problem: Nimrod Megiddo: "Combinatorial Optimization with Rational Objective Functions", Mathematics of Operations Research 4(4), 1979, 414-424
• Link zu einem Paper, das den Inhalt der Weihnachtsvorlesung behandelt
• Folien zur Modellierung einer 2-Band-Turingmaschine durch eine 1-Band-Turingmaschine (aus der Vorlesung vom 10.1.2017)