Algorithmen II

Inhalt

• Einführung: Das Erfülbarkeitsproblem, 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.

Übungen

Blatt	Vorlesungsstoff	Material / Links	Korrektur
Blatt 1	Cover, SAT, Komplexitätsklassen
Blatt 2	Turing-Reduktion, Min-Cut 2-SAT
Blatt 3	APD-Algorithmus	Java Matrix Package
Blatt 4	APSP-Algorithmus	Lösungsvorschlag
Blatt 5	Matching
Blatt 6	Matching

Literatur

• 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
• D. Kozen: The design and Annalysis of Algorithms. Springer, 1992.
• N. Lynch: Distributed Algorithms. Morgan Kaufmann, 1996.
• R. Motwani, P. Raghavan: Randomized Algorithms. Cambridge University Press, 1995.
• R. Niedermeier: Parametrisierte Algorithmen Skript von der Universität Tübingen. www-fs.informatik.uni-tuebingen.de/lehre/ss99/paal.html
• 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).