Vorlesung Randomisierte und Approximationsalgorithmen

Dozent

Professor Dr. Stephan Waack

Ort und Zeit

Vorlesung: dienstags 14-16 Uhr, IfI-Seminarraum 0.101

Beginn

14. 04. 2009

ECTS-Informationen

3 Credits, 2 SWS

Studienfächer

INF MSC ab 1

Module

Effiziente Algorithmen (M.Inf.112), Vertiefung Theoretische Informatik (M.Inf.113)

Kommentar

Diese Vorlesung wird im Rahmen Masterstudienganges für Angewandte Informatik gehalten. Sie ist für Studierende geeignet, die sich mit Kerninformatik beschäftigen. Bachelor-Studierende höherer Fachsemester sind willkommen.

Behandelt werden voraussichtlich:

• Randomisierte Algorithmen: z.B. Primzahltest, Fingerabdrucktechniken
• Approximationsalgorithmen für NP-harte Probleme
• Randomisierte Verfahren zum Entwurf von Approximationsalgorithmen

Literatur

1. R. Wanka, Approximationsalgorithmen, Teubner-Verlag 2006.
2. T. H. Cormen, C. E. Leiserson, R. L. Rivest, Introduction to Algorithms, MIT Press, 2001.
3. J. Hromkovic, Algorithmics for Hard Problems, Springer Verlag, 2001.
4. J. Hromkovic, Theoretical Computer Science, Springer Verlag, 2003.
5. I. Wegener, Effiziente Algorithmen für grundlegende Funktionen, Teubner Verlag, 1989.
6. Neu: K. Jansen, M. Margraf, Approximative Algorithmen und Nichtapproximierbarkeit, de Gruyter, 2008.