Berechenbarkeit und Komplexität (WS2024/2025)

Alle wichtigen organisatorischen Informationen werden im ersten Vorlesungstermin vorgestellt.
Bitte meldet euch in RWTHonline für die Vorlesung an, damit ihr Zugriff auf den Moodle-Raum bekommt.
Wir laden die Vorlesungsmaterialien und wichtige Ankündigungen nur im Moodle-Raum hoch!

Inhalt

Grundlage der Vorlesung sind mathematische Modelle und Methoden. Der Bezug zu realistischen Computern und praktischen Problemen wird aber klar herausgearbeitet. Ein Highlight der Vorlesung ist die NP-Vollständigkeitstheorie, deren Auswirkung auf Theorie und Praxis wohl kaum überschätzt werden kann.

Literatur

  • J.E. Hopcroft, R. Motwani, J.D. Ullman: Introduction to Automata Theory, Languages, and Computation. Addison-Wesley 2001.
  • J. Hromkovic: Theoretische Informatik. Teubner 2004.
  • U. Schöning: Theoretische Informatik - kurzgefaßt. Spektrum Akademischer Verlag 2001.
  • M. Sipser: Introduction to the Theory of Computation. PWS Publishing 1997.
  • I. Wegener: Theoretische Informatik - eine algorithmenorientierte Einführung. Teubner Verlag 1999.
  • I. Wegener: Kompendium Theoretische Informatik - Eine Ideensammlung. Teubner 1996.