TU Wien:Algorithmen auf Graphen VU (Chwatal)
- Algorithmen auf Graphen VU (Chwatal) (TU Wien, veraltet, 3 Resources)
- Algorithmen auf Graphen VU (Saturni) (TU Wien, veraltet, 3 Resources)
Daten[edit | edit source]
| Lecturers | Univ.Ass. Dipl.-Ing. Andreas Chwatal, Univ.Ass. Dipl.-Ing. Mario Ruthmair, Univ.Ass. Dipl.-Ing. Matthias Prandtstetter |
|---|---|
| ECTS | 3 |
| Department | Forschungsbereich Algorithms and Complexity |
| Language | English |
| Links | tiss:186145, Homepage |
Inhalt[edit | edit source]
Topologisches Sortieren; Kürzeste Wege (Dijkstra, Bellman-Ford, Matrik-Multiplikation, Floyd-Warshal, Johnson);
Netzwerkflussalgorithmen: Max-Flow, Min-Cost-Flow, Min-Cut;
Hamiltonsche Zyklen; TSP-Heuristiken: Minimum Spanning Tree, Christofides; Matchings;
Ablauf[edit | edit source]
Es gibt wöchentlich eine 90-minütige Vorlesung. Nach je drei Vorlesungseinheiten gibt es eine Übungseinheit, im Rahmen derer die Teilnehmer der Lehrveranstaltung Übungsbeispiele, die auf auf der Webseite der Lehrveranstaltung zum Download zur Verfügung gestellten Übungsblättern zu finden sind, an der Tafel präsentieren. Für ein positives Absolvieren der Übung sind 70 % der Beispiele zu kreuzen.
Benötigte/Empfehlenswerte Vorkenntnisse[edit | edit source]
Der vorhergehende Besuch von Algorithmen und Datenstrukturen 1 ist zwar nicht unbedingt erforderlich, jedoch sehr empfehlenswert. Der Algorithmus von Dijkstra sowie die MST- und die Christofides-Heuristik für das TSP werden wiederholt.
Vortrag[edit | edit source]
Andreas Chwatal: langweilig. WS09: es geht
Mario Ruthmair: WS09: langweilig
Matthias Prandtstetter: langweilig. WS09: extrem langweilig
Aufmerksamkeit in den Vorlesungseinheiten ist erforderlich, da sich die Beweise für die Korrektheit der vorgestellten Algorithmen zum Großteil nicht auf den zum Download zur Verfügung gestellten Vorlesungsfolien befinden und daher mitgeschrieben werden müssen.
Übungen[edit | edit source]
Nach je drei Vorlesungseinheiten gibt es eine Übungseinheit, im Rahmen derer die Teilnehmer der Lehrveranstaltung Übungsbeispiele, die auf auf der Webseite der Lehrveranstaltung zum Download zur Verfügung gestellten Übungsblättern zu finden sind, an der Tafel präsentieren. Das erste Übungsblatt ist noch recht einfach und schnell zu lösen, für die weiteren Übungsblätter steigt der Aufwand dann.
Die Lösungen müssen absolut nicht perfekt sein, um akzeptiert zu werden.
Ich habe im WS10/11 ca. 1-2 Abende fuer das erste Blatt investiert, 3-5 fuer 2. und 3. Im Informatikforum werden die Beispiele diskutiert und man kann dort oft Ansaetze und teils auch Loesungen in Erfahrung bringen. -- Tresh 11:07, 2. Mär. 2011 (CET)
Prüfung, Benotung[edit | edit source]
Am Ende des Semesters gibt es eine mündliche Prüfung. Die Gesamtbeurteilung ergibt sich aus Übung und Vorlesungsprüfung, wobei die Übung zu einem Drittel in die Gesamtbeurteilung einfließt. Bei der Prüfung stellt jeder Vortragende eine Frage aus seinem Gebiet. Die Folien sollten ausreichen, wobei die fehlenden Beweise, die vorgetragen wurden, auch hilfreich sind. Zumindest die einfachen Beweise sollte man ganz grob können, wobei hier die Prüfer entsprechend weiterhelfen. Es herrscht ein sehr lockeres Gesprächsklima und mit entsprechender Vorbereitung ist die Prüfung auf jeden Fall schaffbar.
Prüfungsfragen finden sich bei den Materialien.
Zeitaufwand[edit | edit source]
Angemessen für eine 2stündige VU. Die 3 Übungsblätter sind jeweils an einem Abend schaffbar (zumindest um ausreichend Beispiele zu kreuzen und wenn man in der Vorlesung nicht geschlafen hat), für die Prüfung sind ein paar Tage investierte Zeit empfehlenswert.
Unterlagen[edit | edit source]
Die Folien werden auf der Webseite der Lehrveranstaltung zum Download bereitgestellt.
Tipps[edit | edit source]
- Die Beweise zu den Sätzen, welche auf den Folien zu finden sind, werden vom Vortragenden an der Tafel präsentiert bzw. skizziert. Es empfiehlt sich, diese Beweise mitzuschreiben, da sie nicht auf den Folien zu finden sind.
Verbesserungsvorschläge / Kritik[edit | edit source]
noch offen