TU Wien:Approximation Algorithms VU (Kellerer)

From VoWi
Jump to navigation Jump to search
The printable version is no longer supported and may have rendering errors. Please update your browser bookmarks and please use the default browser print function instead.

Daten

Lecturers a.o.Univ.Prof. Hans Kellerer
ECTS 3
Department Forschungsbereich Computer Graphics
Links tiss:186102, Homepage, Mattermost-Channel
Zuordnungen
Master Logic and Computation Wahlmodul Algorithms and Complexity
Master Visual Computing Wahlmodul Methoden für Visual Computing
Master Software Engineering & Internet Computing Wahlmodul Algorithmik

Mattermost: Channel "approximation-algorithms"RegisterMattermost-Infos

Inhalt

  • 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

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

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

Der Vortrag ist ziemlich chaotisch. Bei den Beweisen gibt es viele hand-waving Argumente.

Übungen

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

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

SS 14: 1 Woche

Zeitaufwand

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

noch offen

Tipps

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.

Verbesserungsvorschläge / Kritik

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)!

Attachments

This page has no attachments yet but you can add some.