Seminar Algorithms for Large Graphs
Marc Bux
Graphen sind elementare Datenstrukturen in der Informatik und haben eine große Bedeutung in vielen Bereichen. Während viele Fragestellungen für kleine Graphen, Bäume oder DAGs sehr schnell gelöst werden können, sind sehr große Graphen, die nicht in den Hauptspeicher passen, auch für relativ einfache Probleme oftmals noch eine Herausforderung. Beispiele für große Graphen sind soziale Netzwerke (Facebook, Twitter), Zitationsgraphen oder biologische Netzwerke (Gen / Protein Interaktionsnetzwerke). Das Seminar bietet eine Einführung in klassische Graph-Algorithmen (Erreichbarkeit, Subgraphmatching, kürzeste Wege, etc.) mit Fokus auf großen Graphen. Die Studenten stellen in Vortrag und Seminararbeit spezielle Algorithmen und Optimierungen vor.
Das Seminar findet im wesentlichen als Blockseminar am Ende des Semesters statt. Vorher sind aber Einführungstermine und individuelle Themenbesprechungen zu besuchen.Voraussetzungen
- Gute Kenntnisse in Algorithmen und Datenstrukturen (z.B. gleichnamige Vorlesung)
- Kenntnisse in Datenbanken und Indexstrukturen (z.B. Einführung in Datenbanken)
Schein und Anrechenbarkeit
Das Seminar ist anrechenbar für
- Master of Science (Informatik)
- Diplom (Informatik)
- Master of Education (Informatik)
Voraussetzung für den Schein ist:
- das Halten eines fünfminütigen Flash-Vortrags in der Mitte des Semesters,
- das Halten eines dreißigminütigen wissenschaftlichen Vortrags am Ende des Semesters,
- das Erstellen einer zehn- bis fünfzehnseitigen schriftlichen Ausarbeitung (Seminararbeit).
Anmeldung
Die Teilnehmerzahl ist begrenzt, die Anmeldung erfolgt über Goya.
Termine und Ablauf
Am 19.10.2015 findet von 15-17 Uhr die Einführungsveranstaltung statt, die für alle Teilnehmenden verpflichtend ist. Dort werden die Themen erläutert und vergeben.
Das Seminar wird als Blockseminar am Ende des Semesters abgehalten. Jede(r) Studierende muss einen ca. 30-minütigen Vortrag über das zugewiesene Thema halten. Vorher finden mindestens zwei Treffen mit dem Betreuer statt, einmal zur Vorbesprechung des Themas und einmal zur Besprechung der Folien. Außerdem wird es in der Mitte des Semesters einen Termin geben, an dem alle Studierenden in einer 5-minütigen Flash-Präsentation ihr Thema vorstellen, um Querverbindungen zu erkennen und die rechtzeitige Beschäftigung mit dem Thema sicherzustellen. Schließlich muss zu jedem Thema eine 10-15-seitige Seminararbeit verfasst werden.
Zusätzlich zu der speziellen Literatur, über die die Vorträge gehalten werden, gibt es für alle Teilnehmer verpflichtende Einführungslektüre.
Alle Pflichttermine in der Übersicht:
- 19.10.15, 15-17 Uhr, RUD 26, 1'308: Einführung und Themenvergabe
- Bis 20.11.2015: Erstes Treffen mit dem Betreuer zur Themenbesprechung und -eingrenzung (Termin bis 2.11.2015 vereinbaren)
- Bis 30.11.2015: Zusenden eines ersten Entwurfs der Folien für die Flash-Präsentation
- 7.12.2015, 15-17 Uhr, RUD 26, 0'313: Flash-Präsentationen
- Bis 15.1.2016: Zweites Treffen mit dem Betreuer zur Besprechung der Folien (Termin bis 21.12.2015 vereinbaren)
- 29.1. und 5.2., 10-15 Uhr, RUD 25, Humboldt-Kabinett: Blockseminar
- Bis 31.3.2016: Abgabe Seminararbeit
Vorlagen
- Schriftliche Ausarbeitung, Latex
- Vortrag, Powerpoint
- Vortrag, Keynote
- Text für die Selbstständigkeitserklärung
- Checkliste für Vortrag und Seminararbeit
Themen
| Topic | Paper | Vortragende(r) | Betreuer(in) |
|---|---|---|---|
| Einführende Literatur für alle Teilnehmer |
|
||
| Einführung | Folien der Einführung | Bux | |
| Regular Path Queries |
|
Vogt (Folien des Vortrags) | Marc Bux |
| Betweenness-Centrality |
|
Schaeffer (Folien des Vortrags) | Marc Bux |
| Graph Alignment |
|
Döpmann (Folien des Vortrags) | Marc Bux |
| Reachability |
|
Schekahn (Folien des Vortrags) | Marc Bux |
| Max-Flow with Ford/Fulkerson |
|
Dettmer (Folien des Vortrags) | Marc Bux |
| Approximate Subgraph Search |
|
Völker | Marc Bux |
| Algorithms for Pregel |
|
Akili & Hüneburg | Marc Bux |
| Graph Partitioning |
|
Borchert & Skrzypczak | Marc Bux |