Complexity Theory

Module IN2007

This Module is offered by TUM Department of Informatics.

This module handbook serves to describe contents, learning outcome, methods and examination type as well as linking to current dates for courses and module examination in the respective sections.

Basic Information

IN2007 is a semester module in English language at Bachelor’s level und Master’s level which is offered in summer semester.

This Module is included in the following catalogues within the study programs in physics.

  • Catalogue of non-physics elective courses
Total workloadContact hoursCredits (ECTS)
240 h 90 h 8 CP

Content, Learning Outcome and Preconditions

Content

Das Modul behandelt zunächst gründlich Turing-Maschinen. Zeit- und Platzkomplexität werden studiert. Ferner werden Schaltkreise als Berechnungsmodell untersucht. Die Komplexitätsklassen L, NL, P, NP, PSPACE, EXP, NEXP, PH werden eingeführt. Anschließend werden Vollständigkeit und fundamentale strukturelle Zusammenhänge zwischen Komplexitätsklassen hergeleitet. Weiterhin behandelt das Modul das Konzept der Alternierung, Boolesche Schaltkreise, Randomisierung und Interaktive Beweissysteme.

Learning Outcome

Die Teilnehmer des Moduls kennen die zentralen Methoden der Komplexitätstheorie. Sie wissen um Berechnungsmodelle, Komplexitätsklassen, Reduktionen, Vollständigkeit und kennen ausführlich weiterführende Konzepte wie Diagonalisierung, die Polynomialhierarchie, Platzkomplexität, Alternierung, Boolesche Schaltkreise, Randomisierung und Interaktive Beweissysteme.

Preconditions

IN0011 Einführung in die Theoretische Informatik, IN0015 Diskrete Strukturen, IN0007 Grundlagen: Algorithmen und Datenstrukturen

Courses, Learning and Teaching Methods and Literature

Courses and Schedule

ArtSWSTitelDozent(en)Termine
VU 6 Complexity Theory (IN2007) Montag, 10:00–12:00
Dienstag, 14:00–16:00
Mittwoch, 08:00–10:00

Learning and Teaching Methods

Das Modul besteht aus einer Vorlesung und einer begleitenden Übungsveranstaltung. Die Inhalte der Vorlesung werden im Vortrag und durch Präsentation vermittelt. Studierende werden insbesondere durch die Lösung von Übungsblättern zur inhaltlichen Auseinandersetzung mit den Themen angeregt. Die Lösung der Übungsaufgaben wird in der Übungsveranstaltung besprochen. Zusätzlich erhalten die Studenten durch die Korrektur der Übungsblätter eine individuelle Rückmeldung über ihren Lernerfolg.

Media

Folien, Tafelarbeit, Übungsblätter

Literature

Sanjeev Arora, Boaz Barak: Computational Complexity - A Modern Approach. Cambridge University Press: Cambridge-New York-Melbourne, 2009. Giorgio Ausiello, Pierluigi Creszenzi, Giorgio Gambosi, Viggo Kann, Alberto Marchetti-Spaccamela, Marco Protasi: Complexity and approximation - Combinatorial optimization problems and their approximability properties. Springer-Verlag: Berlin-Heidelberg, 1999. Jose L. Balcazar, Josep Diaz, Joaquim Gabarro: Structural Complexity I (and II). EATCS Monographs on Theoretical Computer Science, Springer-Verlag: Berlin-Heidelberg, 1995. Christos H. Papadimitriou: Computational Complexity. Addison-Wesley Publishing Company: London-Amsterdam-New York, 1994. Christos H. Papadimitriou, Kenneth Steiglitz: Combinatorial optimization: Algorithms and complexity. Prentice-Hall, Englewood Clis, NJ, 1982. Karl Rudiger Reischuk: Komplexitätstheorie - Band I: Grundlagen. B.G. Teubner: Stuttgart-Leipzig, 1999. Michael Sipser: Introduction to the Theory of Computation. International Edition, Thomson Course Technology: Australia-Canada-Mexico-Singapore-Spain-United Kingdom-United States, 2006. Ingo Wegener: The complexity of Boolean functions. Wiley-Teubner Series in Computer Science: Stuttgart-Chichester-New York, 1987.

Module Exam

Description of exams and course work

Die Prüfungsleistung wird in Form einer Klausur erbracht. In dieser weisen Studierende anhand der gestellten Aufgaben nach, dass sie über fundamentale und weiterführende Kenntnisse im Bereich der Komplexitätstheorie verfügen. Die Studierenden weisen nach, dass sie in begrenzter Zeit komplexitätstheoretische Probleme erkennen und analysieren können sowie Wege zu einer effizienten Lösung finden.

Exam Repetition

There is a possibility to take the exam at the end of the semester.

Current exam dates

Currently TUMonline lists the following exam dates. In addition to the general information above please refer to the current information given during the course.

Title
TimeLocationInfoRegistration
Komplexitätstheorie
Do, 20.10.2016 bis 19.9.2016 (Abmeldung bis 13.10.2016)

Condensed Matter

When atoms interact things can get interesting. Fundamental research on the underlying properties of materials and nanostructures and exploration of the potential they provide for applications.

Nuclei, Particles, Astrophysics

A journey of discovery to understanding our world at the subatomic scale, from the nuclei inside atoms down to the most elementary building blocks of matter. Are you ready for the adventure?

Biophysics

Biological systems, from proteins to living cells and organisms, obey physical principles. Our research groups in biophysics shape one of Germany's largest scientific clusters in this area.