Uni-Logo

Proseminar: Graphalgorithmen - Organisation

Veranstalter: Prof. Dr. Bernhard Nebel und Dr. Stefan Wölfl

Bei organisatorischen Fragen wenden Sie sich bitte an Dr. Stefan Wölfl.

Beschreibung

Viele Enscheidungs- und Suchprobleme in der Informatik lassen sich als graphentheroetische Probleme auffassen. Im Rahmen des Proseminars sollen Algorithmen zur Lösung solcher graphtheoretische Probleme vorgestellt und implementiert werden.

Termine

Das Seminar findet als Blockseminar nach Ende der Vorlesungszeit statt.

Termin: Mo. 27. Feb., und Di. 28. Feb. 2012, 12:30 - 18:00 Uhr
Ort:   Geb 51, SR 00-034

Vorbesprechung: Di., 25. Oktober 2011, 12:00-13:30, Geb. 52, 00-016 (Folien)

Abgabe der Implementierung: 23. Januar 2012, 23:59 MEZ (beim jeweiligen Betreuer)

Abgabe des Factsheets: 6. Februar 2012, 23:59 MEZ (beim jeweiligen Betreuer)

Abgabe der Folien: 13. Februar 2012, 23:59 MEZ (beim jeweiligen Betreuer)

Bitte achten Sie darauf die Abgabetermine einzuhalten. Werden die Implementierung, die Factsheets, oder Folien später abgegeben, müssen wir aus Gründen der Gleichbehandlung für jeden Verspätungstag eine Notenstufe abziehen (bspw. von 2.3 auf 2.7).

Themenvergabe:

Die Themen werden in der Vorbesprechung von den jeweiligen Betreuern vorgestellt und auf der Themen-Seite aufgeführt. Wir versuchen die Vergabe der Themen zu optimieren. Studierende, die am Seminar teilnehmen wolllen, schicken dazu eine in der Präferenz absteigend sortierte Liste mit den Nummern ihrer Themenwünsche bis spätestens 4. November per E-Mail an Dr. Robert Mattmüller.

Anforderungen

Um ECTS Punkte zu erhalten, müssen die Seminarteilnehmer

  • die Algorithmen des jeweiligen Themas in einer gängigen Programmiersprache (C, C++, Python, Java, ...) in Absprache mit dem Betreuer implementieren und anhand einer geeigneten Fragestellung evaluieren,
  • ein Factsheet zum Thema erstellen (4-6 DIN A5 Seiten, verwenden Sie das LaTeX-Template): die Sammlung der Factsheets wird während des Blockseminars den Teilnehmern zur Verfügung gestellt,
  • einen Vortrag von jeweils 25 Minuten Dauer vorbereiten und während des Blockseminars präsentieren.

Die Anwesenheit während des gesamten Blockseminars ist verpflichtend. Ferner ist eine aktive Mitarbeit im Seminar natürlich erforderlich für Gelingen des Seminars.

Die Leistungen sind entweder auf deutsch oder auf englisch zu erbringen und werden benotet. Für die Beurteilung werden die Implementierung und Evaluation, die Erstellung des Factsheets, die Erstellung der Vortragsmaterialien, die Vorträge selbst sowie die Beteiligung am Seminar miteinbezogen.

Plagiate: Alle Zitate, wörtliche und sinngemäße, müssen als solche gekennzeichnet werden. Dies gilt auch für aus Quellen entnommene Abbildungen. In der Implementierung ist die Verwendung von Bibliotheken und Source-Code von Dritter Seite deutlich kenntlich zu machen. Die Nutzungsbedingungen der jeweiligen Software-Lizenzen sind dabei strikt zu beachten. Richtlinie sollte sein, dass die Implementierung entprechend dem Standard der GPLv3 auch veröffentlicht werden könnte (siehe hierzu z.B. B.M. Kuhn et al.: A Practical Guide to GPL Compliance).

Literatur

  • R. Diestel, Graphentheorie (4. Aufl.), Springer, Berlin, Heidelberg, 2010.
  • S.O. Krumke und H. Noltemeier, Graphentheoretische Konzepte und Algorithmen (2. Aufl.), Vieweg+Teubner, 2009.
  • V. Turau, Algorithmische Graphentheorie, Oldenburg Wissenschaftsverlag, 2009.
  • K. Mehlhorn und P. Sanders, Data Structures and Algorithms: The Basic Toolbox, Springer, 2008.
  • J.G. Siek, L.-Q. Lee und A Lumsdaine, The Boost Graph Library. User Guide and Reference Manual, Addison-Wesley Longman, Amsterdam, 2002.