Die TeilnehmerInnen lernen das selbständige Einarbeiten in ein aktuelles Forschungsthema aus den Bereichen Graphenalgorithmik bzw. algorithmischer Geometrie. Ausgehend von ausgewählten aktuellen Originalarbeiten erarbeiten die TeilnehmerInnen sich die relevante Literatur. Durch den Seminarvortrag und die schriftliche Seminararbeit erlernen die TeilnehmerInnen wichtige Grundfertigkeiten wie das Präsentieren algorithmischer Themen und das wissenschaftliche Schreiben. Durch die Fokussierung des Seminars auf offene Forschungsfragen und wissenschaftliche Diskussionen wird die algorithmische Problemlösungskompetenz geschult. Damit werden insbesondere Fähigkeiten erworben und erweitert, die auch zum Verfassen einer Masterarbeit in der Algorithmik erforderlich sind.

Die Seminarthemen stammen aus dem Bereich Graphenzeichnen und algorithmische Geometrie und behandeln aktuelle Forschungsfragen.

Aufbau der Lehrveranstaltung

Das Seminar behandelt ein aktuelles Teilgebiet aus dem Bereich Graphenzeichnen/Graphenalgorithmik. Nach einer Einführung in das Thema wählen die Studierenden ihr Seminarthema aus einer Liste von Vorschlägen aus. Nach zwei Wochen stellen sie ihr Thema zunächst in einem etwa 5-minütigen Kurzvortrag vor. Im Laufe des Novembers folgen dann die regulären Vorträge mit Diskussion. Dabei soll neben der Vorstellung der Forschungsergebnisse vor allem auch auf offen gebliebene Fragen geachtet werden. Im Dezember werden wir ausgewählte offene Fragen in gemeinsamen Forschungstreffen diskutieren und Lösungsansätze entwickeln. Im vergangenen Jahr ist aus diesen Treffen eine gemeinsame Veröffentlichung entstanden.

Die schriftliche Seminararbeit ist vor der Weihnachtspause abzugeben, wird dann gegenseitig begutachtet und ist in der finalen Version im Februar einzureichen.

ECTS-Aufwandsabschätzung

  5h Einleitung und Themenwahl
15h Präsentationen und Seminartermine

25h Einarbeitung in Seminarthema
10h Präsentationsvorbereitung
20h Seminararbeit
----
75h

Anwesenheitspflicht

Mündliche Präsentation, schriftliche Seminararbeit, Peer Review, Forschungsprotokoll.

• Mixed linear layouts of graphs (taken)
• Queue number of posets of bounded height or width
• Queue layouts of planar 3-trees
• Faster algorithms for some optimization problems on collinear points
• On contact graphs of paths on a grid
• Greedy rectilinear drawings (taken)
• How to fit a tree in a box (taken)
• The painter’s problem: Covering a grid with colored connected polygons (taken)

Entwurf und Analyse von Algorithmen, insbesondere Graphenalgorithmen

geometrische Grundkenntnisse