Proseminar: Perlen der Theoretischen Informatik (SoSe 23)
ALLE ANGABEN SIND VOR BEGINN NOCH ALS VORLÄUFIG ANZUSEHEN

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“ von — trotz des Draft-Status hervorragend geeignet für erste Schritte in diesem Bereich.

Themen Die Themenliste der Vorträge entspricht „Lectures“ des Buchs, aber die Themenanzahl ist aus Zeitgründen begrenzt und damit auch die Anzahl der Teilnehmer. Genauer geht es um diese Lectures: 1–6, 9 und 10.

Zeit, Ort und Organisationsform

• Vorbesprechung = erste Sitzung: 12.4.2023
• mittwochs 10:00-11:30 (voraussichtlicht im Seminarraum MN12 (Geo))
• Organisation und Informationsaustausch: Interessenten melden sich bitte in der Stud.IP-Veranstaltung an
  • alle Materialien werden dort zur Verfügung gestellt
  • Mailingliste und Wiki werden zum Informationsaustausch genutzt

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, Analyse und ggf. Übungsaufgaben) zum Thema in eigenen Worten erklärt werden und auch die Originalliteratur¹ 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 bzw. im Video).

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.

Startphase (Sitzungen 1 und 2: 12. + 19. April)

Einführung in die Thematik, Lesen im Skript (mindestens Kapitel 0), Themenvergabe, Klärung von Fragen zur Organisation

Vorbereitungsphase (Selbststudium)

Gründliche Einarbeitung in das gewählte Thema, Lesen der Kapitel zu den anderen vergebenen Themen, Vertrautmachen mit der Technik, Programmieren der Algorithmen, Auswahl von Testdaten

Vorstellung der Algorithmen (Sitzungen 3 bis 6: 10. + 17. + 24. + 31. Mai)

Bei jeder Sitzung zwei Probevorträge (Idee, Algorithmus und Analyse kurz, Implementierung detailliert vorstellen, Beratung zur Datenauswahl), alle beteiligen sich mit Fragen / Anregungen an der Diskussion (pro Vortrag max. 40min inkl. Diskussion)

Eintägiges Blockkolloquium (Termin wird am 19. April gemeinsam festgelegt)

Jeweils:

• polierte Jupyter-Slideshow-Vorträge (max. 25min) mit etwa diesem Aufbau: Motivation, Unterschied zum vorigen Thema, algorithmische Idee (z.B. Pseudocode oder ausgewählte Passagen der Implementation zeigen) und theoretische Analyse, Demo auf Testdaten (soweit möglich) und/oder Ergebnisse von Leistungsmessungen auf Testdaten vorstellen, kurzer Ausblick auf nächstes Thema (dabei Unterschiede zum eigenen Thema herausstellen)
• anschließende wissenschaftlicher Diskussion und kritische Würdigung (max. 10min): Bei den Vorträgen gibt es keine Zwischenfragen, im Anschluss beteiligen sich alle durch wenigstens eine Fachfrage
• in der Pause (max. 10min) bitte kurzen Ankreuz-Fragebogen zum Vortrag ausfüllen

• 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.