Höhere Algorithmik
Inhalt
• Einführung: Das Erfüllbarkeitsproblem, 2-Sat, probabilistischer Algorithmus für 2-SAT.
• NP-Vollständigkeit: Bedeutung, Beispiele.
• Graph Algorithmen: Minimaler Schnitt, kürzeste Wege zwischen allen Knotenpaaren, Matching, das Heiratsproblem, 3-Färbarkeit.
• Algebraische und zahlentheoretische Algorithmen: Multiplikation großer Zahlen, Matrizen-Multiplikation, modulare Exponentiation, Faktorisierung: Pollard's rho und (p-1) Algorithmen, quadratisches Sieb.
• Approximationsalgorithmen: 0/1 Rucksack, Max-Cut, Travelling-Salesman und Delta-TSP, Max-k-SAT, #DNF-SAT
• Parametrisierte Algorithmen. Grundlegende Methoden: Beschräenkte Suchbäume, Reduktion auf dem Problemkern, verebbare Grapheigenschaften, Color-coding.
• On-line Algorithmen: Das Paging Problem und das Arbeitsverteilungsproblem: deterministische und probabilistische Algoritmen.
Infos zur Vorlesung
Die erste Vorlesung findet am Dienstag, den 20.10.09 statt
Literatur
- Vorlesungsskript (wird in der Vorlesung ausgeteilt)
- T.H. Cormen, C.E. Leiserson, R.L. Rivest: Introduction to Algorithms. MIT Press, 1990.
- M.R. Garey, D.S. Johnson: Computers and Intractability - A Guide to the Theory of NP-Completeness. Freeman, 1979.
- A. Gibbons, W. Rytter: Efficient Parallel Algorithms. Cambridge University Press, 1988.
- M. Goemans: Lecture Notes on On-Line Algorithms. ftp://theory.lcs.mit.edu/pub/classes/18.415/notes-online.ps
- J. Hromkovic: Algorithmics for hard problems . Springer 2005.
- D. Kozen: The design and Annalysis of Algorithms. Springer, 1992.
- R. Motwani, P. Raghavan: Randomized Algorithms. Cambridge University Press, 1995.
- R. Niedermeier: Invitation to Fixed-Parameter Algorithms. Oxford University Press, 2006.
- C.H. Papadimitriou: Computational Complexity. Addison-Wesley, 1994.
- U. Schöning: Algorithmik. Spektrum Akademischer Verlag, 2001.
- A. Lenstra: Integer Factoring. Designs, Codes and Cryptography 19, 101-128 (2000).
Dozent
Vorlesungszeiten
Dienstag, 10:00-12:00 Uhr, O27/122,
Donnerstag, 10:00-12:00 Uhr, O27/122