TU Wien:Algorithms in Graph Theory VU (Chen)

Daten

Zuordnungen

Masterstudium Logic and Computation	Modul Algorithmics and Complexity (Gebundenes Wahlfach)
Masterstudium Software Engineering & Internet Computing	Modul Algorithmik (Gebundenes Wahlfach)

Inhalt

Es sind insgesamt 4 Kapitel, und jede vortragende Person kümmert sich um eines der Themengebiete:

Nöllenburg: Planarity - einiges davon wird auch in anderen Kursen wie etwa Algorithmic Geometry erwähnt. Hier ist die vertiefung deutlicher, zB lernt man auch etwas über outerplanar graphs, oder den Beweis, warum der Satz von Wagner/Kuratowski (K₅ / K_3,3 (Topoligical) Minor als Indikator für non-planarity) gilt.

Chen: Matching - stable Matching kennt man bereits aus Algorithmen und Datenstrukturen. Hier lernt man auch weitere Formen von Matchings, wie etwa Popular Matchings, und wie sie mit Stable Matchings zusammenhängen. Auch Anwendungsfälle für Matchings, die von Haus aus keine Graphenprobleme sind, werden erläutert (zB Job Scheduling)

Szeider: Width Measures - Treewidth ist der bekannteste dieser Eigenschaften und wird auch in Algorithmics angeschnitten. Zustzlich werden auch Pathwidth, Clique-Width und Twin-Width genauer erläutert. Es wird auch auf die Hierarchie eingegangen (zB: bounded Pathwidth -> bounded Treewidth)

Sorge: Sparsity - Eigenschaften, wie die Dichte eines Graphen gemessen werden kann, zB max degree, avg degree und degeneracy. Anschließend werden Algorithmen gezeigt, welche für lichte Graphen besser performen/zugeshcnitten sind.

Ablauf

Jedes Kapitel hat ein eigenes Übungsblatt á 20 Punkte, das in 3er-Teams gelöst werden soll. Zusätzlich kann ein Studi sich in einer Übungseinheit bis zu 5 Extrapunkte (individuell, keine Teamleistung) holen, indem die Lösung eines Beispiels präsentiert wird (Voranmeldung dafür auf TUWEL). DIe Auswahl, wer präsentiert, ist nicht zwingend First come First Serve - so hat bereits eine Person, die sich später angemeldet hat, den Vorzug erhalten, weil sie noch nicht präsentiert hat, während die andere bereits in einer Einheit zuvor präsentiert hat. Man darf maximal zweimal präsentieren. Für eine positive Note waren insgesamt 40 (?) Punkte notwendig, für die Bestnote (2er - gut) waren 67 ausreichend. Am Ende gibt es eine freiwillige mündliche Prüfung, bei der man nur antreten darf, wenn man genug Punkte für einen 4er (genügend) aufgebracht hat. Eine gut absolvierte Prüfung verbessert den Notengrad auf die nächstbessere Note, eine mittelmäßige verändert die Note nicht, und eine schlecht absolvierte verschlechtert die Geamtnote auf die nächstschlechtere.

Benötigte/Empfehlenswerte Vorkenntnisse

Wissen zu Algorithmen und Datenstrukturen bzw Basics, was Graphentheorie angeht.

Vortrag

Es gibt 12 Vorträge (3 für jedes Kapitel) mit 4 verschiedenen Vortragenden (siehe oben). Dadurch sind die Vorträge bzw die Stile sehr unterschiedlich. Alle kennen sich in ihren Gebieten gut aus, aber es kann manchmal schwierig sein, bei den Vorträgen immer gut mitzukommen.

Übungen

An sich recht entspannt, man kann sich durch eine Präsentation nicht verschlechtern. Wird ein Beispiel von Studis nicht präsentiert, so wird eine Musterlösung vom Vortragenden erklärt (idr ist das die selbe Person, welche die Vorträge zu dem Kapitel hielt).

Manchmal schleichen sich Fehler in der Angabe ein - traut euch, das im Forum anzusprechen. Das Team ist auch sehr kulant und verschiebt Deadlines nach hinten für solche Fälle.

Prüfung, Benotung

One can voluntarily take an oral exam about the lecture content which can influence the grade by +1,+0 or -1. In my case, two of the lecturers asked questions about the general lecture content 10 minutes each The questions were not too specific, but one should certainly know and understand the covered content as well as the proofs. The atmosphere is relatively relaxed and general understand is more important than knowing every little specific detail.

Dauer der Zeugnisausstellung

noch offen

Zeitaufwand

noch offen

Unterlagen

noch offen

• Materialien

Tipps

Wenn man etwas nicht verstanden hat, dann am besten beim oder nach dem Vortrag der vortragende Person Fragen stellen. Auch das TUWEL-Forum kann genutzt werden.

Highlights / Lob

Sehr emphehlenswert für alle, die Graphen interessieren.

Verbesserungsvorschläge / Kritik

noch offen

Materialien

Diese Seite hat noch keine Anhänge, du kannst aber neue hinzufügen.