TU Wien:Algorithmen auf Graphen VU (Saturni)
- Algorithmen auf Graphen VU (Chwatal) (TU Wien, veraltet, 3 Materialien)
- Algorithmen auf Graphen VU (Saturni) (TU Wien, veraltet, 3 Materialien)
Dr. Saturni hat die TU verlassen.
Daten[Bearbeiten | Quelltext bearbeiten]
| Vortragende | Projektass. Dr. Cristiano Saturni |
|---|---|
| ECTS | 3 |
| Sprache | English |
| Links | Homepage |
| Masterstudium Logic and Computation | |
| Masterstudium Software Engineering & Internet Computing | |
| Masterstudium Technische Informatik |
Inhalt[Bearbeiten | Quelltext 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 | Quelltext 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 | Quelltext 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 | Quelltext 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 | Quelltext 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 | Quelltext 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 | Quelltext 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).