TU Wien:Algorithmics VU (Szeider)
Daten[Bearbeiten | Quelltext bearbeiten]
| Vortragende | Jan Niclas Dreier• Robert Ganian• Enrico Iurlano• Martin Nöllenburg• Tomas Peitl• Vaidyanathan Peruvemba Ramaswamy• Günther Raidl• Stefan Szeider |
|---|---|
| ECTS | 6,0 |
| Letzte Abhaltung | 2024W |
| Sprache | English |
| Mattermost | algorithmics • Register • Mattermost-Infos |
| Links | tiss:186814 |
Inhalt[Bearbeiten | Quelltext bearbeiten]
Man kann sich die LVA als eine Fortsetzung der Bachelor-LVA Algorithmen und Datenstrukturen 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
WS23/24: Selbe Themengebiete in völlig anderer Reihenfolge
Ablauf[Bearbeiten | Quelltext bearbeiten]
Der Vorlesungsteil wird mit zwei Vorlesungen pro Woche leicht geblockt abgehalten.
WS23/24: Weiterhin die sechs Kapitel, die jeweils von einem anderen Vortragen präsentiert werden. Kreuzerlübungen mit Tafelleistung, jedes Mal ist der Vortragende des Kapitels auch die UE-Leitung dieser EInheit. Am Ende gibt es eine schriftliche Prüfung.
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 | Quelltext 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 Statistik vermittelt werden, sind für den Teil über randomisierte Algorithmen nützlich.
Vortrag[Bearbeiten | Quelltext 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 | Quelltext bearbeiten]
- WS23/24: wie WS17/18. Sonderregeln: wer (mehr als...) 90% aller Beispiele gemacht hat muss theoretisch nicht zum Test. Bewertung der Tafelleistung ist schwer vom Übungsleiter abhängig. In einer Übung hat bekam ich nicht ein Wort gegen meine Lösung, es gab nichts zu verbessern oder zu diskutieren. Am Ende fragte ich nach meine Tafelleistung, (frei übersetzt "kann er noch nicht sagen"?!) waren dann 3/4 Punkte (ohne eines einzigen Kritikpunktes). Eine andere Präsentation war komplett daneben, trotzdem 2/4 Punkte bekommen. Gibt hier kein klares Bewertungsschema.
- 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[Bearbeiten | Quelltext bearbeiten]
2023W: Die schriftliche Prüfung macht 40% der Gesamtnote aus. Man muss 20/50 Punkte bei dieser erreichen, es sei denn, man hat 90% bei der Übung gekreuzt - dann fällt dieser Constraint weg. Die Kreuze der Übung machen weitere 40% aus, die restlichen 20% kommen von der Tafelleistung in der Übung. 75% der Kreuze in der Übung reichen aus, um die vollen 40 Kreuzerl-Punkte zu erreichen (bei 37% würde man 20 erhalten etc. - man sollte nur mehr als 75% kreuzen, um die 90% der Kreuze zu erreichen, falls man keinen Bock auf den Test hat). Man muss mindestens 37% der Beispiele kreuzen und mindestens 50% bei der Tafelleistung erreichen, um eine positive Note bekommen zu können. Sind die Constraints erfüllt, ergibt sich folgender Schlüssel:
| Note | Punkte |
|---|---|
| Sehr gut | 87.5 - 100 |
| Gut | 75 - 87 |
| Befriedigend | 62.5 - 74.5 |
| Genügend | 50 - 62 |
| Nicht genügend | 0 - 49.5 |
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. Ü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.
2020W: Aufgrund von COVID wurde die Prüfung online abgehalten, es waren weiterhin nur 90 Minuten Zeit aber man musste für eine positive Note 50% der Punkte erreichen. Gleichzeitig wurde die Prüfung massiv schwieriger gemacht und die Arbeitsumgebung während der online Prüfung war alles andere als angenehm - als Resultat haben viele eine negative Note auf die Prüfung erhalten. Sollte der Grad an Schwierigkeit beim aktuellen Modus beibehalten werden kann ich von der (ansonst sehr interessanten und gut gemachten) LVA nur massiv abraten!
UPDATE: Als Reaktion auf den zu schwierigen Test wurde der Notenschlüssel in diesem Semester um 4.5 Prozentpunkte zu gunsten der Studierenden herabgesetzt und der Nachtest war sehr human.
2022W: The exam has 50 points, 10 points each for four chapters, 5 points for the other two. One of the profs said they randomly choose each year who gets the 5 point questions, and they take care that those can be done quicker.
Dauer der Zeugnisausstellung[Bearbeiten | Quelltext 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 | Quelltext bearbeiten]
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)
Mein Zeitaufwand (WS23/24): Pro Übungsblatt 1-3 Tage (jeweils versucht alle Beispiele zu lösen). Stoff meiner Meinung nach sehr Umfangreich und involviert. Ausreichend Beispiele für eine Positive Note sollte recht einfach mit wesentlich weniger Zeit möglich sein (gab immer 2 oder 3 leichte Beispiele), aber wer versucht alles zu lösen benötigt einiges an Zeit.
Mein Zeitaufwand (WS23/24): Pro Übungsblatt 1-3 Tage, Planarity, A* und Randalg konnte ich noch großteils lösen (7/8 Beispiele), allerdings nur mit den vollen 3 Tage Aufwand. Gleiches für Network Flows & Matchings (6/8 Beispiele). Die anderen Themen haben mich Lebensfreude und Motivation gekostet. Nach 2 Tagen gerade mal die notwendigen 3 Beispiele geschafft. In der MILP Übung waren die ersten 3 Beispiele als "warming up" angegeben, wobei diese Beispiele zu den schwierigsten gehörten. Prüfungsergebnis steht noch aus, aber ich bin kaum mit 6 ECTS ausgekommen, und mehr als einen 4er erwarte ich mir nicht.
Unterlagen[Bearbeiten | Quelltext bearbeiten]
Vorlesungsfolien im TISS. Kein Skriptum. WS23/24: Vorlesungsaufzeichnungen in Tuwel waren sehr hilfreich (manchmal hat die Aufzeichnung nicht funktioniert, dann gab es alte Videos)
Tipps[Bearbeiten | Quelltext 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 | Quelltext bearbeiten]
noch offen