Veranstaltungen

Vorlesung im Sommersemester 2021: Visualisierung von Graphen

Die Vorlesung "Visualisierung von Graphen" des Sommersemesters 2021, wird folgende Inhalte anbieten:

Das Graphenzeichnen beschäftigt sich mit der geometrischen Repräsentation von Graphen und Netzwerken und wird durch jene Anwendungen motiviert, in denen eine Visualisierung struktureller Informationen als Graph unentbehrlich ist. Das Gebiet erstreckt sich von rein theoretischen Aspekten bis hin zu Implementationen denen man im Alltag begegnet.
Wir beschäftigen uns mit den wichtigsten Algorithmen zum Zeichnen von Graphen. Wir werden Maße für die Qualität einer Graphzeichnung kennenlernen und Algorithmen betrachten, die diese Maße optimieren.

Lernergebnisse (learning outcomes) / Kompetenzen:
Die TeilnehmerInnen bekommen einen Überblick über das Thema Graphvisualisierung (das sich sehr gut für Abschlussarbeiten eignet) und lernen typische Werkzeuge dafür kennen. Sie vertiefen ihre Kenntnisse über das Modellieren und Lösen von Problemen mithilfe von Graphen und Graphalgorithmen.

Literatur:

  • Graph Drawing: Algorithms for the Visualization of Graphs.
    Giuseppe Di Battista, Peter Eades, Roberto Tamassia und Ioannis G. Tollis. Prentice Hall, 1999.
  • Drawing Graphs: Methods and Models.
    Michael Kaufmann und Dorothea Wagner (Hrsg.), Lecture Notes in Computer Science, Band 2025. Springer-Verlag 2001.
  • Planar Graph Drawing.
    Takao Nishizeki und Md Saidur Rahman, Lecture Notes Series on Computing, Band 12. World Scientific Publishing, 2004.

 

Vorlesung im Wintersemester 2021/22: Fortgeschrittene Algorithmen

Mastervorlesung (4+2) 

Dieser Kurs vermittelt einen Überblick über verschiedene Themenbereiche der Algorithmik anhand einer Auswahl von Materialien zu exakten, geometrischen, randomisierten und Approximationsalgorithmen sowie zu fortgeschrittenen Datenstrukturen. Als solcher dient dieser Kurs als eine Basis für die dazugehörigen Mastervorlesungen. Der Kurs behandelt Verbesserungen von klassischen Algorithmen sowie Ansätze, um NP-schwere Probleme anzugehen. Diese Ansätze reichen vom Verständnis "guter" Algorithmen, die solche Probleme exakt lösen, über effiziente Algorithmen, die solche Probleme approximieren, bis hin zu randomisierten Ansätzen, welche im Erwartungswert gut funktionieren. Im Zuge dessen werden wir einige interessante Datenstrukturen kennen lernen, welche hierfür ausgenutzt werden können.

Lernergebnisse (learning outcomes) / Kompetenzen:
Am Ende dieses Kurses sollten TeilnehmerInnen einen groben Überblick über fortgeschrittene Themen der Algorithmik und Datenstrukturen haben. Sie sollten in der Lage sein, Algorithmen von jedem Typ zu analysieren und zu entwerfen sowie den angemessenen Gebrauch der Datenstrukturen verstehen.

Literatur:

  • Introduction to Algorithms (3rd Edition).
    Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford.  MIT Press and McGraw-Hill, 2009 [1990].
  • Parameterized Algorithms.
    Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk and Saket Saurabh. Springer, 2015.
  • Exact Exponential Algorithms.
    Fedor V. Fomin and Dieter Kratsch. Springer, 2010.
  • Computational Geometry: Algorithms and Applications (3rd edition).
    Mark de Berg, Otfried Cheong, Marc van Kreveld, Mark Overmars. Springer, 2008.
  • Algorithmische Geometrie (2. Auflage).
    Rolf Klein. Springer, 2005.
  • The Design of Approximation Algorithms
    David P. Williamson, David B. Shmoys. Cambridge University Press, 2011.
  • Approximation Algorithms
    Vijay V. Vazirani. Springer, 2003.