next up previous
Nächste Seite: Literatur

Algorithmen auf Graphen


Seminar im Grundstudium NWI - SoSe 2004




Veranstalter: Jens Reeder (jreeder(at)techfak...)  M3-114
Belegnummer: 392017
Zeit: Donnerstag 16 ct - 18
Ort: C01 - 136
Scheinkriterien: 30-45 minütiger Vortrag und schriftliche Ausarbeitung
  (ungefähr 6 Seiten)
Voraussetzung: Algorithmen und Datenstrukturen I


Graphen und Algorithmen auf Graphen sind in vielen Teildisziplinen der Informatik von Bedeutung. Viele Probleme kann man als Graphenprobleme formulieren, wie z.B. Fragestellungen im Bereich der Stoffwechselweganalyse, Routenplanung, Programmcodeanalyse usw.. Auch das Internet ist ein riesiger Graph und wir können es nur aufgrund effizienter Graphalgorithmen nutzen.

In diesem Seminar sollen einerseits grundlegende Graphalgorithmen kennen-gelernt und andererseits das Vortragen in wissenschaftlichem Rahmen geübt werden. Im Anschluss an jeden Vortrag findet daher auch eine kurze Diskussion über den Vortragstil statt.

Themenliste

  1. Graphrepräsentationen, Breadth-first und Depth-first Search (Kap. 23: S. 465-484 in [CLR90]); Random Graph Generators (S. 46-54 in [Sed04])
  2. Simple, Eulerian and Hamilton Paths (Kap. 17.7: S. 57-68 in [Sed04])
  3. Topological sort, strongly connected components (Kap. 23: S. 485-493 in [CLR90])
  4. Minimum Spanning Trees (Kap. 24 in [CLR90] und Kap. 20 in [Sed04])
  5. Single Source Shortest Path (Kap. 25 in [CLR90])
  6. All-Pairs Shortest Paths (Kap. 26: 550-563 in [CLR90])
  7. Flow Networks, Maximum Flow, Ford-Fulkerson Algorithm (Kap. 27: S. 579-600 in [CLR90]
  8. Heuristiken zum Traveling Salesman Problem (S.969-973 in [CLR90] and [RSL77])
  9. PageRank: Der Algorithmus hinter Google [LSMW98]


Vortragsplan

Datum
Vortragender
Thema
29.4
-
Vorbesprechung
6.5
J.R.
Grundlegende Begriffe und Algorithmen (1)
13.5
Sascha McSporran
Simple, Eulerian and Hamilton Paths (2)
27.5
-
-
3.6
Christoph Hermes
Single Source Shortest Path (5)
24.6
Benjamin Gess All-Pairs Shortest Paths (6)
1.7
Martin Krzykawski
Flow Networks  (7)
8.7
-
Google (9)




next up previous
Nächste Seite: Literatur
Jens Reeder 2004-04-29