181.142 Komplexitätstheorie Abgesagt
Diese Lehrveranstaltung ist in allen zugeordneten Curricula Teil der STEOP.
Diese Lehrveranstaltung ist in mindestens einem zugeordneten Curriculum Teil der STEOP.

2019S, VU, 2.0h, 3.0EC, wird geblockt abgehalten

Merkmale

  • Semesterwochenstunden: 2.0
  • ECTS: 3.0
  • Typ: VU Vorlesung mit Übung

Ziele der Lehrveranstaltung

Einführung in die Komplexitätstheorie: Verständnis der grundlegenden Begriffe, Konzepte, Methoden und Resultate.

Inhalt der Lehrveranstaltung

Grundlegende Begriffe der Komplexitätstheorie, deterministische und nicht-deterministische Komplexitätsklassen, NP-vollständige Probleme, logarithmischer Speicherbedarf, die Polynomielle Hierarchie, exponentiell schwierige Probleme, Anwendungen.

 

Weitere Informationen

Aufwandsabschätzung

  2 h Eingangstest
30 h Vorlesung (12 Termine inclusive Vorbereitung)
40 h Prüfungsvorbereitung
 3 h schriftliche + mündliche Prüfung
-----------------------------------------------------------
 75 h = 3 Ects

Vortragende

Institut

Leistungsnachweis

Eingangstest,
schriftliche Prüfung,
mündliche Prüfung

LVA-Anmeldung

Von Bis Abmeldung bis
11.02.2019 00:00 05.03.2019 23:55 19.03.2019 23:55

Curricula

Literatur

C. Papadimitriou. "Computational Complexity". Addison-Wesley, 1994. M. R. Garey and D. S. Johnson. "Computers and Intractability". Freeman, 1979.

Vorkenntnisse

  • Grundkenntnisse in mathematischer Logik und Grundkenntnisse in Komplexitätstheorie (entsprechend der Vorlesung "Formale Methoden der Informatik") werden vorausgesetzt.
  • Die TeilnehmerInnen müssen grundlegende mathematische Fertigkeiten (wie das Ausführen von Induktionsbeweisen) entsprechend den Mathematik-LVAs im Bachelor Studium mitbringen.

Weitere Informationen

Sprache

Englisch