Algorithmen auf Graphen

VAK 03-05-H-602.01

Graphen werden vielfach zur Repräsentation komplexer Informationsstrukturen und komplizierter Sachverhalte verwendet. Aber wie kommt man an die Informationen günstig heran? Wie kann man den Sachverhalten auf den Grund gehen? In der Lehrveranstaltung werden einige Antworten gegeben. Insbesondere werden Algorithmen auf Graphen konzipiert und analysiert. Zu den Themen, die behandelt werden, gehören das Königsberger Brückenproblem, kürzeste Wege, minimal aufspannende Bäume, maximale Flüsse, das Vier-Farben-Problem, NP-Probleme, Reduktion und NP-Vollständigkeit sowie einige ausgewählte Heuristiken. Die diskutierten Anwendungen fallen vor allem in den Bereich der Logistik.
Es gibt ein Skript zur Veranstaltung.

[Modulbereich Theorie]

Kategorie: A (ECTS: 6), K 4 SWS

Online-Anmeldung: Anmeldung für die Veranstaltung!

Zeit & Ort
- Di 8:30 - 10:00 Uhr im MZH Senatssaal (1400)
- Do 13 - 15 Uhr im MZH Senatssaal (1400)
erster Termin: 26. Oktober 13:15 Uhr

Skript zur Veranstaltung
- Vom Wintersemester 2003/04 .ps, .pdf
- Ergänzung zu Kapitel 8, Wintersemester 2005/06 .ps, .pdf

Folien zur Vorlesung
- Graphen in der Informatik .pdf
- Eulersche Graphen .pdf
- Vier-Farben-Problem .pdf
- Kürzeste Wege .pdf; Folien zum Algorithmus von Dijkstra .pdf
- Minimal aufspannende Bäume .pdf

Applets
- planare Graphen, Dijkstras kürzeste Wege Algorithmus

Übungsblätter
- Übungsblatt 1 .pdf
- Zusatzblatt zum 1. Übungsblatt .pdf
- Übungsblatt 2 .pdf
- Übungsblatt 3 .pdf
- Übungsblatt 4 .pdf


	Research Group Theoretical Computer Science
	Algorithmen auf Graphen VAK 03-05-H-602.01 Graphen werden vielfach zur Repräsentation komplexer Informationsstrukturen und komplizierter Sachverhalte verwendet. Aber wie kommt man an die Informationen günstig heran? Wie kann man den Sachverhalten auf den Grund gehen? In der Lehrveranstaltung werden einige Antworten gegeben. Insbesondere werden Algorithmen auf Graphen konzipiert und analysiert. Zu den Themen, die behandelt werden, gehören das Königsberger Brückenproblem, kürzeste Wege, minimal aufspannende Bäume, maximale Flüsse, das Vier-Farben-Problem, NP-Probleme, Reduktion und NP-Vollständigkeit sowie einige ausgewählte Heuristiken. Die diskutierten Anwendungen fallen vor allem in den Bereich der Logistik. Es gibt ein Skript zur Veranstaltung. [Modulbereich Theorie] Kategorie: A (ECTS: 6), K 4 SWS Online-Anmeldung: Anmeldung für die Veranstaltung! Zeit & Ort Di 8:30 - 10:00 Uhr im MZH Senatssaal (1400) Do 13 - 15 Uhr im MZH Senatssaal (1400) erster Termin: 26. Oktober 13:15 Uhr Skript zur Veranstaltung Vom Wintersemester 2003/04 .ps, .pdf Ergänzung zu Kapitel 8, Wintersemester 2005/06 .ps, .pdf Folien zur Vorlesung Graphen in der Informatik .pdf Eulersche Graphen .pdf Vier-Farben-Problem .pdf Kürzeste Wege .pdf; Folien zum Algorithmus von Dijkstra .pdf Minimal aufspannende Bäume .pdf Applets planare Graphen, Dijkstras kürzeste Wege Algorithmus Übungsblätter Übungsblatt 1 .pdf Zusatzblatt zum 1. Übungsblatt .pdf Übungsblatt 2 .pdf Übungsblatt 3 .pdf Übungsblatt 4 .pdf	Mail Address University of Bremen Dept. for Math. & Computer Science P.O. Box 330 440 28334 Bremen Germany Physical Address Linzer Strasse 9a OAS 3002 28359 Bremen Phone ++49(421)218 64450 Fax ++49 (421) 218 4322 Email (Secr.) Helga Reinermann helga@tzi.de
		© / 19.02.07