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

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

Merkmale

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

Lernergebnisse

Nach positiver Absolvierung der Lehrveranstaltung sind Studierende in der Lage

  • grundlegende Komplexitätsklassen und ihre Intuition zu erklären
  • Komplexitätsanalysen von Problemen (insbesondere in der polynomiellen Hierarchie)  durchzuführen...

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.

 

Methoden

Der Stoff wird vom Vortragenden präsentiert. Die Studierenden müssen dazu Übungsbeispiele lösen

Prüfungsmodus

Prüfungsimmanent

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

LVA Termine

TagZeitDatumOrtBeschreibung
Di.11:00 - 13:0008.10.2019 - 17.12.2019Seminarraum FAV EG C (Seminarraum Gödel) Vorlesung
Do.09:00 - 11:0010.10.2019 - 17.10.2019EI 5 Hochenegg HS Zulassungstest
Mo.11:00 - 13:0021.10.2019 - 16.12.2019Seminarraum FAV 01 B (Seminarraum 187/2) Vorlesung
Komplexitätstheorie - Einzeltermine
TagDatumZeitOrtBeschreibung
Di.08.10.201911:00 - 13:00Seminarraum FAV EG C (Seminarraum Gödel) Vorlesung
Do.10.10.201909:00 - 11:00EI 5 Hochenegg HS Zulassungstest
Di.15.10.201911:00 - 13:00Seminarraum FAV EG C (Seminarraum Gödel) Vorlesung
Do.17.10.201909:00 - 11:00EI 5 Hochenegg HS Zulassungstest
Mo.21.10.201911:00 - 13:00Seminarraum FAV 01 B (Seminarraum 187/2) Vorlesung
Di.22.10.201911:00 - 13:00Seminarraum FAV EG C (Seminarraum Gödel) Vorlesung
Mo.04.11.201911:00 - 13:00Seminarraum FAV 01 B (Seminarraum 187/2) Vorlesung
Di.05.11.201911:00 - 13:00Seminarraum FAV EG C (Seminarraum Gödel) Vorlesung
Mo.18.11.201911:00 - 13:00Seminarraum FAV 01 B (Seminarraum 187/2) Vorlesung
Di.19.11.201911:00 - 13:00Seminarraum FAV EG C (Seminarraum Gödel) Vorlesung
Mo.25.11.201911:00 - 13:00Seminarraum FAV 01 B (Seminarraum 187/2) Vorlesung
Di.26.11.201911:00 - 13:00Seminarraum FAV EG C (Seminarraum Gödel) Vorlesung
Mo.02.12.201911:00 - 13:00Seminarraum FAV 01 B (Seminarraum 187/2) Vorlesung
Di.03.12.201911:00 - 13:00Seminarraum FAV EG C (Seminarraum Gödel) Vorlesung
Mo.09.12.201911:00 - 13:00Seminarraum FAV 01 B (Seminarraum 187/2) Vorlesung
Di.10.12.201911:00 - 13:00Seminarraum FAV EG C (Seminarraum Gödel) Vorlesung
Mo.16.12.201911:00 - 13:00Seminarraum FAV 01 B (Seminarraum 187/2) Vorlesung
Di.17.12.201911:00 - 13:00Seminarraum FAV EG C (Seminarraum Gödel) Vorlesung
LVA wird geblockt abgehalten

Leistungsnachweis

Die Beurteilung setzt sich aus 3 Teilen zusammen:

  • EIngangstest
  • Übungsbeispiele
  • schriftliche und/oder Prüfung am Ende (Details werden in der Vorbesprechung fixiert)

LVA-Anmeldung

Von Bis Abmeldung bis
01.09.2019 00:00 06.10.2019 23:55 20.10.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