Note: This is an archvied version of our old webpage. Some links might be broken. The current one can be found here.
I7 Logo
Chair for Foundations of Software Reliability and Theoretical Computer Science
Informatik Logo TUM Logo
Home
 Contact
 Teaching
lectures
exercises
seminars
proseminars
research seminars
practical courses
WS 2020/21
SS 2020
WS 2019/20
SS 2019
WS 2018/19
SS 2018
WS 2017/18
SS 2017
WS 2016/17
SS 2016
WS 2015/2016
SS 2015
WS 2014/2015
SS 2014
WS 2013/2014
SS 2013
WS 2012/2013
SS 2012
WS 2011/2012
SS 2011
WS 2010/2011
SS 2010
WS 2009/2010
SS 2009
WS 2008/2009
SS 2008
WS 2007/2008
SS 2007
WS 2006/2007
SS 2006
WS 2005/2006
SS 2005
WS 2004/2005
SS 2004
Before 2004
 People
Publications
 Student Projects
Research
Tools
Heroes of Computer Science
 Help

































Courses

Komplexitätstheorie
held by: Univ.-Prof. Dr. Helmut Veith †
Dr. Christian Schallhart
held in: WS 2007/2008
schedule: Wednesday, 10:15 - 12:00 (MI HS 2)
    start date: 2007-10-31 / end date: 2008-02-09

Thursday, 12:00 - 15:15 (MI HS 2)
    start date: 2007-10-25 / end date: 2008-02-09
sws: 4
ects: 8
Die nächsten Termine der geblockt abgehaltenen Vorlesung sind:
  • 8. Dezember 2007
  • 12. Januar 2008
  • 25. oder 26. Januar 2008: Der genau Tag wird noch geklärt.
Die Vorlesung beginnt an diesen Samstagen jeweils um 10:00 Uhr und findet im HS2 statt.

Tragen Sie sich bitte bei Interesse an der Vorlesung mittels des Webformulars in die Mailingliste zur Lehrveranstaltung ein. Wir können Ihnen dann Ankündigungen, Organisatorisches, etc. direkt mitteilen.

4 SWS Vorlesung im Bereich Informatik III (Theoretische Informatik) Wahlpflichtvorlesung im Gebiet syntaktische und operationelle Beschreibungen

Informationen und Aufgabenblätter zur Übung finden Sie hier: Übung zur Vorlesung Komplexitätstheorie

Literatur
  1. J. L. Balcázar, J. Díaz, and J. Gabarró. Structural Complexity I, volume 11 of EATCS Monographs on Theoretical Computer Science. Springer, 1988.
  2. J. L. Balcázar, J. Díaz, and J. Gabarró. Structural Complexity II, volume 22 of EATCS Monographs on Theoretical Computer Science. Springer, 1990.
  3. J. E. Hopcroft and J. D. Ullman. Formal Languages and Their Relation to Automata. Addison-Wesley, 1968.
  4. J. E. Hopcroft and J. D. Ullman. Introduction to Automata Theory, Languages and Computation. Addison-Wesley, 1979.
  5. C. H. Papadimitriou. Computational Complexity. Addison-Wesley, 1994.
  6. M. R. Garey and D. S. Johnson. Computers and Intractability (A Guide to the Theory of NP-Completeness). Freeman, San Francisco, 1979.
  7. K. R. Reischuk. Einführung in die Komplexitätstheorie. Teubner, 1990

Weiterführende Literatur:
  1. L. A. Hemaspaandra and M. Ogihara. The Complexity Theory Companion. EATCS Monographs in Theoretical Computer Science. Springer, 2002.
  2. K. Wagner and G. Wechsung. Computational Complexity. Mathematics and its applications (East Europeans series). VEB Deutscher Verlag der Wissenschaften, Berlin, 1986.
downloadable material:
slides
title / description download
Turing Maschinen
 click here...
Strukturelle Komplexitätstheorie
 click here...
PSPACE-vollständige Probleme
 click here...
Optimierungsprobleme, Approximation, Approximations-Klassen und deren Beziehungen
 click here...