Prof. Dr. Rainer Schrader

Vorlesung       Komplexitätstheorie                         
                4 St. Di 10-12, Mi 9-11                     
                Hörsaal Pohligstraße 1, 3. Stock            



Übungen¦        zur Vorlesung Komplexitätstheorie           
                (mit K. Wolf)                               
                2 St. nach Vereinbarung                     



Oberseminar     über ausgewählte Themen der Informatik      
                (mit A. Bachem, M. Jünger, E.               
                Speckenmeyer)                               
                2 St. nach Ankündigung                      



Kolloquium      über Informatik (publice)                   
                (mit A. Bachem, M. Jünger, E.               
                Speckenmeyer)                               
                2 St. nach Ankündigung                      

Die Vorlesung wendet sich an Studierende der Wirtschaftsinformatik, der Mathematik und der Naturwissenschaften, die die Grundvorlesungen über Informatik bereits abgeschlossen haben.

Folgende Themen werden behandelt:

• Turingmaschinen, Entscheidbarkeit und Berechenbarkeit
• Komplexitätsklassen, Reduktionen und Vollständigkeit
• Probabilistische Turingmaschinen, randomisierte Algorithmen
• und Komplexitätsklassen
• Interaktive Beweissysteme
• Beweisverifikation und Konsequenzen für Approximierbarkeit von
• Optimierungsproblemen
• Parallele Rechnerkonzepte

Übungen dienen zur Vertiefung des Vorlesungsstoffes.

Literaturhinweise: M.R. Garey und D.S. Johnson

Computers and Intractabilitiy: A Guide to the Theory of NP- Completeness. (W.H. Freeman and Company, 1979)

• D.P. Bovet und P. Crescenzi,Introduction to the Theory of Complexity.(Prentice Hall, 1993)
• C.H. Papadimitriou, Computational Complexity.(Addison Wesley, 1994)

Im Oberseminar und im Kolloquium berichten Mitarbeiter und Gäste über aktuelle Forschungsergebnisse.