News | Content | Logbuch | Dates | Exercises | Prüfungen bzw. Scheine | Literature | Links  

Komplexitätstheorie

Lecture in Summer 2011

Gehalten von Prof. Dr. Nicole Schweikardt
Betreuung der Übungen durch M.Sc. Frederik Harwath

News

Im Logbuch finden Sie nach den Vorlesungen Informationen zum Inhalt der einzelnen Vorlesungsstunden und gelegentlich ergänzende Bemerkungen.

Introduction

Eine Beschränkung wichtiger Ressourcen wie Laufzeit und Speicherplatz auf realistische Dimensionen führt zu einer drastischen Einschränkung der Klasse lösbarer Probleme. Um dieses Phänomen zu studieren, wird, bei fixierten Ressourcen, die Komplexitätsklasse aller Probleme eingeführt, die innerhalb dieser Ressourcen lösbar sind. Wichtige Komplexitätsklassen wie Logspace, NC, P, NP und PSPACE werden eingeführt und ihre Eigenschaften werden untersucht. In der Veranstaltung wird sodann eine Auswahl der folgenden Themengebiete behandelt: Lernziele: Neben dem Verständnis der durch Ressourcenschranken bedingten Grenzen der algorithmischen Lösbarkeit ist die Fähigkeit, die Komplexität spezieller Probleme einzuschätzen und ein fundiertes Gefühl für das Machbare zu entwickeln, das wesentliche Ziel der Veranstaltung.

Kürzel laut Studienordnung: M-KTH.  Creditpoints: 8.  SWS: 3V, 2Ü.

Content

Die Vorlesung wird voraussichtlich in folgende Kapitel gegliedert sein; die Inhalte orientieren sich jeweils an den entsprechenden Kapiteln des Buchs [AB] .

Logbuch

Hier finden Sie (nach den Vorlesungen) Informationen zum Inhalt der einzelnen Vorlesungsstunden, die in der Vorlesung verwendeten Folien und gelegentlich ergänzende Bemerkungen.

Dates

ZeitOrtLeitung
Lecture Dienstags 14:15-17:00 (Pausen: 15:00-15:05 und 15:50-16:05) Magnus-Hörsaal in der Informatik, Robert-Mayer-Str. 11-15 Prof. Dr. Nicole Schweikardt
Exercise 1 Donnerstags 14:15-16:00 Raum 117, Robert-Mayer-Str. 11-15 M.Sc. Frederik Harwath

Exercises

Prüfungen bzw. Scheine

Vorsicht:

In der Vorlesung und der Übung werden viele wichtige Dinge (insbesondere Beweise, aber auch einiges andere) an der Tafel erklärt. Diese Dinge sind für die Veranstaltung "Komplexitätstheorie" wesentlich und daher auch dann prüfungsrelevant, wenn sie nicht in den hier erhältlichen pdf-Dateien enthalten sind.
Zur Vorbereitung auf eine Prüfung (Modulabschlussprüfung oder Diplom-Prüfung) ist es unbedingt notwendig, das gesamte in den Vorlesungs- und Übungsstunden (mit Folien oder an der Tafel) vermittelte Material durchzuarbeiten.

Modulabschlussprüfung (relevant für Studierende in einem Bachelor- oder Master-Studiengang):

Die Modulabschlussprüfung wird durch eine mündliche Prüfung abgelegt.
Termine für mündliche Modulabschlussprüfungen können nach Vereinbarung bei Frau Nadland angefragt werden. Generelle Informationen zur Anmeldung zu mündlichen Prüfungen finden hier.

Im Lauf des Semesters können Bonuspunkte erworben werden, durch deren Einbringen die Note einer bestandenen Modulabschlussprüfung um eine Teilnote verbessert werden kann (also von 4,0 auf 3,7; von 3,7 auf 3,3; von 3,3 auf 3,0; von 3.0 auf 2,7; von 2,7 auf 2,3; von 2,3 auf 2,0; von 2,0 auf 1,7; von 1,7 auf 1,3; von 1,3 auf 1,0).

In der letzten Übungsstunde vor Pfingsten (d.h. am 09.06.2011) und in der letzten Übungsstunde des Semesters (d.h. am 14.07.2011) wird je ein 90-minütiger Test geschrieben.
Voraussetzung für den Erwerb von Bonuspunkten, durch deren Einbringen die Note einer bestandenen Modulabschlussprüfung um eine Teilnote verbessert werden kann, sind:

  1. Bestehen der beiden Tests und
  2. Erreichen von mindestens 50 Prozent aller Übungspunkte (bitte beachten Sie, dass dies insbes. die regelmäßige und aktive Teilnahme an den Übungsstunden erfordert, siehe unten).

Scheinerwerb (relevant für Studierende in einem Diplom- oder Lehramts-Studiengang):

In der letzten Übungsstunde vor Pfingsten (d.h. am 09.06.2011) und in der letzten Übungsstunde des Semesters (d.h. am 14.07.2011) wird je ein 90-minütiger Test geschrieben.
Voraussetzung für den Scheinerwerb sind:
  1. Bestehen der beiden Tests und
  2. Erreichen von mindestens 50 Prozent aller Übungspunkte (bitte beachten Sie, dass dies insbes. die regelmäßige und aktive Teilnahme an den Übungsstunden erfordert, siehe unten).

Verbindliche "Spielregeln" zum Erwerb von Übungspunkten:

Übungsblätter werden dienstags nach der Vorlesung ausgeteilt. Am Donnerstag der darauf folgenden Woche wird das jeweilige Übungsblatt in der Übungsstunde besprochen. Zu Beginn dieser Übungsstunde können alle Teilnehmer in eine Liste eintragen, für welche Aufgaben(teile) sie wie viele Übungspunkte angerechnet bekommen wollen. Während der Übungsstunde werden vom Übungsleiter aus dieser Liste willkürlich einzelne Teilnehmer zum Vorrechnen von Aufgaben(teilen) ausgesucht. Falls sich beim Vorrechnen herausstellen sollte, dass ein Teilnehmer keine sinnvolle Lösung vorweisen kann, obwohl er in der Liste Übungspunkte für diese Aufgabe beansprucht hat, geschieht folgendes:
  1. Tritt diese Situation für den jeweiligen Teilnehmer zum ersten Mal in diesem Semester auf, so werden ihm für das gesamte gerade behandelte Übungsblatt keine Übungspunkte angerechnet.
  2. Tritt diese Situation für den jeweiligen Teilnehmer zum zweiten Mal in diesem Semester auf, so kann er in der Veranstaltung "Komplexitätstheorie" im SoSe 2011 keine Übungspunkte erwerben.

Literature

[AB] Sanjeev Arora and Boaz Barak. Computational Complexity. A Modern Approach. Cambridge University Press, 2009.
[G] Oded Goldreich. Computational Complexity. A Conceptual Perspective. Cambridge University Press, 2008.
[P] Christos H. Papadimitriou. Computational Complexity. Addison-Wesley, 1995.
[W] Ingo Wegener. Komplexitätstheorie. Grenzen der Effizienz von Algorithmen. Springer-Verlag, 2003.
[AB] Jörg Flum and Martin Grohe. Parameterized Complexity Theory. Springer-Verlag, 2006.
[HU] J. E. Hopcroft and J.D. Ullman. Introduction to Automata Theory, Languages, and Computation. Addison-Wesley, 1979.
[S] Jacques Sakarovitch. Elements of Automata Theory. Cambridge University Press, 2009.
[K] Dexter Kozen. Theory of Computation. Springer-Verlag, 2006.
[V] Heribert Vollmer. Introduction to Circuit Complexity. Springer-Verlag, 1999.

Links

[LF-Blog] Lance Fortnow's Computational Complexity Blog
[RJL-Blog] Richard J. Lipton's Theory of Computation Blog
[CCC] IEEE Conference on Computational Complexity (CCC)