Proseminar Algorithmen für Graphen

Proseminar im Wintersemester 2008/09. Dr. Henning Bordihn.

Termine

Die Veranstaltung umfasst 2 SWS (3 LP). Die Themenvergabe und die zugehörigen Termine werden in der ersten Lehrveranstaltung abgesprochen:

• Freitag, 24.10., 11-12.30 Uhr, 03.04.2.01.

Prüfungen

Die Prüfungsleistung wird durch zwei Teilprüfungen erbracht.

• 1. Teilprüfung: Jeder Teilnehmende erarbeitet anhand eines oder mehrerer Buchkapitel oder Zeitschriftenartikel (in der Regel Kapitel von Lehrbüchern) einen Vortrag zu einem vorgegebenen Thema. Neben inhaltlicher Korrektheit muss der Vortrag vor allem gut verständlich und übersichtlich strukturiert sein.
  Die Themen und Vortragstermine werden in der ersten Lehrveranstaltung am 24. Oktober vergeben.


• 2. Teilprüfung: In der letzten Lehrveranstaltung (13. Februar 2009) wird jedem Teilnehmenden ein Thema eines anderen Vortags dieses Proseminars zugelost. Es ist eine etwa einseitige Zusammenfasung des Inhaltes dieses Vortrags in englischer Sprache (ganze Sätze) zu schreiben und bis zum 27. Februar 2009 als pdf-Datei an Dr. Henning Bordihn zu senden.

In die Prüfungsnote geht die Note der ersten Teilprüfung mit einem Gewicht von 75 Prozent, die Note der zweiten Teilprüfung mit einem Gewicht von 25 Prozent ein. Beide Teilleisungen müssen aber mindestens mit 4,0 bestanden werden.

Zuordnung

Praktische Informatik, keine eigenständige Leistung, ab 3. Semester.

Voraussetzung

Grundlagen der Programmierung.

Inhalte

Ziel dieses Proseminars ist es, ergänzend zur Lehrveranstaltung "Grundlagen der Programmierung" wichtige graphentheoretische Konzepte und Algorithmen vorzustellen.
Zum Beispiel:

• Wege, Kreise, Zusammenhang

• Färbungen

• Transitive Hülle

• Minimal spannende Bäume

• Tiefensuche und Breitensuche

• Kürzeste Wege

• Flüsse

Literatur

S. O. Krumke, H. Noltemeier: Graphentheoretische Konzepte und Algorithmen. Teubner-Verlag, 2005.