Logik in der Informatik Prof. Dr. Martin Grohe

Aktuelles

An dieser Stelle finden Sie im Laufe des Seminars aktuelle Mitteilungen.

• Der Vortrag am 28.6. beginnt ausnahmsweise erst um 15:30 Uhr.
• Am 17. Mai 2010 findet das Seminar wegen des Dies Academicus nicht statt.
• Die Vorbesprechung und Themenvergabe findet am Montag, dem 12. April statt.

Einführung

Ein Datenstromalgorithmus bekommt als Eingabe eine Folge von Datenelementen, die er nur einmal von links nach rechts liest. Üblicherweise steht nur ein sehr kleiner Arbeitsspeicher und sehr wenig Zeit pro Element zur Verfügung. Solche Algorithmen sind vor allem zur Verarbeitung von Datenströmen, wie sie z.B. in der Netzwerküberwachung vorkommen, oder aber zur Verarbeitung von riesigen Datenmengen interessant.

In diesem Seminar werden algorithmische Techniken und Datenstrukturen für Datenstromalgorithmen vorgestellt, aber auch Werkzeuge zum Nachweis unterer Schranken an den für einen Datenstromalgorithmus zur Lösung eines Problems benötigten Speicherplatz.

Zeit und Raum

Montags 15-17 Uhr im Erwin Schrödinger-Zentrum (Rudower Chausee 26), Raum 1'306.

Einführende Literatur

Überblicksartikel zu Datenströmen:

• S. Muthukrishnan, Data Streams: Algorithms and Applications. 2003.
• B. Babock, S. Babu, M. Datar, R. Motwani, J. Widom, Models and Issues in Data Stream Systems. 2002.

Zu randomisierten Algorithmen:

• R. Motwani und P. Raghavan, Randomized Algorithms. Cambridge University Press, 1995.
• N. Alon und J. Spencer, The Probabilistic Method. Wiley-Interscience, 2000.

Zu Kommunikationskomplexität:

• E. Kushilevitz und N. Nisan, Communication Complexity. Cambridge University Press, 1999.
  
  Siehe auch den Überblicksartikel von E. Kushilevitz.

Interessant sind vielleicht auch Kapitel 1 und 4 aus dem Skript zur Vorlesung Internet-Algorithmen von Prof. Dr. Georg Schnitger an der Goethe-Universität Frankfurt am Main.

Vortragsthemen

1. J.I. Munro, M.S. Paterson,
   Selection and Sorting with Limited Storage.
   Theoretical Computer Science 12, S. 315-323, 1980.
   
   
2. Abschnitt 1 und 2 aus
   N. Alon, Y. Matias, M. Szegedy,
   The Space Complexity of Approximating the Frequency Moments.
   Journal of Computer and System Sciences 58(1), S. 137-147, 1999.
   
   
3. Abschnitt 3 aus
   N. Alon, Y. Matias, M. Szegedy,
   The Space Complexity of Approximating the Frequency Moments.
   Journal of Computer and System Sciences 58(1), S. 137-147, 1999.
   
   
4. V. Braverman, R. Ostrovsky, C. Zaniolo,
   Optimal Sampling from Sliding Windows.
   Proceedings PODS'09, S. 147-156.
   
   
5. G. Cormode und S. Muthukrishnan,
   An Improved Data Stream Summary: The Count-Min Sketch and Its Applications.
   Journal of Algorithms 55(1), S. 58-75, 2005.
   
   
6. S. Ganguly,
   Counting Distinct Items over Update Streams.
   Theoretical Computer Science 378, S. 211-222, 2007.
   
   
7. S. Ganguly, A. Majumder,
   Deterministic K-Set Structure.
   Information Processing Letters 109, S. 27-31, 2008.
   
   
8. M. Grohe, C. Koch, N. Schweikardt,
   Tight Lower Bounds for Query Processing on Streaming and External Memory Data.
   Theoretical Computer Science 380, S. 199-217, 2007.
   
   
9. C. Demetrescu, I. Finocchi und A. Ribichini,
   Trading Off Space for Passes in Graph Streaming Problems.
   Proceedings SODA'06, S. 714-723.
   
   
10. M. Zelke,
    Weighted Matching in the Semi-Streaming Model.
    Proceedings STACS'08, S. 669-680.

Vorträge