Sublineare Algorithmen
Sommersemester 2009
Christian Sohler
News
30.07.2009: Eine vorläufige Version des Skripts kann bei Frank Hellweg (Raum OH14/315 bzw. per E-Mail frank punkt hellweg at tu strich dortmund punkt de) bezogen werden!
Termine
Die erste Vorlesung findet am 14. April 2009 statt.
Der Übungsbetrieb beginnt in der zweiten Vorlesungswoche.
Inhalt
In vielen Anwendungsbereichen der Informatik fallen sehr große Datenmengen an, die nicht im Hauptspeicher eines Rechners gespeichert
werden können und auch häufig nicht auf eine Festplatte passen. Beispiele sind das World Wide Web, Logfiles für Internetdatenverkehr,
oder Querylogs von Suchmaschinen. Häufig kann man diese sehr großen Datensätze selbst mit klassischen Linearzeitalgorithmen nicht mehr
effizient analysieren. Daher benötigt man spezielle Algorithmen, die dies z.B. mit Hilfe von zufälligen Stichproben tun.
Diese Vorlesung gibt einen Überblick über den aktuellen Stand der Forschung in diesem noch recht jungen Gebiet. Die Herangehensweise
ist durch die algorithmische Komplexitätstheorie geprägt, d.h. es wird versucht, konkrete grundlegende algorithmische Probleme zu lösen
und die Mächtigkeit von Verfahren zu charakterisieren.
Voraussetzung für die Vorlesung sind grundlegende Kenntnisse in den Bereichen Algorithmik (insbesondere randomisierte Algorithmen und
Graphenalgorithmen) und Grundlagen der Wahrscheinlichkeitsrechnung.
Mögliche Themen der Vorlesung (die genaue Themenauswahl steht noch nicht fest):
Grundlagen:
- Wahrscheinlichkeitsräume, Zufallsvariablen, Erwartungswert, Varianz
- Markov-Ungleichung
- Chebyshev Ungleichung
- Chernoff/Hoeffding Schranken
Property Testing in dicht besetzten Graphen:
- Bipartitheit
- k-Färbbarkeit
- MaxCut
- MaxCSP
- Szemeredi's Regularity Lemma und der Zusammenhang zum Property Testing
Property Testing in dünn besetzten Graphen:
- Zusammenhang
- k-facher Zusammenhang
- Expansion
- Testbarkeit in planaren Graphen
- Testbarkeit von unter Minorenbildung abgeschlossenen Grapheigenschaften
Testen von Eigenschaften von Verteilungen:
- Ist eine Verteilung die Gleichverteilung?
- Sind zwei Verteilungen identisch?
- Entropie
Sublineare Approximationsalgorithmen in Graphen:
- Durchschnittsgrad in Graphen
- Mminimale Spannbäume
- Max. Matching
- Max. Independent Set in planaren Graphen
Sublineare Approximationsalgorithmen für metrische Räume:
- Durchmesser
- 1-Median
- k-Median
- Facility Location
- Minimalen Spannbäume
Literatur zur Vorlesung
Es wird im Laufe der Vorlesung ein Skript erstellt werden. Ansonsten dienen die Originalarbeiten als Literatur.
Übungen
Es werden abwechselnd Präsenzübungen und Heimübungen stattfinden. Die Übungsblätter werden entsprechend der Ankündigung in der Vorlesung ins Netz gestellt.
Prüfungen
Prüfungsgrundlage ist der Inhalt der Vorlesung Sublineare Algorithmen des Sommersemesters 2009.