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.

2023W, VU, 2.0h, 3.0EC, wird geblockt abgehalten
TUWEL

Merkmale

  • Semesterwochenstunden: 2.0
  • ECTS: 3.0
  • Typ: VU Vorlesung mit Übung
  • Format der Abhaltung: Präsenz

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 (inklusive Übungsbeispielen) wird vom Vortragenden präsentiert.

 

Prüfungsmodus

Schriftlich und Mündlich

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 Personen

Institut

LVA Termine

TagZeitDatumOrtBeschreibung
Di.11:00 - 13:0003.10.2023 - 19.12.2023Seminarraum FAV EG C (Seminarraum Gödel) Vorlesung
Do.16:00 - 18:0005.10.2023EI 8 Pötzl HS - QUER Eingangstest
Do.16:00 - 18:0012.10.2023EI 8 Pötzl HS - QUER Eingangstest (Ersatztermin)
Fr.13:30 - 15:0024.11.2023Seminarraum FAV EG B (Seminarraum von Neumann) Ersatztermin für Jänner
Mi.16:00 - 18:0029.11.2023Seminarraum 384 Ersatztermin für Jänner
Do.18:00 - 20:0011.01.2024Seminarraum FAV EG C (Seminarraum Gödel) Prüfungseinsicht und Präsentation der Mustlösungen
Mi.16:00 - 18:0006.03.2024Seminarraum FAV EG B (Seminarraum von Neumann) Prüfungseinsicht und Präsentation der Mustlösungen
Komplexitätstheorie - Einzeltermine
TagDatumZeitOrtBeschreibung
Di.03.10.202311:00 - 13:00Seminarraum FAV EG C (Seminarraum Gödel) Vorlesung
Do.05.10.202316:00 - 18:00EI 8 Pötzl HS - QUER Eingangstest
Di.10.10.202311:00 - 13:00Seminarraum FAV EG C (Seminarraum Gödel) Vorlesung
Do.12.10.202316:00 - 18:00EI 8 Pötzl HS - QUER Eingangstest (Ersatztermin)
Di.17.10.202311:00 - 13:00Seminarraum FAV EG C (Seminarraum Gödel) Vorlesung
Di.24.10.202311:00 - 13:00Seminarraum FAV EG C (Seminarraum Gödel) Vorlesung
Di.31.10.202311:00 - 13:00Seminarraum FAV EG C (Seminarraum Gödel) Vorlesung
Di.07.11.202311:00 - 13:00Seminarraum FAV EG C (Seminarraum Gödel) Vorlesung
Di.14.11.202311:00 - 13:00Seminarraum FAV EG C (Seminarraum Gödel) Vorlesung
Di.21.11.202311:00 - 13:00Seminarraum FAV EG C (Seminarraum Gödel) Vorlesung
Fr.24.11.202313:30 - 15:00Seminarraum FAV EG B (Seminarraum von Neumann) Ersatztermin für Jänner
Di.28.11.202311:00 - 13:00Seminarraum FAV EG C (Seminarraum Gödel) Vorlesung
Mi.29.11.202316:00 - 18:00Seminarraum 384 Ersatztermin für Jänner
Di.05.12.202311:00 - 13:00Seminarraum FAV EG C (Seminarraum Gödel) Vorlesung
Di.12.12.202311:00 - 13:00Seminarraum FAV EG C (Seminarraum Gödel) Vorlesung
Di.19.12.202311:00 - 13:00Seminarraum FAV EG C (Seminarraum Gödel) Vorlesung
Do.11.01.202418:00 - 20:00Seminarraum FAV EG C (Seminarraum Gödel) Prüfungseinsicht und Präsentation der Mustlösungen
Mi.06.03.202416:00 - 18:00Seminarraum FAV EG B (Seminarraum von Neumann) Prüfungseinsicht und Präsentation der Mustlösungen
LVA wird geblockt abgehalten

Leistungsnachweis

Die Beurteilung setzt sich aus 3 Teilen zusammen:

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

Prüfungen

TagZeitDatumOrtPrüfungsmodusAnmeldefristAnmeldungPrüfung
Di.10:00 - 12:0005.03.2024Seminarraum FAV EG C (Seminarraum Gödel) schriftlich27.01.2024 00:00 - 03.03.2024 23:59in TISSwritten exam

LVA-Anmeldung

Von Bis Abmeldung bis
18.09.2023 00:00 05.10.2023 00:00 23.10.2023 00:00

Curricula

StudienkennzahlVerbindlichkeitSemesterAnm.Bed.Info
066 011 DDP Computational Logic (Erasmus-Mundus) Keine Angabe
066 931 Logic and Computation Gebundenes Wahlfach
066 937 Software Engineering & Internet Computing Gebundenes Wahlfach
066 938 Technische Informatik Gebundenes Wahlfach
860 GW Gebundene Wahlfächer - Technische Mathematik Keine Angabe

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