TU Wien:Algorithmics VU (Raidl, Leitner, Ruthmair)

Aus VoWi
Wechseln zu: Navigation, Suche


Daten[Bearbeiten]

Inhalt[Bearbeiten]

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[Bearbeiten]

Der Vorlesungsteil wird mit zwei Vorlesungen pro Woche leicht geblockt abgehalten. Es sind außerdem drei Kreuzerlübungen und ein Programmierbeispiel zu absolvieren.

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[Bearbeiten]

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 Statisk vermittelt werden, sind für den Teil über randomisierte Algorithmen nützlich.

Vortrag[Bearbeiten]

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[Bearbeiten]

3 Kreuzerlübungen und 1 Programmieraufgabe zu Integer Linear Programming.

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.

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.

Prüfung, Benotung[Bearbeiten]

Alt: Die Note setzt sich aus der Prüfung (50%), den Übungsblättern (25%) und der Programmieraufgabe (25%) zusammen. Im WS 11/12 (und auch im WS12/13) wurde die Prüfung mündlich zum Ende des Semesters abgehalten. Zu Beginn des Semesters wurde gesagt, dass der Typ der Prüfung (mündlich/schriftlich) von der Teilnehmerzahl abhängt. Bei der Prüfung wird stark auf Verständnis gefragt. Es wird nicht bis ins letzte Detail gefragt, was auf Grund der Menge des Stoffes auch schwer möglich wäre zu beantworten. Beweise muss man nicht völlig korrekt aufschreiben können, aber es wird erwartet, dass man die Beweisidee kennt und den Ablauf grob erklären kann.

WS12/13: Vor allem das Verständnis und die Erklärung der Programmieraufgabe waren wichtig. Formeln oder Beweise wurden nicht gefragt. Bei einer Prüfungsfrage zu Markov/Chernoff/Chebychef wurde gleich dazugesagt, dass die Formeln nicht aufgesagt werden müssen-

WS14/15: Je eine Frage pro Gruppenmitglied, einmal Shortest Path Problem, dazu Bellman Ford erklaeren, aufzeichnen, durchgehen und Laufzeit angeben, dann noch weiter Shortest Path zwischen allen Knoten mit Floyd Warshall, wiederum das selbe, wobei der Dynamic Programming Aspekt wichtig war. Im Anschluss wurde das Programmierbeispiel durchgegangen, das abgegebene Dokument wurde besprochen und Fragen zu diversen Constraints, Objective function etc. gestellt. Fragen zu CPLEX, wie zur genauen Funktionsweise wurden auch gestellt. Insgesamt waren die Fragen schon detailliert, Formeln oder Beweise wurden jedoch nicht gefragt.

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[Bearbeiten]

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[Bearbeiten]

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)

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.

Unterlagen[Bearbeiten]

Vorlesungsfolien im TISS. Kein Skriptum.

Tipps[Bearbeiten]

  • 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[Bearbeiten]

noch offen