TU Wien:Komplexitätstheorie VU (Pichler)
Daten[Bearbeiten | Quelltext bearbeiten]
| Vortragende | Reinhard Pichler |
|---|---|
| ECTS | 3,0 |
| Alias | Complexity theory (en) |
| Letzte Abhaltung | 2024W |
| Sprache | English |
| Mattermost | komplexitaetstheorie • Register • Mattermost-Infos |
| Links | tiss:181142, eLearning, Homepage |
Inhalt[Bearbeiten | Quelltext 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 | Quelltext bearbeiten]
(Fast) jede Woche ist entweder ein Übungsblatt auszuarbeiten oder ein Review über ein Paper zu schreiben.
WS 2021/22 Keine Übungsblätter mehr. Dafür Eintrittstest, schriftlicher Test und (optionaler) mündlicher Test.
Benötigte/Empfehlenswerte Vorkenntnisse[Bearbeiten | Quelltext bearbeiten]
Theoretische Informatik und Logik bzw. Theoretische Informatik 1 und Algorithmen und Datenstrukturen sind ein Muss. Formale Methoden der Informatik wird am Anfange schnellt wiederholt, allerdings sollte man zumindest den ersten Teil (NP, Reduktionen) bereits können. Ansonsten ist der Zutrittstest vielleicht etwas schwieriger. Algorithmen auf Graphen ist hilfreich.
Vortrag[Bearbeiten | Quelltext 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 | Quelltext 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).
WS 2021/22: Keine Übungen
Prüfung[Bearbeiten | Quelltext 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.)
WS 2021/22:
Eintrittstest: Beweise Korrektheit einer NP-Hardness Reduktion. (Reduktion selbst ist bereits gegeben)
Schriftlicher Test: Beweise Korrektheit einer Π2P Reduktion. (Reduktion wieder gegeben)
Mündlicher Test: Theorie-Fragen. Note kann sich durch mündlichen Test um max. 1 verschlechtern/verbessern oder gleich bleiben. Wenn man mit Note aus schriftlichem Test - 1 zufrieden ist, muss man nicht zum mündlichen Test antreten
WS2023/24: Eintrittstest: Beweis Korrektheit einer NP-Hardness Reduktion (Vertex Cover <-> Dominating Set). Schriftliche Prüfung war exakt gleich wie WS2021 (siehe Materialien)
Literatur[Bearbeiten | Quelltext bearbeiten]
Siehe LVA-HP
Zeitaufwand[Bearbeiten | Quelltext 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.
WS 2021/22
Wöchentliche Vorlesung. Drei freiwillige - unbenotete - Beispiele, die man als Vorbereitung für das Exam machen kann und in der Vorlesung durchgegangen wurde. Schriftliches Exam benötigt nicht viel Vorbereitung, wenn man Reduktionen einigermaßen beherrscht. Darum Aufwand für 3 ECTS eigentlich sehr gering.
Highlights / Lob[Bearbeiten | Quelltext bearbeiten]
noch offen
Verbesserungsvorschläge / Kritik[Bearbeiten | Quelltext bearbeiten]
noch offen