Vorlesung (3V)

Sublineare Algorithmen

Wintersemester 2006/07

Veranstalterin:	Beate Bollig beate.bolliguni-dortmund.de
Termine:	montags 14:15-15:45 Uhr (alle 14 Tage) mittwochs 8:30-10:00 Uhr Start 18.10.2006
Raum:	R 3.05 OH 14 (montags) und SR 3.04 OH 14 (mittwochs)

Inhalt:

Im Bereich der Algorithmentheorie versteht man unter effizienten Algorithmen häufig polynomielle und bestenfalls lineare Algorithmen. Heutzutage kommen jedoch in vielen Anwendungen derartig große Datenmengen vor, dass diese selbst mit klassischen Linearzeitalgorithmen nicht mehr behandelt werden können, da diese zu langsam oder zu speicherintensiv sind. In der Vorlesung geht es um den Entwurf und die Analyse sogenannter sublinearer Algorithmen für die neue Konzepte gefragt sind. Ein weit verbreitetes Konzept ist Sampling, das Ziehen einer kleinen, geschickt ausgewählten Stichprobe, von der man sich erhofft, dass sie repräsentativ für die Struktur aller Daten ist. Ein weiteres Konzept ist Streaming. Hier kommen die Daten sequentiell in Form eines Datenstroms an und die Aufgabe besteht darin, von den bereits betrachteten Daten lediglich eine Skizze anzufertigen, um Speicherplatz zu sparen.

Die Vorlesung führt in das Gebiet ein und stellt Entwurfsmethoden und Analysetechniken beispielhaft für Algorithmen aus unterschiedlichen Bereichen vor. Teilgebiete sind

Sublineare Approximationsalgorithmen

Property Testing

Streaming Algorithmen

Der Schwerpunkt der Vorlesung liegt im Bereich Property Testing.

Literatur:

Leider existiert noch kein Lehrbuch im Bereich Sublinearer Algorithmen, die Vorlesung orientiert sich überwiegend an Originalliteratur. Teile der Vorlesung orientieren sich an Christian Sohlers Skript zur Vorlesung Sublineare Algorithmen (WS04/05). (Siehe Christian Sohlers Vorlesung.) (Vorsicht, bei dem Skript handelt es sich um eine vorläufige Version).

Einen kurzen Überblick über das Gebiet Sublineare Algorithmen bietet:

Rubinfeld, R. (2006). (Ronitt Rubinfelds Publikationen )
Sublinear time algorithms.

Einen guten Überblick über das Gebiet Property Testing im speziellen bieten:

Fischer, E. (2001). (Eldar Fischers Publikationen )
The art of uninformed decisions. A primer to property testing.
Bulletin of the European Association for Theoretical Computer Science, 75:97-126.
Ron, D. (2001). (Dana Rons Publikationen )
Property testing.
In Handbook of Randomized Algorithms. Kluwer Academic Publishers.

In der Vorlesung verwendete Originalliteratur (nicht vollständig):

Alon, N., Dar, S., Parnas, M., Ron, D. (2003).
Testing of Clustering.
SIAM Journal on Discrete Mathematics 16 (3), 393-417.
Bender, M.A., Ron, D. (2002).
Testing Properties of directed graphs: acyclicity and connectivity.
Random Struct. Algorithms 20 (2), 184-205.
Chazelle, B., Rubinfeld, R., Trevisan, L. (2001).
Approximating the minimum spanning tree weight in sublinear time.
ICALP, LNCS 2076, 190-200.
Dodis, Y., Goldreich, O., Lehman, E., Raskhodnikova, S., Ron, D., Samorodnitsky, A. (1999).
Improved testing algorithms for monotonicity.
RANDOM-APPROX, LNCS 1671, 97-108.
Goldreich, O., Goldwasser, S., Ron, D. (1998).
Property Testing and its connection to learning and approximation.
Journal of the ACM 45 (4), 653-750.
Goldreich, O., Goldwasser, S., Lehman, E., Ron, D., Samorodnitsky, A. (2000).
Testing monotonicity.
Combinatorica 20 (3), 301-337.
Goldreich, O., Ron, D. (2002).
Property testing in bounded degree graphs.
Algorithmica 32 (2), 302-343.
Parnas, M., Ron, D. (2005).
On approximating the minimum vertex cover in sublinear time and the connection to distributed algorithms.
ECCC Report 94.
Raskhodnikova, S. (2003).
Approximate testing of visual properties.
Approximation, Randomization, and Combinatorial Optimization
Algorithms and Techniques, LNCS 2764, 370-381.

Inhalt der Vorlesung

18.10.2006: Motivation und Überblick über die Vorlesung, Beispiel Durchmesser in metrischen Räumen, Beispiel Testen auf Nullvektor, Sublineare Algorithmen und Property Testing im speziellen, Beispiel Test auf Sortiertheit

22.10.2006: Analyse Test auf Sortiertheit (Fortsetzung), Grundlagen der Wahrscheinlichkeitstheorie (Wiederholung), Sublinearer det. Approximationsalgorithmus für das Finden einer Senke in Turniergraphen, Wahrscheinlichkeitstheoretische Grundlagen (Wiederholung), probability amplification für randomisierte Algorithmen mit ein- und zweiseitigem Fehler (Wiederholung), Test auf Monotonie für boolesche Vektoren, Testen von Grapheigenschaften: Modelle

25.10.2006: Testen von Grapheigenschaften: Adjazenzlisten-Modelle, Test auf Graphzusammenhang im unbeschränkten Adjazenzlisten-Modell, Test auf Kreisfreiheit im gradbeschräkten Adjazenzlisten-Modell

6.11.2006: Test auf Graphzusammenhang im gradbeschränkten Adjazenzlisten-Modell, Test, ob ein Graph einen Eulerpfad hat

15.11.2006: Analyse Test auf Kreisfreiheit im gradbeschränkten Adjazenzlisten-Modell, Test auf Kreisfreiheit in gerichteten Graphen (Adjazenzmatrix-Modell), Testen visueller Eigenschaften

20.11.2006: Analyse Test auf Kreisfreiheit in gerichteten Graphen, Fortsetzung Testen visueller Eigenschaften

22.11.2006: Fortsetzung Testen visueller Eigenschaften,

29.11.2006: Fortsetzung Test, ob Bild konvex ist, Test auf Bipartitheit im Adjazenzmatrix-Modell

4.12.2006: Analyse Test auf Bipartitheit als Spiel, Einführung sublineare Approximationsalgorithmen

6.12.2006: Vertiefung Analyse Test auf Graphzusammenhang, Bipartitheit, kleinstes Element in einer Menge

13.12.2006: sublineare Approximationsalgorithmen: Anzahl Zusammenhangskomponenten im gradbeschränkten Adjazenzlisten-Modell

18.12.2006: Vorlesung verlegt auf 8.1.2007

20.12.2006: sublineare Approximationsalgorithmen: Gewicht minimaler Spannbäume, Einführung Datenströme

8.1.2007 : Datenstromalgorithmus für EMST

10.1.2007: Test boolescher Funktionen auf Monotonie

15.1.2007: Fortsetzung Test von Funktionen auf Monotonie

17.1.2007: Monotonie: Halls Theorem, zufällige Stichprobe gegen gezielte Anfragen

24.1.2007: Test von Funktionen auf Linearität

29.1.2007: Approximatonsalgorithmen für Vertex Cover

31.1.2007: Vorlesung verlegt auf 5.2.2007

5.2.2007 : Testalgorithmen für Clustering

7.2.2007: Verallgemeinerung des Linearitätstests für nichtboolesche Funktionen; Rückblick; von der Vorlesung zur Forschung

Aufgaben

Folien und weitere Unterlagen

Die bisher benutzten Folien zur Vorlesung sind hier erhältlich.

Joschas Zusammenfassung über Approximationsalgorithmen für Vertex Cover und Nicos Zusammenfassung über Clustering stehen ebenfalls hier.

7.2.2007 - Beate Bollig