Prof. Dr. Christian Sohler
General
Home
Contact
People
Research
Projects
Teaching
Winter 08/09
Summer 08
Topics for Diploma Thesis
Links
Bonn Research Platform on Algorithmics
Institute of Computer Science
International MSc Program
Durch die gestiegene Vernetzung von Rechnern insbesondere duch das Internet sehen wir uns immer häufiger mit dem Problem der Analyse sehr großer Datenmengen konfrontiert, die in Form von Datenströmen auftreten. Wollen wir z.B. Internetdatenverkehr auf Paketbasis analysieren, so müssen wir riesige Datenmengen verarbeiten und können diese nicht komplett im Rechner oder auf Festplatte abspeichern. Wir benötigen also spezielle Algorithmen, die die Eingabe sequentiell verarbeiten (Paket für Paket) und dabei viel weniger Speicherplatz verwenden als die gesamte Eingabe groß ist.
Inhalt der Vorlesung wird die Modellierung von Datenstromalgorithmen, Techniken zur zur Entwicklung und Analyse sowie untere Schranken sein. Unter anderem werden wir voraussichtlich folgende Probleme untersuchen:
- Anzahl unterschiedlicher Elemente in Datenströmen - Johnson-Lindenstrauss-Lemma - Frequency Moments - Hashing mit beschränkter Unabhängigkeit - Heavy Hitters - Histogramme - Clustering - Graphenalgorithmen (Spanner, Motifs, ...) - untere Schranken - Multipass Algorithmen - u.v.m.
| Zeit, Ort | Mo, Do 13-15, HS C |
| Semesterwochenstunden | 4V + 2Ü |
| Übungen | Do 15-17, HS C (Prof. Dr. Christian Sohler, N. N.) |
| Voraussetzungen | Voraussetzung für die Vorlesung sind grundlegende Kenntnisse in Algorithmen und Datenstrukturen und Wahrscheinlichkeitsrechnung (Erwartungswert, Varianz, Zufallsvariablen). |
| Bereich (alte DPO) | A,C |
| Bereich (neue DPO) | A |
Skript:
Eine vorläufige Version des Skripts finden Sie hier.