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

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

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

• 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

• Ziv Bar-Yossef, T. S. Jayram, Ravi Kumar, D. Sivakumar, Luca Trevisan: Counting Distinct Elements in a Data Stream. RANDOM 2002: 1-10 Sections 2,3,4 : F_0.
• Piotr Indyk: Sublinear Time Algorithms for Metric Space Problems. STOC 1999: 428-434 Sections 3,4 : 1-median und k-median.
• Sudipto Guha, Adam Meyerson, Nina Mishra, Rajeev Motwani, Liadan O'Callaghan: Clustering Data Streams: Theory and Practice. IEEE Trans. Knowl. Data Eng. 15(3): 515-528 (2003) Sections 3,4 : k-median.
• Piotr Indyk: Algorithms for dynamic geometric problems over data streams. STOC 2004: 373-380 Sections 3,4,5 : MST, Matching und Facility location.
• Bernard Chazelle, Ronitt Rubinfeld, Luca Trevisan: Approximating the Minimum Spanning Tree Weight in Sublinear Time. SIAM J. Comput. 34(6): 1370-1379 (2005) Sections 2,3,5 : MST.
• Gereon Frahling, Piotr Indyk, Christian Sohler: Sampling in Dynamic Data Streams and Applications. Int. J. Comput. Geometry Appl. 18(1/2): 3-28 (2008) Sections 3,4 : MST.
• Sariel Har-Peled, Soham Mazumdar: On coresets for k-means and k-median clustering. STOC 2004: 291-300 Sections 4,7 : k-median, Coreset und Strom Algorithmus.
• Gereon Frahling, Christian Sohler: Coresets in dynamic geometric data streams. STOC 2005: 209-217 Sections 3 : k-median, Coreset und Strom Algorithmus.
• Piotr Indyk: A near linear time constant factor approximation for Euclidean bichromatic matching (cost). SODA 2007: 39-42 Whole paper : Earth Mover Distance (EMD).
• Joan Feigenbaum, Sampath Kannan, Andrew McGregor, Siddharth Suri, Jian Zhang: On graph problems in a semi-streaming model. Theor. Comput. Sci. 348(2-3): 207-216 (2005) Section 3: Maximum Matching.
• Krzysztof Onak, Ronitt Rubinfeld: Maintaining a large matching and a small vertex cover. STOC 2010: 457-464 Maximum Matching and vertex cover.
• Huy N. Nguyen, Krzysztof Onak: Constant-Time Approximation Algorithms via Local Improvements. FOCS 2008: 327-336 Section 2,3 : Maximum Matching.
• Funda Ergün, Sampath Kannan, Ravi Kumar, Ronitt Rubinfeld, Mahesh Viswanathan: Spot-Checkers. J. Comput. Syst. Sci. 60(3): 717-751 (2000) Whole paper : Tester for Sorting.
• Parikshit Gopalan, T. S. Jayram, Robert Krauthgamer, Ravi Kumar: Estimating the sortedness of a data stream. SODA 2007: 318-327 Sections 2,3 : Streaming implementation of the tester.

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:

• Falls einer der folgenden 4 Fälle eintritt, so ist die Gesamtnote eine 5.0 und es wird kein Seminarschein erteilt bzw. 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.