TU Wien:Algorithmen auf Graphen VU (Chwatal)

Aus VoWi
Wechseln zu: Navigation, Suche
Diese LVA wird nicht mehr von dieser Person angeboten, ist ausgelaufen, oder läuft aus und befindet sich daher nur noch zu historischen Zwecken im VoWi. Eventuell findest du über dieser Meldung noch andere Vortragende, oder Links für dieselbe LVA.


Daten[Bearbeiten]

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

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]

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]

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]

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]

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]

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]

Die Folien werden auf der Webseite der Lehrveranstaltung zum Download bereitgestellt.

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

noch offen