Wintersemester 95/96

Dr. R. Winter


Seminar

NP-Vollständigkeit

Grund-und Hauptstudium Informatik

Gehaltene Vorträge:

  1. Deterministische und nichtdeterministische Turingmaschinen. P und NP
    Lit.: WEGENER: Theoretische Informatik

  2. NP-Vollständigkeit, Satz von COOK mit Beweis
    Lit.: WEGENER

  3. Nachweis der NP-Vollständigkeit von 3SAT und CLIQUE
    Lit.: WEGENER

  4. NP-Vollständigkeitsbeweise
    Lit.: WEGENER

  5. NP-Vollständigkeitsbeweise
    Lit.: PAPADIMITRIOU: Computational Complexity

  6. Linear äquivalente Probleme zu SAT
    Lit.: CREIGNOU: The class of problems that are linear equivalent to ...

  7. Linear äquivalente Probleme zu SAT
    Lit.: DEWDNEY: Linear Time Transformations ...

  8. Klassen QL und NQL
    Lit.: SCHNORR: Satisfiability is Qusilinear Complete in NQL

  9. SAT ist quasilinear vollständig in NQL
    Lit.: SCHNORR

  10. Pseudopolynomielle und Approximationsalgorithmen
    Lit.: WEGENER

  11. Probabilistische Algorithmen
    Lit.: WEGENER

  12. Varianten von linearen Optimierungsproblemen in P bzw. NP
    Lit.: HOPCROFT, ULLMAN: Einführung in die Automatentheorie ...

  13. Simplexalgorithmus
    Lit.: versch. Bücher zur Linearen Optimierung

  14. Polynomialzeitalgorithmus (Ellipsoid-Algorithmus) zur Lösung linearer Optimierungsprobleme
    Lit.:LOVASZ/HACIJAN

R. Winter