Wintersemester 96 / 97

Seminar

Reduktionen und Klassifizierungen bei NP-vollständigen Problemen

Turingmaschinen, Zeit- und Speicherplatzkomplexität, effizient lösbare Probleme

• Datum: 15. 10. 96
• Vortragende: Renate Winter

NP-vollständige Probleme, Hypothese von Edmunds, Klassen P und NP

• 22. 10. 96
• R. Winter

NP-Vollständigkeit, Motivation, Definition, Sätze

• 29. 10. 96
• R. Winter

Deterministische und nichtdeterministische Turingprogramme, Satz von COOK

• 05. 11. 96
• R. Winter

Beweis des Satzes von COOK

• 12. 11. 96
• R. Winter

Reduktionsarten - Beweismethoden zur NP-Vollständigkeit, Klassifizierung von NPC-Problemen

• 19. 11. 96
• R. Winter

Fortsetzung der Reduktionsarten

• 26. 11. 96
• R. Winter

Die Berman-Hartmanis-Vermutung

• 03. 12. 96
• Vortragende: Heidrun Weise
• Literatur: SCHÖNING: Perlen der Theoretischen Informatik

Die Berman-Hartmanis-Vermutung und spärliche Mengen

• 10. 12. 96
• Vortragende: Heidrun Weise
• Literatur: SCHÖNING: Perlen der Theoretischen Informatik

Nachweis und Lösung einiger schwerer Optimierungsprobleme

• 17. 12. 96
• Vortragende: Katrin Bräunig
• Literatur: WEGENER: Theoretische Informatik

KP und TSP als Spezialfälle ganzzahliger LOP

• 07. 01. 97
• Vortragende: Katrin Bräunig
• Literatur: WEGENER: Theoretische Informatik

Reduktionen von ECKDOMINO und 3SAT auf CLIQUE

• 14. 01. 97
• Vortragende: Vera Hörhold
• Literatur: BÖRGER: Berechenbarkeit, Komplexität, Logik, WEGENER: Theoretische Informatik

Reduktionen von SSS auf CLIQUE

• 21. 01. 97
• Vortragende: Vera Hörhold
• Literatur: FLOYD, BEIGEL: The language of machines

Reduktionen von CLIQUE auf Multiprozessor Scheduling

• 28. 01. 97
• Vortragende: Kathrin Hinniger
• Literatur: PAPADIMITRIOU, STEIGLITZ: Combinatorial Optimization

Reduktionen von CLIQUE auf ECKDOMINO

• 04. 02. 97
• Vortragende: Kathrin Hinniger
• Literatur: SPECKER: Komplexität von Entscheidungsproblemen, BÖRGER: Berechenbarkeit, Komplexität, Logik

Vortragsbeendigung, Zusammenfassung

• 11. 02. 97