Komplexitätstheorie

LECTURE WILL BE HELD IN GERMAN

Im Zentrum der Vorlesungen über Komplexitätstheorie stehen die Frage nach den Grenzen der Berechenbarkeit und die Klassifizierung von Problemen bezüglich ihrer algorithmischen Komplexität. Als Maße für Komplexität werden insbesondere Laufzeit und Speicherbedarf, aber auch z. B. Parallelisierbarkeit herangezogen. Es beinhaltet den Nachweis sowohl der Nichtentscheidbarkeit z. B. der Arithmetik als auch die Untersuchung der Problem-inhärenten Komplexität, d.h. den Beweis unterer Komplexitätsschranken und den Komplexitätsvergleich von Problemen. Es werden unter anderem folgende Themen behandelt: Eine untere Schranke für 1-Band-Turingmaschinen, Vergleiche zwischen Komplexitätsklassen, PSPACE-Vollständigkeit und Nichtentscheidbarkeit.

Dozenten

  • Vorlesung: Friedhelm Meyer auf der Heide
  • Übungen: Simon Pukrop

Termine

  • Vorlesung: Montags, 15:15 - 17:30, F0.530
  • Übungsgruppe 1: Dienstags, 16:00 - 17:30, F2.211
  • Übungsgruppe 2: Freitags, 14:15 - 15:45, F1.110

Die Anmeldung zur Vorlesung erfolgt über Paul. Die Vorlesung beginnt am 7. Oktober, die Übungen beginnen ebenfalls in der ersten Semesterwoche!

Übungen

Es wird wöchentlich Mittwochs ein Übungsblatt mit Aufgaben auf Panda herausgegeben, das von Ihnen zu bearbeiten ist. Die Lösung ist bis Montag (11 Tage nach Ausgabe) um 10:00 Uhr abzugeben. Die Abgabe muss in elektronischer Form über Panda geschehen. Es werden nur Lösungen im PDF Format akzeptiert! Des Weiteren ist Gruppenabgabe (in der Regel bis zu 3 Personen) erlaubt.

Fragen zu den Übungsblättern bitte an Simon Pukrop.

Bonuspunkte und Prüfung

Im Anschluss an die Vorlesung erfolgt eine mündliche Prüfung über den Stoff dieser Veranstaltung. Voraussetzung für die Teilnahme an der Prüfung sind das Erreichen von mindestens 40% der Punkte der Hausaufgaben.

Wenn Sie aktiv in den Übungen mitarbeiten, können Sie Ihre Note wie folgt verbessern (Bonus):

  • Erreichen Sie mindestens 50% der Punkte der Hausaufgaben, so verbessert sich die Note um 1/3 Notenpunkt.
  • Erreichen Sie mindestens 75% der Punkte der Hausaufgaben, so verbessert sich die Note um 2/3 Notenpunkt.

Eine Verbesserung der Note 5 ("nicht bestanden") ist nicht möglich. Als Bonusleistung zählen die Hausaufgaben von dieser Veranstaltung. Voraussetzung für einen Bonus ist aktive Mitarbeit in den Übungen, insbesondere Vorrechenen eigener Lösungen.

Bonuspunkte aus früheren Vorlesungen können nicht angerechnet werden.

Vorraussichtliche Prüfungszeiträume

Es wird zwei Prüfungszeiträume geben:

  • 10.02.-12.02.2020
  • 23.03.-25.03.2020

Wir behalten uns vor die Prüfungszeiträume zu ändern.

Vorlesungsmaterial, Übungsblätter & Literatur

Material wird auf der zugehörigen Panda-Seite veröffentlicht