Proseminar: Perlen der Theoretischen Informatik (SoSe 22)

Inhaltsverzeichnis

Thematik: Streaming Algorithmen

Das sind Algorithmen, die große Datenmengen „on the fly“, d.h. mit wenig Speicher verarbeiten und dabei Eigenschaften des Datenstroms ermitteln bzw. schätzen. Sie finden Anwendung in datenintensiven Bereichen wie automatischem Prüfen von Videomaterial, Auswertung astronomischer oder genomischer Daten usw. In diesem Proseminar werden nicht die Anwendungen sondern die algorithmischen Grundlagen in ihrer Grundform, sozusagen „in vitro“ studiert.

Literatur Als Grundlage nutzen wir das Buch/Skript „Data Stream Algorithms“ — trotz des Draft-Status hervorragend geeignet für erste Schritte in diesem Bereich.

Themen Die Themenliste der Vorträge entspricht den Kapiteln des Buchs, beginnend bei Kapitel 1, aber die Themenanzahl ist aus Zeitgründen begrenzt und damit auch die Anzahl der Teilnehmer.

Zeit, Ort und Organisationsform

  • Vorbesprechung = erste Sitzung: 21.4.2022
  • donnerstags 10:00-11:30 im Seminarraum 0.101 (Präsenzbetrieb)

    ACHTUNG Am 9. Juni findet die Sitzung ersatzweise online statt, im BBB-Meetingraum von Stud.IP (Vortragende melden sich bitte vorher gemeinsam bei mir für die Detailabsprachen bzw. 15 Minuten vor Beginn für einen kurzen Technik-Check).

  • Organisation und Informationsaustausch: Interessenten melden sich bitte in der Stud.IP-Veranstaltung an
    • alle Materialien werden dort zur Verfügung gestellt
    • Forum, Mailingliste und Wiki werden zum Informationsaustausch genutzt

Prüfungsleistung

Die Prüfungsleistung (anrechenbar wahlweise als Modul B.Inf.1207 oder B.Inf.1208) wird benotet, das Benotungsschema ist im Stud.IP-Wiki angegeben. Sie besteht aus diesen Teilen:

  • Vortrag und Ausarbeitung (s.u.) zu einem behandelten Thema und
  • den Vorträgen folgen (Notizen machen) und Beteiligung an der Diskussion zu jedem der Vorträge anderer Teilnehmer (d.h. Fragen an Vortragende richten, Bemerkungen zum Thema, im Anschluss Kritk und Würdigung des Vortrags - Details dazu in der ersten Sitzung)

Die Ausarbeitung besteht aus einem Jupyter-Notebook, in der

  • die Hintergründe (vollständig: Problemstellung, Lösungsidee, Beweise und ggf. Übungsaufgaben) zum Thema in eigenen Worten erklärt werden und auch die Originalliteratur1 aufgeführt sind (erfordert i.d.R. etwas Recherche)
  • das Wichtigste in Python implementiert wird und anhand geeigneter selbst zu wählender Daten (hier einige Vorschläge) ausgeführt werden kann und
  • das Ergebnis der Ausführung geeignet analysiert und mit theoretischen Vorhersagen verglichen wird

Für den Vortrag wird ebenfalls das Notebook genutzt, aber in Form einer Jupyter-Slideshow (ausgewählte Passagen des originalen Notebooks werden präsentiert und erläutert). Dazu wird die GWDGJupyter Cloud vom Hörsaal-PC aus genutzt (Beispiel und Anleitung dazu in der ersten Sitzung, später im Download verfügbar).

Das Notebook (mit Link auf verwendete Daten) und der slides.html-Export dazu sind im Anschluss in einen (allen zugänglichen) Stud.IP-Ordner hochzuladen.

Ablauf

Startphase (Sitzungen 21. + 28. April)
Einführung in die Thematik, Lesen im Skript (mindestens Kapitel 0), Themenvergabe
Vorbereitungsphase (Selbststudium)
Einarbeitung in das Thema, Vertrautmachen mit der Technik, Entwurfsfassung eines Notebooks für Vortrag vorbereiten
Probephase (Sitzungen 12. + 19. Mai, 2. + 9. Juni)
Bei jeder Sitzung gibt es bis zu zwei Probevorträge (je max. 35min) mit anschließender Aussprache (max. 10min). Bei den Vorträgen gibt es keine Zwischenfragen, in der Aussprache stellen alle Teilnehmer Fragen (z.B. auch technische) anhand ihrer Notizen und geben Anregungen und Verbesserungsvorschläge.
Kolloquium (Sitzungen 23. + 30. Juni, 7. + 14. Juli)
Bei jeder Sitzung bis zu zwei überarbeitete Vorträge (je max. 30min) mit anschließender wissenschaftlicher Diskussion und kritischer Würdigung (max. 15min). Bei den Vorträgen gibt es keine Zwischenfragen, im Anschluss stellen die Teilnehmer Fachfragen an die Vortragenden und geben schließlich ihre Eindrücke vom Vortrag wieder.

Formalia

  • implementierte Module: B.Inf.1207 und B.Inf.1208 (5C)
  • Flexnow: Anmeldung bis Ende April (wird noch eingerichtet)
  • Erklärung zur Plagiatsanalyse etc.: bitte unterschreiben und gescannt/fotografiert in den dafür vorgesehenen Stud.IP-Ordner (write-only) hochladen.

Fußnoten:

1

wissenschaftlicher Fachaufsatz, in dem der jeweilige Algorithmus publiziert wurde

Datum: <2022-03-24 Do>

Autor: Carsten Damm

Created: 2022-03-24 Do 11:17

Validate