Komplexitätstheorie

Sommersemester 2012

Vorlesung: Prof. Dr. Ludwig Staiger

Übungen: Dipl.-Ing. Marian Kogler

Vorlesung:

Kapitel 5 (Zusatz), 6, 7

Kapitel 5 (Zusatz), 6, 7 (verkleinert)

Literatur zur Vorlesung:

G. Wechsung: Vorlesungen zur Komplexitätstheorie. Teubner, Stuttgart 2000.

K.R.Reischuk: Komplexitätstheorie. Teubner, Stuttgart 1999.

D.P.Bovet, P.Crescenzi: Introduction to the theory of complexity. Prentice Hall, New York, 1994.

K.Wagner, G.Wechsung: Computational Complexity. Deutscher Verlag der Wissenschaften, Berlin 1986.

I. Wegener: Komplexitätstheorie. Springer, Berlin 2003.

J.L.Balcazar, J.Diaz, J.Gabarro: Structural Complexity I. Springer-Verlag, Berlin 1988.

M.R.Garey, D.S.Johnson: Computers and Intractability. A Guide to the Theory of NP-Completeness. Freeman, San Francisco 1979.

J.E.Hopcroft, J.D.Ullman: Einführung in die Automatentheorie, formale Sprachen und Komplexitätstheorie. Oldenbourg 2000.

J.E.Hopcroft, J.D.Ullman: Introduction to Automata Theory, Languages and Computation. Addison-Wesley, seit 1979.

J.E.Hopcroft, R. Motwani, J.D.Ullman: Einführung in die Automatentheorie, formale Sprachen und Komplexitätstheorie. Pearson Studium 2006. (auch in engl.)