TU Wien:Algorithmen auf Graphen VU (Chwatal)
- Algorithmen auf Graphen VU (Chwatal) (TU Wien, veraltet, 3 Materialien)
- Algorithmen auf Graphen VU (Saturni) (TU Wien, veraltet, 3 Materialien)
Daten[Bearbeiten | Quelltext bearbeiten]
| Vortragende | Univ.Ass. Dipl.-Ing. Andreas Chwatal, Univ.Ass. Dipl.-Ing. Mario Ruthmair, Univ.Ass. Dipl.-Ing. Matthias Prandtstetter |
|---|---|
| ECTS | 3 |
| Sprache | English |
| Links | tiss:186145 , Homepage |
| Masterstudium Logic and Computation | |
| Masterstudium Software Engineering & Internet Computing | |
| Masterstudium Technische Informatik |
Inhalt[Bearbeiten | Quelltext bearbeiten]
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[Bearbeiten | Quelltext bearbeiten]
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[Bearbeiten | Quelltext bearbeiten]
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[Bearbeiten | Quelltext bearbeiten]
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[Bearbeiten | Quelltext bearbeiten]
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[Bearbeiten | Quelltext bearbeiten]
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[Bearbeiten | Quelltext bearbeiten]
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[Bearbeiten | Quelltext bearbeiten]
Die Folien werden auf der Webseite der Lehrveranstaltung zum Download bereitgestellt.
Tipps[Bearbeiten | Quelltext bearbeiten]
- 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[Bearbeiten | Quelltext bearbeiten]
noch offen