TU Wien:Algorithmen auf Graphen VU (Saturni)

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.


Dr. Saturni hat die TU verlassen.

Daten[Bearbeiten]

Inhalt[Bearbeiten]

Shortest paths, Network flows, Maximal flow, Hard or Intractable problems, Matchings and covers in bipartite graphs, Minimum Spanning Tree Problem, Polytopes, polyhedra and linear programming - wobei die letzteren drei Themen aufgrund von Zeitmangels im WS 06 nicht behandelt wurden.

Ablauf[Bearbeiten]

Geblockt im Oktober und November. Nach der Vorbesprechung gibt es 3 Blöcke, die aus 3 Vorlesungseinheiten und einer Übungseinheit, die zu 10% in die Endnote einfließt, bestehen. Zum Schluss gibt es eine Prüfung über den Stoff, welche mit 70% in die Note einfließt.

Empfehlenswerte Vorkenntnisse[Bearbeiten]

Algorithmen und Datenstrukturen 1 VL, vielleicht ein bisschen Graphentheorie aus Mathematik 1 VO. Sollten die Vorkenntnisse fehlen, kein Problem; in der ersten VO-Einheit wird alles noch einmal wiederholt (besonders günstig, wenn man sich mit den englischen Begriffen noch nicht so auskennt).

Vortrag[Bearbeiten]

Der Vortrag von Dr. Saturni hat sich eindeutig gebessert; war er noch in der ersten VO-Einheit kaum zu verstehen, spricht er jetzt lauter und deutlicher, auch sein Tafelbild hat sich wesentlich verbessert. Leider schweift er gerne ab, um einen Beweis zu führen, welcher bis zu einer halben Vorlesung dauern kann und am Ende sich doch als falsch entpuppt. Auch gibt es inzwischen zu den Vorlesungen "lecture notes" auf der Homepage. Die Sprache sowohl der Vorlesung als auch der Unterlagen ist Englisch.

Übungen[Bearbeiten]

3 Übungstermine zu je 8 bis 12 Beispielen, Kreuzerlübungen. Die Beispiele der ersten Übungsrunde sind nicht übermäßig schwer, bei der zweiten und dritten Übungsrunde wird es schwerer. Kann man bei einem Beispiel nicht genug, muss man so lange Beispiele vorrechnen, bis sich ein Beispiel findet, das man kann oder die Übungsstunde zu Ende ist ;).

Prüfung[Bearbeiten]

Zwei schriftliche Prüfungen in einem Abstand von 2 Wochen (die erste gleich nach der letzten Übungseinheit), wobei man nur zu einer antreten muss. Hat man bei beiden keine Zeit oder ist negativ, kann man eine mündliche Prüfung bei Dr. Saturni ablegen. Der Prüfungsmodus ist eher den leichteren Übungsbeispielen nachempfunden: es kommen keinerlei Beweise, lediglich Anwendung und Vergleich diverser Algorithmen. Es sind jedoch keine Unterlagen erlaubt und die Zeit ist auch recht knapp.

Zeitaufwand[Bearbeiten]

Für jeden Übungstermin einen Tag bis einen Nachmittag, für die Prüfung sich alles noch einmal einen Tag lang anschauen. Wichtig sind vor allem shortest path (die verschiedenen Algorithmen) und network flows (mit maximum cost flows und min cost flows).