TU Wien:Algorithmen und Datenstrukturen 2 VU (Raidl)
- Algorithmen und Datenstrukturen 2 VO (Raidl) (TU Wien, veraltet, 16 Materialien)
- Algorithmen und Datenstrukturen 2 VU (Raidl) (TU Wien, veraltet, 16 Materialien)
- Algorithmen und Datenstrukturen 2 VU (Raidl, vor 2006) (TU Wien, veraltet, 1 Material)
Daten[Bearbeiten | Quelltext bearbeiten]
| Vortragende | Szeider, Raidl |
|---|---|
| ECTS | 3 |
| Ersetzt | Algorithmen und Datenstrukturen 2 VO (Raidl) |
| Sprache | English |
| Links | tiss:186815 , Homepage |
Inhalt[Bearbeiten | Quelltext bearbeiten]
Die Lehrveranstaltung baut natürlich auf Algorithmen und Datenstrukturen 1 auf und sollte auch der Reihenfolge danach gemacht werden. Wer bereit ist, Big-O-Notationen für Laufzeiten und Graphentheorie nachzulernen (wird auch in den Mathe-LVAs behandelt), sollte es aber auch ohne die vorige schaffen.
ALGODAT ist Software Engineering im pursten Sinne, kein Softwaremanagement, kein Lernen von Java API-Kolossen. Das kann Spaß machen, da man Algorithmen kennen lernt, die wirklich erstaunliches leisten und motivieren, das später auch selbst anzuwenden. Dafür ist es auch wesentlich mathematischer (wobei mehr auf Intuition und praktische Anforderungen gesetzt wird als in reinen Mathe-Vorlesungen). Es ist sicher eine eher komplexe VU aber der Stoff sollte für einen Informatiker interessant genug sein, dass man sich freiwillig gern in die Materie einliest.
Die VU wurde mit SS2016 komplett neu aufgerollt, Unterlagen aus vorigen Semestern sind damit nur noch bedingt bis gar nicht hilfreich.
- Polynomialzeitreduktion
- Branch-and-Bound
- Approximationsalgorithmen
- Heuristiken und lokale Suche
- Dynamische Programmierung
- Weitere Themen (z.B. Textsuche, Randomisierung, geometrische Algorithmen)
Benötigte/Empfehlenswerte Vorkenntnisse[Bearbeiten | Quelltext bearbeiten]
Das Wissen aus Algorithmen und Datenstrukturen 1 ist auf jeden Fall nützlich: Theta-Notation, Datenstrukturen oder Quicksort begegnen einem immer wieder.
Vortrag[Bearbeiten | Quelltext bearbeiten]
Die Vorträge wechseln zwischen sehr gut und angenehm erklärt und teilweise etwas verworren (das Rucksackproblem-Beispiel in dynamische Programmierung zum Beispiel musste ich zuhause nochmal googeln). Die Vorlesungen wurden auch als Videostream zum Nachsehen zur Verfügung gestellt (wo das Aufnehmen funktionierte). Da auch Beispiele vorgerechnet werden, ist sie als Vorbereitung für Übung und Prüfung unerlässlich.
Übung[Bearbeiten | Quelltext bearbeiten]
Es gibt zwei Ankreuz-Übungen mit je 8 Beispielen, wobei es auf Beispiele 1 oder 2 Punkte geben kann. Insgesamt kann man maximal 20 Punkte erreichen, 8 Punkte sind Minimum. Man wird zufällig aufgerufen. Die Bewertung ist recht human: Wer das Beispiel zu dem man aufgerufen wird kann (auch bei minimalen Rechenfehlern) bekommt alle gekreuzten Punkte. Wer etwas hat, aber sehr große Fehler hat bzw. die Angabe missinterpretiert hat, kann die Punkte für das präsentierte Beispiel aberkannt bekommen, behält aber den Rest der gekreuzten Beispiele. Wer gar nichts hat bzw. offensichtlich spekuliert hat oder nicht erscheint, bekommt keine der gekreuzten Beispiele der Übungseinheit anerkannt. Vertut man sich mit dem Hinaufladen der Lösungen bzw. Kreuzen wird in maximal einer Übungseinheit ein Auge zugedrückt, wenn man sich rechtzeitig bei der LVA-Leitung meldet und das klärt.
Programmierbeispiel[Bearbeiten | Quelltext bearbeiten]
Der wahre "Brocken" der LVA. Hier muss meistens ein Branch and Bound Algorithmus implementiert werden mit gutem ersten Schätzwert und lokalen oberen und unteren Schranken für die Verzweigung. Das kann recht kompliziert sein. Es gibt 5 Testinstanzen zum selbst testen und weitere 10 "geheime" am Abgabeserver. Da das Programm bis zu 30 Sekunden pro Instanz laufen kann, dauert das Abarbeiten des Abgabeergebnises oft recht lange, in den letzten Tagen vor der Deadline oft 'Stunden', wenn man in die Warteschleife kommt. Da man alle Instanzen unter einen Schwellwert bringen muss und der Abgabeserver etwas mit Rückgabe-Informationen geizt, kann das Korrigieren, Warten und erneute Testen im Fall einer negativen Abgabe einem schnell ins Schwitzen bringen. Es gibt maximal 30 Abgabeversuche.
Es kann gar nicht genug betont werden, wie wichtig es ist, früh (also am besten am Tag der Angabe) zu beginnen! Das wird immer gesagt, aber in dieser LVA mehr als sonst wo kann das zwischen Erfolg und Durchfallen entscheiden. Fängt man eher spät an (also ein paar Tage vor der Abgabe), so sollte man seine Aktivitäten in die frühen Morgenstunden (05.00 - 12.00 Uhr) verlagern. Hier ist der Abgabeserver auch kurz vor der Deadline am geringsten ausgelastet und liefert in vergleichsweise kurzer Zeit ein Ergebnis. Am Abend und in der Nacht gibt es üblicherweise Wartezeiten von einigen Stunden, da so viele Programme in der Abgabequeue sind.
Es gibt 11 Basis-Punkte wenn man es geschafft und Branch and Bound verwendet hat, maximal 3 Bonuspunkte wenn man möglichst viele Testinstanzen optimal löst und maximal 6 Punkte für gute Implementierung der einzelnen Schritte.
Prüfung[Bearbeiten | Quelltext bearbeiten]
Seit SS 2016: Es gibt drei große Beispiele die alle in etwa gleich viele Punkte bringen, wobei diese Beispiele in ungefähr jeweils 2 Unterbeispiele aufgeteilt sind. Beim 1. Test im SS 2016 waren die Beispiele Weighted Vertex Cover (analog zu Weighted Set Cover, wie in den Folien beschrieben), Weighted Vertex Cover und Komplexität sowie das Rucksackproblem mit Hilfe von Branch and Bound lösen. Ein Unterbeispiel waren Multiple-Choice-Fragen mit jeweils 4 Antwortmöglichkeiten. Für alle richtigen Kreuze bekam man pro Frage 4 Punkte, hat man ein Kreuz falsch gesetzt (oder nicht gesetzt), bekam man noch 1 Punkt, ansonsten 0 Punkte. Laut LVA-Leitung werden gültige Unterschritte auch bei Folgefehlern besser berücksichtigt.
Benotung[Bearbeiten | Quelltext bearbeiten]
Punkte: 20 (min 8) für die Übung, 20 (min 11) für die Programmieraufgabe, 50 (min 26) für den Test
[79; 90] S1 Sehr gut
[68; 79[ U2 Gut
[57; 68[ B3 Befriedigend
[45; 57[ G4 Genügend
[0; 45[ N5 Nicht genügend
Im SS 2016 reichten 25 Punkte auf den Test für eine positive Note, wobei man insgesamt immer noch 45 Punkte erreichen musste.
Dauer der Zeugnisausstellung[Bearbeiten | Quelltext bearbeiten]
SS12: 4 Wochen
SS15: Test am 25.6., Ergebnisse waren am 7.7. da, also rund zwei Wochen, die Zeugnisse selbst dann noch etwa eine Woche darauf.
SS16: Test am 23.6., Ergebnisse waren am 4.7. da, also ca. 1,5 Wochen, die Zeugnisse selbst dann noch etwa eine Woche darauf.
Literatur[Bearbeiten | Quelltext bearbeiten]
Es wird leider kein Skriptum mehr angeboten, nur noch die Foliensätze. Die sind zwar recht übersichtlich gestaltet, aber halt wie Präsentationsfolien das so in sich haben nur bedingt zum Lernen geeignet. Teilweise hat man das Gefühl, es ist wichtiger Inhalte auf einer Folie unterzubringen als z.B. einen Absatz mehr mit guter Erklärung.
Zeitaufwand[Bearbeiten | Quelltext bearbeiten]
Üblich für die 2 Übungen, sehr hoch für die Programmieraufgabe. Dafür auf jeden Fall genug Zeit (ca. 20h laut ECTS-Breakdown, wenn man sich wo vertut kann der auch weit höher liegen!) einplanen. Da Abgaben am Server zum Durchrechnen über 3 Minuten pro Person/Abgabe dauern können, kann die Wartezeit schon mal mehrere Stunden betragen! Die "geheimen" Testdaten oder spezielle Anforderungen des Abgabeservers (multi-threading führt beispielsweise zu Problemen) bedeuten auch, dass oft Zeit damit drauf gehen kann, die oft sehr kargen/nicht-existenten Fehlerrückmeldungen im Abgabesystem zu interpretieren und zu korrigieren. Wer erst in den letzten 3 Tagen mit dem Programmierbeispiel anfängt, spielt mit einem realen Risiko es nicht rechtzeitig zu schaffen. Am besten bereits sofort nachdem die Angaben draußen sind beginnen (spreche aus Erfahrung)!
Andere Erfahrung: - den sehr hohen Aufwand für die Programmieraufgabe kann ich so nicht bestätigen. Hab ohne Vorerfahrungen ca. 5 Stunden für die komplette Aufgabe (Branch & Bound) gebraucht (1 Stunde zum Einlesen, den Rest für die Implementierung) und volle Punktezahl erhalten.
Es kommt hier sehr stark darauf an wieviel Vorwissen man bringt und welche Aufgabe gestellt wird. Bin im SoSe 14 angetreten und da war Branch&Bound für das TSP gegeben, was ich nicht rechtzeitig fertig stellen konnte. Im SoSe 15 kam Branch&Bound für quasi BinPacking und das war in 2 Nachmittagen erledigt.
Hilfreiche Links[Bearbeiten | Quelltext bearbeiten]
noch offen
Verbesserungsvorschläge / Kritik[Bearbeiten | Quelltext bearbeiten]
Bring back the Skriptum!