TU Wien:Algorithmics VU (Raidl)

Aus VoWi
Zur Navigation springen Zur Suche springen

Daten

Vortragende Günther Raidl, Stefan Szeider, Robert Ganian, Martin Nöllenburg, Friedrich Slivovsky, Martin Riedler
ECTS 6
Abteilung Forschungsbereich Algorithms and Complexity
Wann Wintersemester
Links tiss:186814
Zuordnungen
E033531 Pflichtmodul Algorithmik
E033537 Wahlmodul Algorithmik
Master Logic and Computation Pflichtmodul Algorithmics

Mattermost: Channel "algorithmics" Team invite & account creation link Mattermost-Infos

Inhalt

Man kann sich die LVA als eine Art Algorithmen und Datenstrukturen 3 vorstellen. Es werden wichtige Algorithmen aus verschiedenen Teilgebieten abgedeckt. Grob unterteilt werden folgende Themengebiete behandelt: Algorithmen auf Graphen (shortest path, network flows, planarity,...), randomisierte Algorithmen, Lineare Programmierung und Integer Linear Programming.

WS16/17: In der Vorlesung werden sechs Themengebiete behandelt:

  • Network Flows and Matchings
  • Geometric Algorithms (Closest Pair of Points, Sweep-Line Algorithms, Voronoi, Smallest Enclosing Disk)
  • Parameterized Algorithms (Bounded Search Tree, Kernelization)
  • Structural Decompositions and Algorithms (Tree Decomposition for Party Problem, Coloring, SAT)
  • Mathematical Programming (Linear Programming, (Mixed) Integer Linear Programming)
  • Planarity, A* Search, and Randomized Algorithms

Ablauf

Der Vorlesungsteil wird mit zwei Vorlesungen pro Woche leicht geblockt abgehalten.

WS16/17: Jedes der sechs Gebiete wird von einem anderen Vortragenden präsentiert, und es gibt zu jedem Gebiet eine Übung, die vom jeweiligen Vortragenden geleitet wird. Es gibt kein Programmierbeispiel mehr.

Benötigte/Empfehlenswerte Vorkenntnisse

Algorithmische Grundkenntnisse wie sie in Algodat vermittelt werden, werden vorausgesetzt. Wichtigste darüber hinausgehende Voraussetzung ist Interesse am Thema. Grundkentnisse der Wahrscheinlichkeitstheorie, wie sie in Statistik vermittelt werden, sind für den Teil über randomisierte Algorithmen nützlich.

Vortrag

Raidl, Leitner und Ruthmair tragen jeweils recht gut vor (d.h. in einem angemessenen Tempo und so, dass man es halbwegs versteht). Wenn man in die VOs geht und mitdenkt, erspart man sich viel lernen.

Übungen

  • WS17/18: 6 Übungen zu je 8 Bsp. Um 100 % auf die Übung zu erhalten reicht es, 75 % der Beispiele zu kreuzen. Man benötigt mindestens 37% der Kreuzerl, allerdings müssen 5 von 6 Übungsblätter gemacht (min. 3 Beispiele) werden.
  • WS16/17: Kein Programmierbeispiel, dafür 6 Kreuzerlübungen zu je 8 Beispielen. Um 100 % auf die Übung zu erhalten reicht es, 50 % der Beispiele zu kreuzen.

Prüfung, Benotung

Übungsbeispiele werden mit 0-4 Punkten beurteilt. Die Übungsgruppen sind klein, man muss also öfters Beispiele präsentieren. Zu beachten ist, dass ein Beispiel aberkannt und zusätzlich mit 0 oder 1 Punkt bewertet wird, wenn es falsch ist.

Ab WS16/17: Es gibt kein Programmierbeispiel mehr und die Prüfung ist schriftlich. Die Prüfung trägt 40 % zur Note bei, die Kreuzerlübungen 60 %. Für eine positive Note reicht es 40% der Punkte auf die Prüfung zu schaffen.

Dauer der Zeugnisausstellung

Zeugnis kam am Tag nach der mündlichen Prüfung. (WS 11/12) Zeugnis kam ca. eine Woche nach der mündlichen Prüfung (WS12/13) Ca. zwei Tage danach (WS 14/15)

Zeitaufwand

Mein Zeitaufwand (WS17/18): Ich habe ca 1 Woche recht intensiv für die Vorlesungsprüfung gelernt (habe in den Vorlesungen und Übungen leider nicht immer sehr aufgepasst) und habe einen 3er auf die Prüfung erhalten. Den Stoff würde ich generell als sehr anspruchsvoll bezeichnen.

Hängt stark von Vorwissen, Interesse und der gewünschten Note ab. Wer mit einem Genügend zufrieden ist wird sicher unter den 6*25=150 Stunden bleiben.

Mein Zeitaufwand: 1. Übungsblatt 1 Nachmittag (Stoff war mir bereits bekannt), 2. Übungsblatt 2 Tage, Programmieraufgabe 2 Tage, Lernen für die Prüfung 1 Woche. Note: Sehr Gut.

Mein Zeitaufwand (WS12/13): Pro Übungsblatt einen Tag; Programmieraufgabe ca. 3 Tage; 3 Tage (intensiv) lernen für die Prüfung (ich war fast immer in der VO)

Mein Zeitaufwand (WS15/16): Pro Übungsblatt einen Tag; 2 Tage lernen für die Prüfung (Disclaimer war nie in der Vorlesung)

Unterlagen

Vorlesungsfolien im TISS. Kein Skriptum.

Tipps

  • Bei den Übungsaufgaben wurden einige Beispiele aus der nicht mehr angebotenen LVA Algorithmen auf Graphen wiederverwendet. Diskussionen dazu gibt es im Informatik Forum[1] wenn man zu den Beiträgen aus den Jahren 2009 und 2010 zurückgeht.
  • Bei den Übungsaufgaben mehr als nur das Minimum machen, da das Wissen aus den Übungen sehr stark beim Lernen für die Prüfung hilft.

Verbesserungsvorschläge / Kritik

noch offen