Literatur

• Introduction to the Theory of Computation.
  Michael Sipser, PWS Publishing Company, 1997

  Ein sehr gutes Buch, anschaulich geschrieben, gibt intuitive Beweisideen und enthält viele Beispiele.

• Computational Complexity: A Modern Approach
  Sanjeev Arora, Boaz Barak Cambridge University Press, 2009.

• Automaten und Sprachen: Theoretische Informatik für die Praxis
  Andreas Müller, Springern Vieweg, 2024.
  

  Ein sehr ausfürlich geschriebenes Buch mit vielen Anwendungsbeispielen, sehr gut zu lesen.

• Computational Complexity
  Christos Papadimitriou, Addison-Wesley, 1994.

  Ein ebenfalls sehr empfehlenswertes Werk, das den Stoff der Vorlesung weit überdeckt.

• Introduction to Automata Theory, Languages and Computation
  John Hopcroft, Rajeev Motwani und Jeffrey Ullman, Addison-Wesley, 2000.

  Die Erstauflage dieses Klassikers erschien 1979 von Hopcroft und Ullman und war Grundlage der meisten Vorlesungen auf diesem Gebiet. Die neue Edition ist eine stark überarbeitete Fassung in Zusammenarbeit mit Motwani. Insbesondere wurden die Anwendungen stärker betont.

• On-line:
  Berechenbarkeit und Komplexität
  Berthold Vöcking, 2011.
  • The Status of the P verus NP Problem
    Ein Artikel von Lance Fortnow, erschienen in Communications of the ACM, 2009.

  • Lectures in Computational Complexity
    Jin-yi Cai, 2003.

• Theoretische Informatik, kurz gefasst.
  Uwe Schöning, Spektrum Akademischer Verlag, 2001.

  Hier finden Sie die Inhalt der Vorlesung kurz und kompakt, ohne viele Erklärungen. Das Buch eignet sich sehr gut als Ergänzung zur Vorlesung.

• Computers and Intractability- A Guide to the Theory of NP-Completeness.
  Michael Garey und David Johnson, W.H. Freeman and Company, 1979.

  Hier findet man im Anhang eine sehr nützliche Liste NP-vollständiger Probleme. Diese dient bis heute (das Buch ist von 1979) oft als Ausgangspunkt für Reduktionen auf weitere Probleme.

• Approximation Algorithms for NP-hard Problems
  Dorit Hochbaum (Ed.), PWS Publishing, 1995.

  Das Buch behandelt eine Vielzahl von Approximationsalgorithmen zu einer Vielxahl von Problemen.

• Introduction to Algorithms Thomas Corman, Charles Leiserson, Ronald Rivest,
  The MIT Press, 2001.

  Ein Algorithmen-Buch, das auch ein Kapitel über NP-Vollständigkeit und Approximations-Algorithmen enthät.

• Perlen der Theoretischen Informatik
  Uwe Schöning, BI Wissenschaftverlag, 1995.

• Automata and Computability
  Dexter Kozen, Springer.

• Theoretische Informatik. Eine algorithmenorientierte Einführung
  Ingo Wegener, Teubner Verlag, 1999.

• Kompendium Theoretische Informatik
  Ingo Wegener, Teubner Verlag, 2001.