Komplexitätstheorie und Effiziente Algorithmen
Wintersemester 2007/2008
|
| Veranstalter: | | Martin Sauerhoff / Ingo Wegener | |
|
| Termin: | | Montag | | 12:15-13:45 Uhr | | OH 14, E23
|
| | | Mittwoch | | 12:15-13:45 Uhr | | OH 14, E23
|
| Beginn: | | 15. Oktober 2007 | |
|
Die Vorlesung ist beendet.
Diese Vorlesung hat im Wintersemester den Schwerpunkt Komplexitätstheorie und im Sommersemester
den Schwerpunkt Effiziente Algorithmen. Ein Besuch beider Vorlesungen ist sinnvoll und für eine
Spezialisierung in diesen Bereichen sehr nützlich.
[Inhalt] [Begleitmaterial] [Übungen] [Übungsblätter] [Literatur und nützliche Links]
Die Vorlesung wird sich im Wesentlichen an folgendem Buch orientieren:
Ingo Wegener, "Komplexitätstheorie -- Grenzen der Effizienz von Algorithmen". Springer, 2003.
Geplant ist die Behandlung der Kapitel 7-12 und 14-16.
Vorlesungsfolien
Übungsgruppen:
| | Zeit: | Ort: | Veranstalter:
|
| Gruppe 1: | Mittwoch 16-18 | OH 14, Raum 304 | Marcel Marquardt
|
| Gruppe 2: | Freitag 12-14 | OH 16, Raum 205 | Marcel Marquardt
|
Übungsblätter
Nicht behandelt, nur ergänzend zum Stoff der Vorlesung.
Kapitel 8:
A compendium of NP optimization problems.
(Editoren: P. Crescenzi und V. Kann.)
Kapitel 10:
- J. L. Balcázar, J. Díaz, J. Gabarró, "Structural Complexity I", Springer 1995.
Kap.7: Beweis von Satz 10.2.1 aus der Vorlesung.
- Completeness in the polynomial-time hierarchy -- a compendium
(Marcus Schaefer und Christopher Umans, 2005).
- K. R. Reischuk, "Komplexitätstheorie", Teubner 1990.
(Dies ist die alte Version des in der Literaturliste am Anfang der Vorlesung genannten Buches.)
Abschnitt 6.4.4: Relativierte Ergebnisse zu P versus NP.
- "The 'P =? NP'-Poll" von Bill Gasarch, 2002.
(Vielleicht nicht direkt ein "nützlicher" Link im strengen Sinne, aber unterhaltsam auf jeden Fall.)
Kapitel 11:
- T.H.Cormen, C.H.Leiserson, R.L.Rivest, C.Stein, "Introduction to Algorithms", 2nd Edition, MIT Press, 2001.
Kap.11.3.3: Weitere Details zu universellem Hashing.
- O. Goldreich, "Zero-knowledge twenty years after its invention", 2004.
Tutorial mit mehr Details (teilweise technisch anspruchsvoll) zum Thema von Abschnitt 11.4.
- O. Goldreich, "Foundations of Cryptography (Fragments of a Book)", 1995.
Fragmentarische Vorversionen von einigen Kapiteln des gleichnamigen Buches (2 Bände, Cambridge University Press, 2004).
Kapitel 12:
- G. Ausiello, P. Crescenzi, G. Gambosi, V. Kann, A. Marchetti-Spaccamela, M. Protasi, "Complexity and Approximation", Springer-Verlag, 1999.
- E.W. Mayr, H.J. Prömel, A. Steger (Hrsg.), "Lectures on Proof Verification and Approximation Algorithms", LNCS 1367, Springer-Verlag, 1998.
-
S. Arora, "Probabilistic Checking of Proofs and Hardness of Approximation Problems", PhD Thesis, UC Berkeley, 1994.
Kostenlose Version des vollständigen Beweises des PCP-Theorems (im alten Stil).
- I.Dinur, "The PCP theorem by gap amplification", JACM 54(3):1-44, 2007.
Neue Version des vollständigen Beweises des PCP-Theorems (erste Version 2005).
Der Beweisverifizierer aus dem Beweis von Satz 12.2.2 in der Vorlesung ist auch als Teil dieses neuen Beweises hilfreich.
Kapitel 13:
Kapitel 15:
- J. Hromkovič, "Communication Complexity and Parallel Computing", Springer-Verlag, 1997.
- E. Kushilevitz, N. Nisan, "Communication Complexity", Cambridge University Press, 1997.
Kapitel 16:
- S. Jukna, "Extremal Combinatorics", Springer-Verlag, 2001.
("Extremal" bezieht sich hier auf die Eigenschaften der kombinatorischen Objekte, die untersucht werden -- nicht auf den Schwierigkeitsgrad!)
- I. Wegener, "Branching Programs and Binary Decision Diagrams", SIAM, 2000.
- I. Wegener, "Complexity of Boolean Functions", Teubner, 1987.
Kapitel 17:
M. Sauerhoff