Vorlesung (WS 2006/07): Algorithmen II

Vorlesungszeiten und Ankündigung

• Vorlesung: Prof. Jacobo Torán, Dienstag 10-12 Uhr in H21

                                                           Donnerstag 14-16 Uhr in H21

• Übung: Henning Wunderlich , Freitag, 1230-1400 Uhr in H21

Einordnung in das Curriculum

• Kernfach M  (Theoretische und Mathematische Methoden der Informatik)
• Kernfach P (Praktische und Angewandte Informatik)
• Vertiefungsgebiet Theoretische Informatik

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

• Übung 1 (Besprechung 27.10.06)
• Übung 2 (Besprechung 03.11.06)
• Übung 3 (Korrigierte Fassung (-1), Besprechung 10.11.06)
• Übung 4 (Besprechung 17.11.06)
• Übung 5 (Besprechung 24.11.06)
• Übung 6 (Besprechung 01.12.06)
• Übung 7 (Besprechung 08.12.06)
• Übung 8 (Besprechung 15.12.06)
• Übung 9 (Besprechung Donnerstag! 21.12.06)
• Übung 10 (Besprechung 12.01.07)
• Übung 11 (Besprechung 19.01.07)
• Übung 12 (Besprechung 26.01.07)
• Übung 13 (Besprechung 02.02.07)
• Übung 14 (Korrigierte Fassung (max), Besprechung 09.02.07)

Folien

• Einführung
• Kürzeste Wege zwischen allen Knotenpaaren
• Isolierung von Zeugen beim BMPW

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. http://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).