Forschungsinstitut für Diskrete Mathematik
Vorlesung "Diskrete Mathematik II"
Sommersemester 2004
Nachdem im ersten Teil des
zweisemestrigen Vorlesungszyklus "Diskrete Mathematik" Grundlagen
insbesondere aus der Graphentheorie gelegt wurden, aber auch z.B.
Netzwerkflüsse behandelt wurden, werden im zweiten
Teil Matching-Algorithmen, Matroide, und NP-schwere Probleme behandelt, für die man sich oft
mit Approximationsalgorithmen begnügen muss.
Die Vorlesung wird zum großen Teil auf folgendem Buch basieren:
- B. Korte, J. Vygen :
Combinatorial Optimization: Theory and Algorithms.
Springer-Verlag,
Zweite Auflage 2002
Weitere empfehlenswerte Bücher für Teile der Vorlesung (eine kleine Auswahl):
- A. Schrijver : Combinatorial Optimization: Polyhedra and Efficiency.
Springer 2003
- W. Cook, W. Cunningham, W. Pulleyblank, A. Schrijver : Combinatorial
Optimization. Wiley 1997
- M.R. Garey, D.S. Johnson: Computers and Intractability: A Guide to the Theory of
NP-Completeness. Freeman 1979
- C.H. Papadimitriou : Computational Complexity. Addison-Wesley 1994
- V.V. Vazirani : Approximation Algorithms. Springer 2001
- J.G. Oxley : Matroid Theory. Oxford University Press 1992
Vorkenntnisse: | Diskrete Mathematik I
|
Ort: | Gerhard-Konow-Hörsaal (im Arithmeum, Lennéstr. 2)
|
Zeit: | Dienstags und donnerstags 16-18 Uhr
|
Beginn: | voraussichtlich 20.4.2004
|
Übung: | Donnerstags 14-16 Uhr (Beginn: 29.4.2004)
|
Prof. Dr. J. Vygen