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).

Vorlesungszeiten

Dienstag, 10:00-12:00 Uhr, O27/122,
Donnerstag, 10:00-12:00 Uhr, O27/122

Übungsleiter

Weitere Informationen

LSF-Eintrag

Die erste Vorlesung findet am  20.10. statt.

Höhere Algorithmik

Vorlesungszeiten

Dienstag, 10:00-12:00 Uhr, O27/122,
Donnerstag, 10:00-12:00 Uhr, O27/122

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.

Übungsleiter

Infos zur Vorlesung

Die erste Vorlesung findet am Dienstag, den 20.10.09 statt

Weitere Informationen

LSF-Eintrag

Die erste Vorlesung findet am  20.10. 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).