TU Wien:Approximation Algorithms VU (Kellerer)
Daten[Bearbeiten | Quelltext bearbeiten]
| Vortragende | Hans Kellerer |
|---|---|
| ECTS | 3,0 |
| Letzte Abhaltung | 2024W |
| Sprache | Deutsch |
| Mattermost | approximation-algorithms • Register • Mattermost-Infos |
| Links | tiss:186102 |
Inhalt[Bearbeiten | Quelltext bearbeiten]
- Absolute performance guarantees (and graph coloring)
- Relative performance guarantees (and graph theory)
- Scheduling problems (and polynomial time approximation schemes)
- Bin Packing problem (and asymptotic polynomial time approximation schemes)
- Knaksack problem (and fully polynomial time approximation schemes)
- Linear programming (This topic might be skipped if there is not enough time.)
Generell versucht der Vortragende viele Themen zu behandeln. Die Qualität bleibt dabei meiner Meinung nach auf der Strecke.
Ablauf[Bearbeiten | Quelltext bearbeiten]
Vorlesung wird stark geblocked abgehalten. Vorlesungszeiten sind sehr unregelmäßig und hauptsächlich Montag und Freitag Abend, können aber bei Bedarf angepasst werden, damit alle Interessierten teilnehmen können. Im SS2013 war die erste VO Mitte April. Die Übungstermine finden während der regulären VO-Einheiten statt.
Benötigte/Empfehlenswerte Vorkenntnisse[Bearbeiten | Quelltext bearbeiten]
Nicht benötigt aber hilfreich da Stoff sich teilweise überschneidet:
- Algorithmics (Erstes Drittel zu Graphen, letztes Drittel für Scheduling. Wer IP/LP versteht, versteht die Hintergründe ein bisschen besser, ist aber überhaupt nicht notwendig)
- Diskrete Mathematik (Graphen)
Benötigte Vorkenntnisse laut Vortragendem:
- NP-completeness theory
- basic graph theory
- dynamic programming
- linear programming
Vortrag[Bearbeiten | Quelltext bearbeiten]
Der Vortrag ist ziemlich chaotisch. Bei den Beweisen gibt es viele hand-waving Argumente.
Übungen[Bearbeiten | Quelltext bearbeiten]
SS2016: Drei Übungsblätter mit je etwa 10 Beispielen. Die Beispiele sind nicht trivial. Abgabe: in Latex oder handschriftlich, per Email oder in Papierform in der Vorlesung. Übungen können in Gruppen gemacht werden. Die Beispiele werden in der Vorlesung nur sehr kurz besprochen, d.h. meist nicht an der Tafel sondern nur in Worten. Es reichen auch Beweis-Skizzen an Stelle von Beweisen.
Prüfung, Benotung[Bearbeiten | Quelltext bearbeiten]
Prüfung SS14: 6 Beispiele, es wird nicht erwartet alle zu lösen. Einige waren sehr ähnlich zu den Übungen, ein Beispiel konnte ich gar nicht zu ordnen. Benotung SS14: Sehr fair, 3 (vermutlich 4 auf die Prüfung + viele Übungsbeispiele, weiß es aber nicht genau).
Prüfung SS16: 4 Beispiele, 2 davon über Scheduling.
Dauer der Zeugnisausstellung[Bearbeiten | Quelltext bearbeiten]
SS 14: 1 Woche
Zeitaufwand[Bearbeiten | Quelltext bearbeiten]
SS 14 Hoch. Es wird zwar nicht erwartet alle Übungsbeispiele zu lösen, aber aufgrund der intransparenten Benotung und weil die meisten Beispiele zur Prüfung kommen können, ist es im Grunde notwendig alle zu lösen um auch selbst Ausarbeitungen zu besitzen. Kenntnisse über Komplexitätsklassen helfen und Verständnis von Reduktionsbeweisen sowie Induktionsbeweisen sind Voraussetzung.
Übungen können in 2er Gruppen gelöst werden, es gab aber auch Studenten welche sie alleine gelöst haben. Ich persönlich fand die Übungen teilweise extrem schwer und hätte sie alleine nicht lösen können. Sich selbstständig mit allen Beispielen zu beschäftigen, bleibt einem dabei trotzdem nicht erspart um für die Prüfung zu lernen.
Unterlagen[Bearbeiten | Quelltext bearbeiten]
noch offen
Tipps[Bearbeiten | Quelltext bearbeiten]
SS 14 Unbedingt alles sauber mitschreiben. Es gibt für das meiste keine Unterlagen und auch wenn manchmal Folien präsentiert werden ist es fast essentiell die Ausführungen selbst schriftlich festzuhalten.
In den Übungsstunden unbedingt darauf bestehen alle Beispiele die unklar sind zu besprechen und auch selbst mitzuschreiben, andernfalls ist ein richtiges Lösen bei der Prüfung nicht möglich, da man selbst vielleicht davon ausgeht seine Lösung sei korrekt oder weil man das Beispiel nicht gelöst hat.
Highlights / Lob[Bearbeiten | Quelltext bearbeiten]
noch offen
Verbesserungsvorschläge / Kritik[Bearbeiten | Quelltext bearbeiten]
Meiner Meinung nach Braucht man für diese LVA vor allem starke Nerven: Sehr viele Themen, jedes davon sehr kurz, sehr schlecht vorgetragen, in schlechtem Englisch, fast keine Unterlagen (Vortrag mit Tafel)!