Sommersemester 96

Dr. R. Winter


Seminar

Parallele Komplexitätsklassen

Hauptstudium Informatik

Zur Auswahl stehende Vortragsthemen:

  1. PRAM
    QUINN: Parallel Computing, S. 25-49

  2. Parallele Algorithmen und parallele Berechnungsmodelle
    PAPADIMITRIOU: Computational Complexity, S. 359-375

  3. Die Klasse NC. RNC - Algorithmen
    PAPADIMITRIOU: Computational Complexity, S. 375-385, teilw. 386-394

  4. Konvertierung von RNC - Algorithmen in NC - Algorithmen
    MOTWANI/NAOR, S. 8-13 bzw. LUBY, S. 162-173

  5. Zeitlich beschränkte PRAM's
    SAVITCH/STIMSON, S. 103-117

  6. Parallelarbeit bei NP-vollst�digen Problemen
    FERREIRA, S. 383-391

  7. Parallele Algorithmen für Clique, Graphfärbbarkeit, u. a.
    DAHLHAUS/KARPINSKI/NOVICK, S. 224-250

  8. Parallele Algorithmen fr das maximale Unabh�gigkeitsmengenproblem
    LUBY, S. 1036 bzw. BEAME/LUBY, S. 212-225

  9. Parallele Programme fr Maschinen mit verteiltem Speicher
    GOMM/ HECKNER/ LANGE/ RIEDLE, S. 381-391

  10. BRAM's als realistischeres PRAM-Modell
    NIEDERMEIER, 10 S.

Bemerkungen: Das Seminar kann in Form von Projekt- und Diplomarbeiten fortgesetzt werden (z.B. in Verbindung mit praktischer Implementierung von Parallel-Algorithmen).

R. Winter