Proseminar "Graphalgorithmen"
[go to overview]Summer Term 2015
Überblick
In vielen Bereichen der Informatik werden Graphen als Datenstruktur verwendet und dienen auch als Abstraktion für viele verschiedene Probleme. Dieses Proseminar vertieft und erweitert dazu die in "Algorithmen und Datenstrukturen" vermittelten Inhalte zu Graphen. Neben formalen Grundlagen der Graphentheorie werden in diesem Proseminar dabei Probleme auf Graphen wie Färbbarkeit, Clustering, und Routing, als auch praktische Aspekte wie Graphdatenbanken diskutiert.
Seminarthemen
- Grundlagen der Graphentheorie I
Typen von Graphen, Bipartite Graphen, Vollständige Graphen, Bäume, Wege, Kreise, Traversierung - Grundlagen der Graphentheorie II
Adjazenzmatrizen, Graphmetriken, Durchmesser von Graphen, Planare Graphen, Satz von Euler - Grundlagen der Graphentheorie III
Zusammenhang, Starker Zusammenhang, Isomorphismus, Algorithmus von Kosaraju - Das Vertex-Cover Problem
Satz von König, Komplexität, Algorithmen - Matching
Matching, Perfekte Matchings, Satz von Tutte, Algorithmus von Edmonds, Algorithmus von Hopcroft-Karp - Spannbäume und das Steinerbaumproblem
Minimale Spannbäume, Algorithmus von Prim, Algorithmus von Kruskal, Steinerbaumproblem, Algorithmen, Komplexität - Färbung von Graphen
Chromatische Zahl, Knotenfärbung planarer Graphen, Komplexität, Algorithmen - Hamilton'sche Graphen und das Traveling Salesman Problem
Hamilton'schheit, Hypohamilton'schheit, Trassable Graphen, Satz von Grinberg, Traveling-Salesman Problem, Komplexität, Algorithmen - Visualisierung von Graphen
Crossing numbers, Graphlayoutstrategien, Force-directed Layout, Coffman-Graham Algorithmus - Graph Clustering
Community detection, Modularität von Graphen, Algorithmus von Girvan-Newman - Max-Cut, Min-Cut, und Maximum Flow
Algorithmus von Ford-Fulkerson, Algorithmus von Goldberg-Tarjan, Max-flow Min-cut Theorem, Max-cut, Approximationsalgorithmen von Max-cut - Kürzeste Wege
Djikstra, Bellmann-Ford, A*, IDA*, Algorithmus von Johnson - Graphprobleme in sozialen Netzwerken
Link Prediction, Barabasi-Albert Modell, Zentralität, PageRank Algorithmus - Graphdatenbanken
Cypher, Gremlin, Neo4J, RDF, Anwendungen, Vergleich relationale Datenbanken
Literaturempfehlungen
- Sven Oliver Krumke and Hartmut Noltemeier. Graphentheoretische Konzepte und Algorithmen. Springer, 2012.
- Peter Tittmann. Graphentheorie: Eine anwendungsorientierte Einführung. Carl Hanser Verlag, 2011
Termine
Vorbesprechung: 14.04.2015 14:15 (Raum F.522)
Blockseminar: 04.08. 09:15-17:45, 05.08. 09:15-17:45 (Raum B.017)
Teilnahme
Um an dem Proseminar teilzunehmen ist eine Teilnahme an der Vorbesprechung am 14.04.2015, 14:15 (Raum F.522) erforderlich. Wenn Sie Interesse haben an dem Proseminar teilzunehmen, kündigen Sie dies bitte vorab in einer informellen E-Mail an Matthias Thimm an.
Von den Teilnehmern wird eine Präsentation (ca. 30 Minuten) über eines der oben genannten Themen erwartet. Im Anschluss an das Proseminar ist eine Ausarbeitung über das Seminarthema (ca. 12 Seiten) abzugeben.
Bitte beachten Sie bei der Erstellung der Präsentation und der Ausarbeitung folgende allgemeine Richtlinien (nur in Englisch verfügbar): pdf
Proseminar - Graphenalgorithmen
Veranstaltungsnummer: 04448
Dozent(in) | Dr. Matthias Thimm |
Termin(e) |
|