Übersicht: alle Semester Wintersemester 2004/05

Vorlesung Betriebssysteme (4V+2Ü) (B) [B1] Mo, Mi 11-13, HS A (Prof. Dr. Christoph Strelen) Übungen: Mo 13-15, SR N102 (Prof. Dr. Christoph Strelen u.M.) Algorithmen auf Strings (4V+2Ü) (A) [A1] Mo 15-17, Mi 11-13, HS A207 (Prof. Dr. Norbert Blum) Übungen: n.Vereinb. (Prof. Norbert Blum)

Vorlesung (Hauptstudium)

Randomisierte und Approximative Algorithmen für NP-Harte Berechnungsprobleme

Prof. Dr. M. Karpinski

Zeit, Ort	Di, Do 11-13, HS 1
Semesterwochenstunden	4V + 2Ü
Beginn	12.10.2004
Übungen	n.Vereinb. (Prof. Dr. Karpinski u. Mitarbeiter)
Voraussetzungen	Vordiplom in Informatik, Mathematik oder Physik, Interesse an algorithmischen Fragestellungen.
Nachfolgeveranstaltungen	Projektgruppe "Effiziente Approximationsalgorithmen: Implementation und Analyse", Seminar "Schnelle Parallele Algorithmen"
Bereich (alte DPO)	A,C
Bereich (neue DPO)	A1
Prüfungsmöglichkeiten	Diplomprüfung A oder C
Literatur	S. Arora: Probabilistic Checking of Proofs and Hardness of Approximation Problems ECCC Books on Complexity, 1995, http://www.eccc.uni-trier.de/eccc-local/ECCC-Books/sanjeev_book_readme.html G. Ausiello, P. Crescenzi, G. Gambosi, V. Kann, A. Marchetti-Spaccamela, M. Protasi: Complexity and Approximation, Springer 1999 P. Crescenzi, V. Kann: A compendium of NP optimization problems http://www.nada.kth.se/~viggo/problemlist/compendium.html D. Hochbaum: Approximation Algorithms for NP-hard Problems PWS Publishing, 1997 M. Karpinski: Vorlesungsskript: Effiziente Algorithmen und Komplexitätstheorie (Ausgearbeitet von K. Werther) Universität Bonn, 1998 M. Karpinski: Vorlesungsskript: Randomisierte und approximative Algorithmen für harte Berechnungsprobleme (Ausgearbeitet Vorlesungsskript: Randomisierte und approximative Algorithmen für harte Berechnungsprobleme (Ausgearbeitet von C. Dorgerloh, C. Günzel, J. Wirtgen und P. Wegner) Universität Bonn, 2000 M. Karpinski, W. Rytter: Fast Parallel Algorithms for Graph Matching Problems Oxford University Press, 1998 R. Motwani, P. Raghavan: Randomized Algorithms Cambridge University Press, 1995 C. Papadimitriou: Computational Complexity Addison-Wesley, 1994 V.V. Vazirani: Approximation Algorithms, Springer, 2001