Bachelor-Seminar zu aktuellen Themen der Theoretischen Informatik

Seminar im SoSe 2011

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

Aktuelles

• Am Mittwoch, den 04.05. und 11.05. wird Morteza Monemizadeh zwei ins Thema "Datenstromalgorithmen" einführende Vorträge halten (14:15-16:00 Uhr in Raum 117).
• Das erste Seminartreffen zur Vorbesprechung und Vergabe der Vortragsthemen fand am Mittwoch, den 20.04.2011, 14:15-16:00 Uhr in Raum 117 (Robert-Mayer-Str. 11-15) statt.

Einführung

Im Seminar werden aktuelle Themen der theoretischen Informatik behandelt. Das Seminar richtet sich an Studierende mit besonderem Interesse an theoretischer Informatik.
Lernziele: Kenntnis zentraler und aktueller Methoden und Verfahren der theoretischen Informatik, Einüben der Literatursuche und -analyse, sowie Präsentationstechniken, Kompetenz in Methoden der theoretischen Informatik; autodidaktische Kompetenz.

Kürzel laut Studienordnung: B-ATThI-BS.  Creditpoints: 5.  SWS: 2.

Inhalte

In diesem Seminar werden der Entwurf und die Analyse von Datenstrom-Algorithmen betrachtet.
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.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

• Einen sehr schönen Überblick über die für dieses Seminar nötigen Grundlagen aus der Stochastik bietet Abschnitt 1.4 des Skriptes zur Vorlesung Internet Algorithmen (Sommersemester 2011) von Prof. Dr. G. Schnitger. Das Skript können Sie auf der Webseite zur Vorlesung herunterladen. Abschnitt 4.2 des Skriptes enthält auch eine schöne Darstellung des Reservoir Sampling Algorithmus, mit dem man Stichproben aus Datenströmen gleichverteilt ziehen kann.
• Hash-Tabellen und Hash-Funktionen werden in Abschnitt 8.4 des Buches Randomized Algorithms von Rejeev Motwani und Prabhakar Raghavan (Cambridge University Press, 1995) gut erklärt.
• Das Buch Data Streams: Algorithms and Applications von S. Muthu Muthukrishnan gibt einen umfassenden Überblick über das Forschungsgebiet der Datenstrom-Algorithmen.
• Auf den Webseiten der beiden Worshops zu Datenstrom-Algorithmen in Aarhus 2007 und Kanpur 2006 finden sich Vortragsfolien und z.T. auch Videoaufnahmen von Überblicksvorträgen.

Vortragsthemen und Literatur

• Noga Alon, Yossi Matias, Mario Szegedy: The Space Complexity of Approximating the Frequency Moments. J. Comput. Syst. Sci. 58(1): 137-147 (1999) Section 2 : F_k, Sampling.
• Noga Alon, Yossi Matias, Mario Szegedy: The Space Complexity of Approximating the Frequency Moments. J. Comput. Syst. Sci. 58(1): 137-147 (1999) Section 2 : F_2, Sketching.
• Moses Charikar, Kevin Chen, Martin Farach-Colton: Finding frequent items in data streams. Theor. Comput. Sci. 312(1): 3-15 (2004) Sections 3,4.
• Graham Cormode, S. Muthukrishnan: An improved data stream summary: the count-min sketch and its applications. J. Algorithms 55(1): 58-75 (2005) Sections 3,4,5.

Verbindliche Regeln zum Bestehen des Moduls

Um das Modul zu bestehen 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:

• Falls einer der folgenden 4 Fälle eintritt, so ist die Gesamtnote eine 5.0 und das Modul wird als "nicht bestanden" gewertet:
  1. Der Teilnehmer war an weniger als 75% der Vorträge anwesend.
  2. Der Teilnehmer erhielt für seinen Vortrag die Note 5.0.
  3. Der Teilnehmer erhielt für seine schriftliche Ausarbeitung die Note 5.0.
  4. Der Teilnehmer hat mindestens eine der drei oben genannten Deadlines nicht eingehalten.
• Falls keiner der obigen 4 Fälle eintritt, so wird ein Seminarschein erteilt bzw. das Modul wird als "bestanden" gewertet, und die Gesamtnote setzt sich zu 2/3 aus der Note für den Vortrag und zu 1/3 aus der Note für die schriftliche Ausarbeitung zusammen.