Sommersemester 95

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
    Lit.: WEGENER

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

  4. NP-Vollständigkeitsbeweise
    Lit.: AHO/HOPCROFT/ULLMAN

  5. NP-Vollständigkeitsbeweise
    Lit.: PAPADIMITRIOU

  6. Pseudopolynomielle und Approximationsalgorithmen
    Lit.: WEGENER

  7. Probabilistische Algorithmen
    Lit.: WEGENER

  8. Effizienz von Algorithmen
    Lit.: LEWIS/PAPADIMITRIOU

  9. Parallele Programme und PRAM's
    Lit.: EITAN/GURARI

  10. Schaltkreisfamilien
    Lit.: EITAN/GURARI

  11. BRAM - praxixnahe Variante der PRAM
    Lit.: NIEDERMEIER/ROSSMANITH

R. Winter