TU Wien:Graph Drawing Algorithms VU (Nöllenburg)

Daten

Zuordnungen

Masterstudium Data Science	Modul BDHPC/EX - Big Data and High Performance Computing - Extension (Gebundenes Wahlfach)
Masterstudium Business Informatics	Modul ISE/EXT - Information Systems Engineering Extension (Gebundenes Wahlfach)
Masterstudium Logic and Computation	Modul Algorithmics and Complexity (Gebundenes Wahlfach)
Masterstudium Visual Computing	Modul Advanced Visualization (Gebundenes Wahlfach)
Masterstudium Software Engineering & Internet Computing	Modul Algorithmik (Gebundenes Wahlfach)

Inhalt

Grob zusammengefasst geht es in der LVA darum, Techniken und Algorithmen zu beleuchten, die eine für Menschen gut lesbare Repräsentation verschiedener Graphen zum Ziel haben. Zum Beispiel die Berechnung einer planaren Zeichnung eines planaren Graphen, optimierung der Winkel der Kanten bzw diskrete auswahl möglicher WInkel (zB bei U-Bahn-Plänen), Minimirung der Kreuzungen bei nicht-planaren graphen, hierarchische Darstellungen (Flowcharts), Zeichnung auf Ebenen (zB Sugiyama Framework), Kreis-Graphen, Zeichnung auf diskreten Koordinaten (zusätzlich: Minimierung der benötigten Fläche)...

Das Fach ist sowohl für Logikinteressierte, als auch für Leute die sich mit Computer Graphics beschäftigen interessant.

Ablauf

Wöchentliche Vorlesung, manchmal auch zweimal wöchentlich. Es gibt eine große Übung die über das ganze Semester geht, also keine Aufgabenblätter oder Zwischentests. Man kann wählen, ob man eine Gruppenarbeit (Programmierung oder Visualisierung) bearbeitet, oder alleine arbeitet (Paper Präsentation). Am Ende gibt es eine mündliche Prüfung.

Benötigte/Empfehlenswerte Vorkenntnisse

Mathematik VOs aus dem Bachelor

Algorithmen und Datenstrukturen

Oder allgemein: Basiswissen zur Graphentheorie, vertiefendes Wissen zb via andere Masterfächer ist bei manchen Themen vorteilhaft.

Vortrag

Der Professor macht viele Notizen auf den Folien die dann später über TUWEL verfügbar gemacht werden. Manchmal ist die Vorlesung etwas interaktiv (z.B. kleine Diskussionen oder Punkte nennen die einem einfallen). Die Beweise waren manchmal etwas lang.

Übungen

Es gibt eine große Übung die über das ganze Semester geht, wobei man drei Auswahlmöglichkeiten hat. Zwei davon sind Gruppenarbeiten: entweder eine Programmieraufgabe, bei der man die ANzahl de Kreuzungen bei arbiträren Input-Graphen minimieren muss (Optimization), oder Kreativ-Aufgabe, bei welcher für einen Inputgraphen mit klar definierten Daten ein Poster entworfen werden muss, der die Informationen visuell ansprechend darstellt, wobei auch Informationen weggelassen oder hinzugefügt werden dürfen (Visualization). Entscheidet man sich für die Einzelaufgabe (Seed Paper), muss man ein vorgegebenes Thema wählen (zB Crossing-Bundling, Vertex Splitting...) und erhält danach ein Research-Paper zugewiesen. Man muss die Ergebisse des Papers präsentieren (eventuell under Berücksichtigung von Follow-ups, aufbauende Forschung oder ähnlichen Projekte). Die Dedlines sind jeweils der Tag der Präsentation, die immer in den letzten 2 Wochen des Semesters stattfindet (Angefangen mit Seed Paper Studis, gefolgt von Visualization Gruppen und abschließend die Optimization Gruppen).

Prüfung, Benotung

Die Übung trägt 40%, die mündliche Prüfung 60% zur Gesamtnote bei.

Die Benotung ist absolut fair. Die Prüfung bestand mehr aus einem 20-Minütigen Gespräch bei dem man selbst ziemlich viel in eine Richtung lenken konnte. Gefragt wurde dabei alles Mögliche von den Vorlesungsfolien (auch aus der ersten und letzten Einheit!), aber es wurde nicht sehr in die Tiefe gegangen. Der Professor legte dabei aber auch Wert auf Laufzeiten und obere/untere Schranken (z.B. Area Bounds), die sollte man sich also auch einprägen. Ansonsten wurde zwar nach Beweisen gefragt, aber hier hat es absolut gereicht eine kleine Skizze zu beschreiben. Es ging definitiv eher um Verständnis als ums auswendig Lernen. Meine Fragen:

• Was ist ein Graph? Welche Drawing Conventions gibt es, zwei Beispiele nennen.
• Hier habe ich dann das Sugiyama Framework genannt und sollte es dann in mehr Detail beschreiben:
  • Die einzelnen Schritte aufzählen und jeweils die in der VO besprochenen Heuristiken und Methoden beschreiben
  • Laufzeiten der Heuristiken
• SP-Graphs: Rekursive Definition, Drawing Area Bounds, Beweisskizze (planarität und azyklisch)
• Generelle Fragen zu planaren Graphen (Eigenschaften, Algorithmen nennen die wir in der VO gesehen haben)

Insgesamt war die Prüfung ziemlich genau 20 Minuten lang und absolut ohne übermäßigem Aufwand schaffbar.

Hatte Ende September Prüfung und meine Erfahrung war da sehr ählich. Die Prüfung war mega entspannt und fair und nachdem sie ja nur 20 Minuten dauerte, wurde auch nicht so extrem ins Detail gegangen. Ich hab folgende Fragen bekommen:

• Graph Drawing Problem beschreiben, was sind Drawing Conventions, Aesthetic Criteria und Constraints, nenne jeweils Beispiele
• Ich habe uniform edge lengths erwähnt und wurde gefragt ob ich eine Methode kenne bei der das vorkam, ich habe Metro Maps erwähnt
  • Sollte dann das Metro Maps Problem genauer beschreiben und sagen welche Kriterien es dabei gibt
  • habe auch kurz die einzelnen Schematisations zusammengefasst
  • wurde noch genauer gefragt was octolinearität ist
• Von octolinearität kamen wir zu orthogonal graph drawing
  • STM framework beschreiben
  • Flow network für bend minimization genauer beschreiben mit skizze und bounds, euler formel wollten sie beim Beweis der Gültigkeit des Netzwerks auch hörn
  • Kurz erklären wie das mit der area minimization funktionieren würde und sagen, was die complexity davon ist
  • beweis für np completeness von area minimization ganz grob beschreiben

Dauer der Zeugnisausstellung

Zwei Wochen

Zeitaufwand

Variiert wahrscheinlich stark je nach Semester. Man kann sich schon ganz schön in die Übung vertiefen, aber insgesamt war der Zeitaufwand OK.

Unterlagen

Annotierte Folien über TUWEL

Teilweise weiterführende Infos zu ausgewählten Themen als PDF (auch über TUWEL)

Manche der empfohlenen Bücher sind online abrufbar; sonst in der Bibliothek

Online Quizzes zur Selbstüberprüfung in TUWEL

Tipps

Es gibt gute Aufzeichnungen zu den Vorlesungen; Anwesenheit ist also nicht unbedingt notwendig

Highlights / Lob

noch offen

Verbesserungsvorschläge / Kritik

• Evtl. könnte man bei den Folien eine condensed Version einfügen bei denen die Zwischenfolien rausgenommen wurden. Das würde beim Lernen helfen.

Materialien

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