Komplexitätstheorie
Complexity Theory

Modul IN2007

Dieses Modul wird durch Fakultät für Informatik bereitgestellt.

Diese Modulbeschreibung enthält neben den eigentlichen Beschreibungen der Inhalte, Lernergebnisse, Lehr- und Lernmethoden und Prüfungsformen auch Verweise auf die aktuellen Lehrveranstaltungen und Termine für die Modulprüfung in den jeweiligen Abschnitten.

Basisdaten

IN2007 ist ein Semestermodul in Englisch auf Bachelor-Niveau und Master-Niveau das im Sommersemester angeboten wird.

Das Modul ist Bestandteil der folgenden Kataloge in den Studienangeboten der Physik.

  • Allgemeiner Katalog der nichtphysikalischen Wahlfächer
GesamtaufwandPräsenzveranstaltungenUmfang (ECTS)
240 h 90 h 8 CP

Inhalte, Lernergebnisse und Voraussetzungen

Inhalt

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.

Lernergebnisse

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.

Voraussetzungen

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

Lehrveranstaltungen, Lern- und Lehrmethoden und Literaturhinweise

Lehrveranstaltungen und Termine

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

Lern- und Lehrmethoden

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.

Medienformen

Folien, Tafelarbeit, Übungsblätter

Literatur

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.

Modulprüfung

Beschreibung der Prüfungs- und Studienleistungen

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.

Wiederholbarkeit

Eine Wiederholungsmöglichkeit wird am Semesterende angeboten.

Kondensierte Materie

Wenn Atome sich zusammen tun, wird es interessant: Grundlagenforschung an Festkörperelementen, Nanostrukturen und neuen Materialien mit überraschenden Eigenschaften treffen auf innovative Anwendungen.

Kern-, Teilchen-, Astrophysik

Ziel der Forschung ist das Verständnis unserer Welt auf subatomarem Niveau, von den Atomkernen im Zentrum der Atome bis hin zu den elementarsten Bausteinen unserer Welt.

Biophysik

Biologische Systeme, vom Protein bis hin zu lebenden Zellen und deren Verbänden, gehorchen physikalischen Prinzipien. Unser Forschungsbereich Biophysik ist deutschlandweit einer der größten Zusammenschlüsse in diesem Bereich.