Wintersemester 94/95
Dr. R. Winter
Seminare
Komplexitätstheorie
Hauptstudium Informatik
Gehaltene Vorträge:
- Turingmaschinen mit 2-dimensionalem Speicher und ihre Zeitkomplexität
- NP-Vollständigkeitsbeweis von CLIQUE
- Das Knapsack-Problem
- PARTITION
- Bin Packing Problem
- Gerichteter HAMILTON-Kreis
- Travelling-Salesman Problem
- Das Knotenüberdeckungsproblem
- Problem der Ganzzahligen Linearen Optimierung
- Das Erbteilungsproblem
- SAT*
- MINIMUM EQUIVALENT CIRCUIT
- Die Klasse co-NP
- Approximationsalgorithmen
- Probabilistische Algorithmen
Literatur:
- GAREY/JOHNSON: Computers and Intractability
- BÖRGER: Berechenbarkeit, Komplexität, Logik
- HOPCROFT/ULLMAN: Einführung in die Automatentheorie, Formale Sprachen und Komplexitätstheorie
- WEGENER: Theoretische Informatik
R. Winter