[TZI]  [IAI]  [h-da]  [Faculty 3, Mathematics/Computer Science]  [University of Bremen] 

Vorlesungsfolien

Vorlesungsskript

Übungen

Klausurergebnisse SS-17

Vorlesung
Komplexitätstheorie

Dozent

Stefan Edelkamp

Termine

3.3.- 30.6.2017

Thema

In dieser Vorlesung wird ein algorithmischer Zugang zur Komplexitätstheorie gelegt und verschiedene Maschinenmodelle mit den Grenzen ihrer Berechnungskraft verglichen. Inhaltsverzeichnis (auf Basis Ingo Wegeners Büchern "Theoretische Komplexität", "Komplexitättheorie", "Highlights der Informatik", Uwe Schönings Buch "Theoretische Informatik - kurzgefasst", sowie dem KT-Skript von Marian Margraf)

Studienbrief 1: Einleitung und Landau'sche O-Notation

  • 1.1 Einleitung und Übersicht
  • 1.2 Beweisprinzipien und die reelen Zahlen
  • 1.3 O-Notation

Studienbrief 2: Turingmaschinen, churchsche These und Entscheidbarkeit

  • 2.1 Registermaschinen und deterministische Turingmaschinen
  • 2.2 Techniken zur Programmierung von Turingmaschinen
  • 2.3 Simulationen zwischen Turingmaschinen und Registermaschinen
  • 2.4 Universelle Turingmaschinen
  • 2.5 Die churchsche These
  • 2.6 Die Unentscheidbarkeit des Halteproblems
  • 2.7 Eigenschaften rekursiver und rekursiv aufzählbarer Sprachen
  • 2.8 Die Unentscheidbarkeit des postschen Korrespondenzproblems

Studienbrief 3: Die NP-Vollständigkeitstheorie

  • 3.1 Die Komplexitätsklasse P
  • 3.2 Nichtdeterministische Turingmaschinen und die Komplexitätsklasse NP
  • 3.3 NP-Vollständigkeit
  • 3.4 Die NP-Vollständigkeit wichtiger Probleme
  • 3.5 Pseudopolynomielle Algorithmen und starke NP-Vollständigkeit
  • 3.6 Turing-Reduzierbarkeit, NP-schwierige, NP-einfache und NP-äquivalente Probleme
  • 3.7 Eine Komplexitätstheorie für Approximationsprobleme
  • 3.8 Eine Komplexitätstheorie für probabilistische Algorithmen
  • 3.9 Die Struktur von NP und die polynomielle Hierarchie

Studienbrief 4: PCP Theorie

  • 4.1 Logische Charakterisierung von Sprachen
  • 4.2 Interaktive Beweise
  • 4.3 PCP Theorem
  • 4.4 Konsequenz für Approximationsalgorithmen

Komplexitätstheorie

Stefan Edelkamp (edelkamp@tzi.de)