| Titel | Graph-Algorithmen |
| Veranstalter | Prof. Dr. Petra Mutzel |
| Veranstaltungsart | Proseminar (INF-BSc-110, Element 2) |
| Veranstaltungsnummer | 040607 |
| SWS | 2 |
| Max. Teilnehmer | 16 |
Dieses Proseminar richtet sich an Interessentinnen und Interessenten der Algorithmik. Insbesondere sollten Sie sich sehr für die Inhalte zu DAP 2 interessiert haben. Der erfolgreiche Besuch des Moduls Effiziente Algorithmen ist von Vorteil. In dem Proseminar werden Datenstrukturen und Algorithmen für Graphen behandelt, die jeweils rigoros auf ihre Korrektheit, Qualität und Laufzeit analysiert werden.
Algorithmen auf Graphen werden beispielsweise in sozialen Netzwerken, für Ähnlichkeitsberechnungen, in Straßen- und Rechnernetzen und bei Zuordnungsproblemen verwendet. Im Rahmen des Proseminars möchten wir uns mit grundlegenden Algorithmen auf Graphen befassen, die nicht nur in den oben genannten Themen eine wichtige Rolle spielen.
| VortragsID | Vortragende | Thema | Quelle | Kapitel | Seiten | Betreuer/in |
|---|---|---|---|---|---|---|
| 1+2 | Dennis Hebbeler, Alexander Herlez | Graph Spectrum | [1] | 1.1-1.7 | 1-14 | Christine Dahn, Lutz Oettershagen |
| 3+4 | Maximilian Dettmer, Oskar Zeino-Mahmalat | Eigenvalues | [1] | 3.1-3.6 | 33-42 | Nils Kriege |
| 5 | Wei Huang | Application of Eigenvectors | [1] | 3.13 | 58-62 | Adalat Jabrayilov |
| 6 | Patrick Miß | Separation | [1] | 4.7-4.7.2 | 72-77 | Andre Droschinsky |
| 7+8 | Marc-Andre Maruda, Erkan Kement | Frequent itemsets / A-priori | [2] | 6-6.2 | 201-214 | Till Schäfer |
| 9+10 | Ramin Eqbal, Bruno Steffen | Advertising on the Web | [2] | 8 | 281-302 | Denis Kurz |
| 11 | Ingo Eigenseher | Clustering of Social-Network Graphs | [2] | 10.2 | 349-356 | Bernd Zey |
| 12+13 | Ahmed Alhaj Kheder, Maximilian Bald | Community Detection and Partitioning | [2] | 10.3-10.4 | 357-368 | Jonas Charfreitag |
| 14 | Cemre Yurdakul | Counting Triangles | [2] | 10.7 | 380-386 | Christopher Morris |
| 15+16 | Tolunay Kunduraci, Timo Nowodworski | Mining Data Streams | [2] | 4-4.5 | 131-149 | Petra Mutzel |
[1] A.E. Brouwer, W.H. Haemers: Spectra of Graphs — Monograph, Springer, 2011
[2] J. Leskovec, A. Rajaraman, J. Ullman: Mining of Massive Datasets, 2014
Diese Veranstaltung ist ein Proseminar für Studierende im Grundstudium. Sie umfasst 3SWS. Dies beinhaltet einen Präsentationskurs (1SWS), der extern (zentral veranstaltet) angeboten wird. Hierzu müssen Sie sich über das LSF anmelden. Dieser Kurs ist für BachelorstudentInnen verpfichtend.
Die Themenverteilung erfolgt während der Vorbesprechung zu Beginn des Sommersemesters 2019. Im weiteren Verlauf des Semesters haben die Teilnehmer/inne/n Zeit, die Ausarbeitung zu schreiben und den Vortrag vorzubereiten. In dieser Zeit wird es regelmäßigen Treffen geben und ggf. themenbezogene Einzelgespräch.
Voraussetzung für den Hauptvortrag ist die vorherige Abgabe einer schriftlichen Ausarbeitung zu dem fest vorgegebenen Termin (s. unten), welche 8-10 Seiten umfasst und mit LaTeX erstellt wird (Vorlage: [.zip-Archiv]). Mangelhafte Ausarbeitungen sowie 1:1 Übersetzungen bzw. Kopieren führen zum Nicht-Bestehen des Seminars. Die Abgabe erfolgt per E-Mail an Petra Mutzel sowie an Ihre/n Betreuer/in als PDF.
Es wird empfohlen, rechtzeitig vor der Abgabe der schriftlichen Ausarbeitung dem Betreuer ein kurzes Konzeptpapier vorzulegen, in dem der Inhalt und Aufbau der Ausarbeitung stichpunktartig erläutert wird. Denn eine Aufgabe der Teilnehmer/innen besteht auch darin, den zu präsentierenden Stoff aus der Literaturquelle sorgsam auszuwählen. Es geht nicht darum, den ganzen Inhalt zu präsentieren, sondern die interessanten Aspekte. Hierbei ist eine frühzeitige Rückmeldung oft hilfreich. Der Inhalt der Ausarbeitung stimmt im Allgemeinen mit dem Inhalt der späteren Präsentation überein.
Jede Ausarbeitung wird zunächst von zwei Teilnehmer/innen korrigiert. Die zu beachtenden Kriterien finden Sie am Ende dieser Website. Die Teilnehmer/innen senden die korrigierte Versionen zu einem festgelegten Zeitpunkt an den Betreuer und den Verfasser. Nach einer gemeinsamen Diskussion, haben die Teilnehmer/innen die Gelegenheit, ihre Ausarbeitung noch einmal zu überarbeiteten und endgültig abzugeben.
Mitte Juni halten alle Teilnehmer/innen einen 5-minütigen Vortrag zur Vorstellung ihres Themas sowie dem geplanten Inhalt. Dieser dient dazu, häufige Fehler bei den Abschlussvorträgen zu vermeiden. Die dabei genutzten Folien könne als Grundlage für den Abschlussvortrag dienen und erweitert werden. Um die vorbereiteten Abschlussvorträge zu perfektionieren, treffen sich die Teilnehmer/innen ggf. in kleineren Gruppen um sich gegenseitig zu unterstützen. Der Betreuer steht für Fragen zur Verfügung. Auch diese Teilnahme ist Pflicht./
Alle Teilnehmer/innen halten kurz nach Ende der Vorlesungszeit einen 30-minütigen Vortrag über das festgelegte Thema im Rahmen eines Blockseminars. Im Anschluss folgt eine Diskussion über Thema und Vortrag. Es herrscht Anwesenheitspflicht bei allen Vorträgen. Bitte beachten Sie auch die Hinweise zur Foliengestaltung!
Mangelhafte Ausarbeitungen, Plagiate und 1:1-Übersetzungen sowie mangelhafte Vorträge führen zum Nicht-Bestehen des Proseminars. Auch nicht rechtzeitig abgegebene Ausarbeitungen können zum Nicht-Bestehen führen.
Die Vorbesprechung mit Themenverteilung fand am Mittwoch, dem 3. April 2019 um 14:00 Uhr in OH14 R.202 statt.
Die schriftliche Abgabe der Ausarbeitungen muss bis zum 8. Mai 2019 um 23:59 Uhr (pdf per email) an Petra Mutzel erfolgen. Verspätete Abgaben werden nicht akzeptiert und führen zum Nicht-Bestehen des Proseminars. Dasselbe gilt für Ausarbeitungen, die ganz oder teilweise von anderen Arbeiten plagiiert sind (dies inkludiert auch Übersetzungen englischsprachiger Texte).
Diese schriftliche Abgabe wird ab 9. Mai an jeweils zwei Teilnehmer/innen zur Korrektur gesendet. Diese haben dann 2 Wochen Zeit dazu. Wir treffen uns wieder alle am Mittwoch, dem 22. Mai 2019 von 14-16 Uhr in OH14 R.202 zur (dezentralen) Korrekturbesprechung. Das heisst, die Dreiergruppen besprechen hier ihre gegenseitigen Korrekturen. Die Betreuer/innen sind bei Fragen vor Ort.
Danach bleibt Zeit bis zum 5. Juni 2019 um die endgültigen schriftlichen Versionen abzugeben. Diese sind an Petra Mutzel mit cc an Ihre/n Betreuer/in per Email einzureichen.
Die 5-minütigen Vorträge erfolgen am Mittwoch, dem 19. Juni 2019 von 14:00 Uhr bis 17:00 Uhr in OH14 R.202. In diesem Vortrag sollen Sie das behandelte Problem vorstellen und einen Überblick über Ihren Vortrag geben. Die dabei genutzten Folien müssen danach für den Endvortrag nur noch erweitert werden.
Die Treffen in den Kleingruppen erfolgen am Mittwoch, dem 3. Juli 2019 von 14:00 Uhr bis 16:00 Uhr in OH14 R.202.
Die Folien für die jeweiligen Vorträge sind bis zum 10. Juli 2019 per Email bei Petra Mutzel mit cc an Ihre/n Betreuer/in einzureichen.
Die Vorträge finden an den Tagen 31. Juli und 2. August 2019 in OH14 R. 202 jeweils von 10:00-17:00 Uhr statt.
Kriterien der schriftlichen Ausarbeitung:
Kriterien des Vortrags:
Die Anmeldung erfolgt über das zentrale Verfahren und ist bereits abgelaufen.
Bei Fragen zu dieser Veranstaltung wenden Sie sich bitte an Petra Mutzel.