Proseminar Graph-Algorithmen (SS 2019)

Titel Graph-Algorithmen
Veranstalter Prof. Dr. Petra Mutzel
Veranstaltungsart Proseminar (INF-BSc-110, Element 2)
Veranstaltungsnummer 040607
SWS 2
Max. Teilnehmer 16

Inhalt und Themen

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.

Themen

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

Ablauf (geplant)

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.

Termine

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:

  • Darstellung/Formales: Struktur, Literaturangaben (adäquat und sind im korrekten Format), Abbildungen/Tabellen, Form (Formatierung, Erscheinungsbild), frei von grammatikalischen Fehlern, von Zeichensetzung- und Tippfehlern.
  • Stil/Aufbau/Struktur: Schreibstil (Fachbegriffe werden korrekt definiert und verwendet, flüssig geschrieben, gut lesbar), gut strukturiert, Inhalt ist prägnant dargestellt, Verwendung von Latex-Theorem-Umgebungen wie “Definition”, “Lemma”, etc.
  • Inhalt: adäquate Stoffauswahl, evtl. über die Seminarliteratur hinausgehende Quellen, keine inhaltlichen Fehler, eigenständige Aufbereitung des Stoffs, z.B. durch selbst erstellte Beispiele, eigene Formulierungen etc., kritische Auseinandersetzung mit dem Thema
  • Selbstständigkeit in der Vorbereitung: Fragen in Vorbesprechung geklärt, angemessene Schwerpunktsetzung, eigenes eingebracht (Achtung: Fragen an und Diskussionen mit den Betreuern führen nicht zur Abwertung, sondern in der Regel durch die dadurch folgenden qualitativ bessere Abgaben zu besseren Noten; viel eher ist damit gemeint, dass nicht jeder dritte Satz der Ausarbeitung korrigiert werden muss)

Kriterien des Vortrags:

  • Inhalt: Aufbau, adäquater Umfang und Auswahl, Korrektheit, Einbringen eigener Überlegungen (z.B. Beispiele, Graphiken, eigene kritische Anmerkungen), Verständlichkeit (z.B. Definition von Fachbegriffen), Veranschaulichung durch Bilder, eigene Bewertung/Diskussion
  • Präsentation: Vortragsstil (frei, flüssig, Wortwahl, gut verständlich), Folien sinnvoll eingesetzt und sinnvoll gestaltet, Zeitplanung

Anmeldung

Die Anmeldung erfolgt über das zentrale Verfahren und ist bereits abgelaufen.

Ansprechpartner

Bei Fragen zu dieser Veranstaltung wenden Sie sich bitte an Petra Mutzel.

 
Last modified: 2019-06-28 18:05 by Petra Mutzel
DokuWikiRSS-Feed