TU Wien:Komplexitätstheorie VU (Pichler)

Aus VoWi
Wechseln zu: Navigation, Suche

Daten[Bearbeiten]

Inhalt[Bearbeiten]

Laut Webseite der Lehrveranstaltung:

  • Logarithmic Space
  • Boolean Logic, proof of the Cook-Levin Theorem
  • More NP-Completeness
  • The polynomial hierarchy
  • The class PSPACE
  • Applications (Database Theory, Abduction, ...)
  • Fixed-Parameter Tractability

Ablauf[Bearbeiten]

(Fast) jede Woche ist entweder ein Übungsblatt auszuarbeiten oder ein Review über ein Paper zu schreiben.

Benötigte/Empfehlenswerte Vorkenntnisse[Bearbeiten]

Theoretische Informatik und Logik bzw. Theoretische Informatik 1 und Algorithmen und Datenstrukturen sind ein Muss. Algorithmen auf Graphen ist hilfreich.

Vortrag[Bearbeiten]

In der Vorlesung wird alles sehr langsam, aber dadurch auch gut verständlich erklärt. Schläft man jedoch in der Vorlesung ein, empfiehlt es sich, aus den Folien zu lernen.

Übungen[Bearbeiten]

Sieben Übungsblätter (Aufwand mindestens 30 Minuten bis eine Stunde pro Blatt, in Extremfällen 10 Stunden). Diese sind so konstruiert, dass man mehr Zeit mit Nachdenken als mit Schreiben verbringt. Die Übungen sind entweder einfache Beispiele, die nach einem vorgegebenen Algorithmus berechnet werden müssen, oder man muss eine Reduktion aufstellen und/oder eine Beweisskizze dafür und/oder einen vollen Beweis angeben.

Zwei Paper-Reviews (Aufwand mindestens eine Stunde).

Prüfung[Bearbeiten]

Fand im SS07 im Konsens mit den Studierenden nicht statt (Note bestand nur aus den Bewertungen der Übungen und Paperreviews). Ob es auch in den nächsten Jahren dabei bleibt, ist noch unbekannt.

Im SS13 gabs auch keine Prüfung, das scheint die Regel zu sein (Die Prüfung ist quasi "zur Sicherheit" immer prinzipiell angekündigt, weil man sie wegfallen lassen darf, aber es wäre nicht erlaubt, eine durchzuführen, wenn das nicht von Anfang an so gesagt werden würde.)

Literatur[Bearbeiten]

Siehe LVA-HP

Zeitaufwand[Bearbeiten]

Je nach Vorkenntnissen und (mathematischen) Fähigkeiten des Teilnehmers von 25 Stunden aufwärts. Der durch die ECTS-Punkte vorgegebene Aufwand (75 Stunden) wird jedoch meiner Meinung nach nicht überschritten.

Verbesserungsvorschläge / Kritik[Bearbeiten]

noch offen