Aktuelles | Inhalte | Unterstützung | Einführende Literatur | Vortragsthemen und Literatur | Verbindliche Regeln zum Erwerb eines Scheins bzw. Bestehen des Moduls  

Seminar zu aktuellen Themen der Theoretischen Informatik: Algorithmen — Datenstrom-Algorithmen

Seminar im SoSe 2011

Gehalten von Prof. Dr. Nicole Schweikardt, Dr. Morteza Monemizadeh

Aktuelles

Einführung

Aktuelle Themen im Bereich der Theoretischen Informatik, insbesondere bezüglich Algorithmen und Komplexität, sind anhand von Originalarbeiten und ergänzender Literatur vorzustellen.
Lernziele: Das Kennenlernen neuester Forschungsergebnisse in der Theoretischen Informatik, das Verstehen wissenschaftlicher Originaltexte, die Fähigkeit zur Einordnung der Inhalte und Aussagen sowie deren Wiedergabe in eigener Darstellung in einem begrenzten Zeitrahmen.

Kürzel laut Studienordnung: M-ATThIA-S.  Creditpoints: 4.  SWS: 2.

Inhalte

Ein Datenstrom ist eine Folge von Daten, auf die nur nach und nach zugegriffen werden kann. Datenstrom-Algorithmen müssen mit sehr wenig Speicher auskommen, und können oft nur eine Approximation der Lösung berechnen. In diesem Seminar werden wir Techniken zum Entwurf und zur Analyse von Datenstrom-Algorithmen genauer untersuchen. Randomisierung ist beim Entwurf essentiell und tritt in Form von Sampling und Hashing auf.
Das Seminar richtet sich an Studierende mit Interesse an und sehr guten Kenntnissen in theoretischer Informatik.

Ort und Zeit

Alle Vorträge finden in Raum 117 (Robert-Mayer-Str. 11-15) statt. Termine:

  1. Mittwoch, 20.04.2011, 14:15-16:00:
    Vorbesprechung und Themenvergabe
  2. Mittwoch, 04.05.2011, 14:15-16:00:
    Vortrag von Morteza Monemizadeh: Grundlegende Begriffe und Resultate aus der Wahrscheinlichkeitsrechnung — Teil I: Markov-Ungleichung, Chybechev-Ungleichung, Chernoff-Schranken (jeweils mit Beweisen) sowie Reservoir Sampling
  3. Mittwoch, 11.05.2011, 14:15-16:00:
    Vortrag von Morteza Monemizadeh: Grundlegende Begriffe und Resultate aus der Wahrscheinlichkeitsrechnung — Teil II: 2-fach bzw. k-fach unabhängige Zufallsvariablen und deren Konstruktion, sowie "An elementary proof of a theorem of Johnson and Lindenstrauss" (Sanjoy Dasgupta and Anupam Gupta, Random Struct. Algorithms 22(1):60-65 (2003))
  4. "Deadline 1": bis spätestens Mittwoch, 01.06.2011, 14:15 Uhr:
    Treffen jedes Seminarteilnehmers mit einem der Organisatoren des Seminars: Klärung von Detailfragen zum Vortragsthema und Vorlage eines groben Konzepts zum Vortrag und zur schriftlichen Ausarbeitung des Vortragsthemas
  5. "Deadline 2": bis spätestens Montag, 20.06.2011, 14:15 Uhr:
    Abgabe der schriftlichen Ausarbeitung des Vortragsthemas bei den Organisatoren des Seminars (Layout: wie in der Layout-Vorlage angegeben)
  6. "Deadline 3": bis spätestens Dienstag, 05.07.2011, 14:15 Uhr:
    Treffen jedes Seminarteilnehmers mit einem der Organisatoren des Seminars: Vorlage eines detaillierten Vortragskonzepts inkl. Vortragsfolien
  7. Dienstag, 26.07. bis Donnerstag, 28.07.2011:
    Blockseminar mit Vorträgen der am Seminar teilnehmenden Studierenden

Unterstützung

Während der Vorlesungszeit stehen jeden Mittwoch von 14:15 bis 15:00 Termine bei Morteza Monemizadeh sowie von 15:00 bis 15:45 Termine bei Nicole Schweikardt zur Verfügung, während denen Seminarteilnehmer Fragen zur Literatur klären können. Falls Sie einen solchen Termin wahrnehmen wollen, melden Sie sich bitte spätestens am Tag vorher per Email an.

Einige generelle Informationen darüber, wie man gute Vorträge im Fach Informatik halten kann, finden sich hier.

Einführende Literatur

Vortragsthemen und Literatur

Verbindliche Regeln zum Erwerb eines Scheins bzw. Bestehen des Moduls

Um das Modul zu bestehen bzw. einen Schein zu erwerben, sind nötig:
  1. Einen Vortrag zu einem der oben genannten Themen zu halten (Dauer: 60 Minuten, plus 10 Minuten zur Diskussion und zur Klärung von Fragen aus dem Publikum),
  2. Abgabe einer schriftlichen Ausarbeitung des Vortragsthemas (abzugeben: spätestens am 20.06.2011; Layout: wie in der Layout-Vorlage angegeben),
  3. Anwesenheit bei mindestens 75% aller Vorträge und
  4. Einhalten der drei oben genannten Deadlines.
Es werden eine Note für den Vortrag und eine Note für die schriftliche Ausarbeitung vergeben. Die Gesamtnote setzt sich folgendermaßen zusammen: