Seminar

NP-Vollständigkeit

Grund-und Hauptstudium Informatik

Inhalt des Seminars:

Nach Einführung des Begriffs der NP-Vollständigkeit werden eine Reihe von Problemen untersucht, für die man bis heute keine in Polynomialzeit arbeitenden Algorithmen kennt. Zu ihrer Lösung betrachten wir:

pseudopolynomielle Algorithmen
Approximationsalgorithmen
probabilistische Algorithmen

Literatur:

WEGENER: Theoretische Informatik. Teubner Stuttgart 1993
PAPADIMITRIOU: Computational Complexity. Addison-Wesley 1994
AHO, HOPCROFT, ULLMAN: The Design and Analysis of Computer. Addison-Wesley 1974
Spezielle Artikel

Bemerkungen:

Es werden keine Voraussetzungen verlangt.
Der Seminarschein kann durch Halten eines Vortrages und Seminarmitarbeit erworben werden.
Das Seminar ist in Form von Projekt- und Diplomarbeiten fortsetzbar.

1. 4. 96 Einfhrung 15. 4. 96 Turingmaschinen, Klassen P und NP 22. 4. 96 NP-Vollständigkeit 29. 4. 96 SAT- und 3SAT-Problem
Zur Auswahl stehende Vorträge:
1. NP-Vollständigkeit von CLIQUE, Knapsack-Problem u.a. WEGENER:Theoretische Informatik, S. 52 ff 2. NP-Vollständigkeit von INDEPENDENT SET, VERTEX COVER und CLIQUE BRANDSTÄ:Graphen und Algorithmen, GAREY/JOHNSON:Computers and intractability 3. NP-Vollständigkeit graphentheoretischer Probleme PAPADIMITRIOU:Computational Complexity 4. Probabilistische Algorithmen WEGENER:Theoretische Informatik, S. 73ff, SCHÖING: S. 169-183 5. Die Berman-Hartmanis-Vermutung und spärliche Mengen SCHÖNING: S. 150-158 6./7. Isomorphie von NP-vollständigen Mengen BERMAN/HARTMANIS: S. 305-321 8. P = NP mit Wahrscheinlichkeit 1 SCHÖNING: S. 225-229 9. Kollabierende Hierarchien SCHÖNING: S. 159-168 10. Der BP-Operator und Graphenisomorphie SCHÖNING: S. 184-193 11. Der BP-Operator und die Mächtigkeit von Zählklassen SCHÖNING: S. 194-206 12. Polynomielle Reduktionen, Relativierungen und P = NP DOWNEY/GASARCH: S. 196-206 13. Approximationsalgorithmen fr das Clique-Problem STEWART: S. 117-132 (* 1. - 5. wurden gewählt)
R. Winter