Termine:
Vorlesung: Mi, 16-18 (Magnus)
Fr, 10-12 (Magnus)
Übung: Do, 12-14 (310)
Zuordnung: T2, T3; alt: T2, T3
Inhalt:
Das Black Box Modell ist vielleicht das einfachste aller
Berechnungsmodelle: auf
n-Bit Eingaben
x(1)...,x(n)
kann nur durch Fragen der Form
x(i)=?
an eine Black Box zugegriffen werden, die Kosten sind gleich der Anzahl
benötigter Fragen um ein Problem zu lösen. Trotz der
Einfachheit des
Modells ergeben sich vielfältige Anwendungen und interessante
Fragestellungen.
Themen der Vorlesung sind z.B.:
- Vergleich von Determinismus, Probabilismus, Quantenalgorithmen;
- fast alle bekannten Quantenalgorithmen basieren auf Black Box
Techniken;
- Property Testing;
- fehlertolerante Black Box Algorithmen;
- Eigenschaften von Funktionen mit effizienten Black Box
Algorithmen: Lernbarkeit, Testbarkeit;
- Zusammenhang zwischen Black Box Komplexität und dem Grad von
Polynomen;
- Untere Schranken für Black Box Algorithmen;
- Time-Space Trade-offs;
- Rechenzeit von Parallelrechnern;
- Orakel-Separationen zwischen Komplexitätsklassen;
- Zusammenhang mit Kommunikationskomplexität.
Vorkenntnisse:
Vordiplom Informatik erwünscht
Scheinerwerb:
Fachgespräch
Vorlesungen:
13.4.:
.pps ,
pdf
[Entscheidungsbäume, Beispiele sublinearer Algorithmen,
Sortierschranke, Randomisierung, Grapheigenschaften, Property Testing]
15.4.:
.pps ,
pdf [Connectivity,
untere Schranke, Adjazenzlistenmodell, Tester, Bipartitheit]
20.4.:
.pps ,
pdf [Bipartitheit]
22.4.:
.pps ,
pdf
[k-Färbbarkeit,Standardform von Testern für
Grapheigenschaften, Clique]
27.4.:
.pps ,
pdf
[Tester für Clique]
29.4.:
.pps ,
pdf
[Approximation von Max Cut I]
4.5.:
.pps ,
pdf
[Approximation von Max Cut II]
13.5.:
.pps ,
pdf
[Allgemeine Ergebnisse zur Testbarkeit, Rivest Vuillemin Theorem]
18.5.:
.pps ,
pdf
[Zertifikate, Nichtdeterminismus, [Block]-Sensitivität]
20.5.:
.pps ,
pdf
[Forts. Blocksensitivität vs. Tiefe, Anwendung: CREW PRAMS]
25.5.:
.pps ,
pdf
[Forts. Anwendung: CREW PRAMS]
1.6.:
.pps ,
pdf
[Separation von R(f), D(f), untere Schranke R(f) via
Block-Sensitivität, Yao Prinzip]
Übungszettel:
15.4:
.ps ,
pdf [Korrektur in Aufg. 5!]
22.4:
.ps ,
pdf
29.4:
.ps ,
pdf
13.5:
.ps ,
pdf
Literatur/Links:
Property Testing:
Vorlesung
v. Rubinfeld/Ben-Sasson
Goldreichs
Property Testing Seite
Übersichtsartikel:
D. Ron:
Property
Testing (A Tutorial), Handbook of Randomization
E. Fischer:
The art of
uninformed decisions:
A primer to property testing,
The Computational Complexity Column of
The Bulletin of
the European Association for Theoretical Computer Science 75
(2001),
97-126
Entscheidungsbäume:
H. Buhrman and R. de Wolf.
Complexity
Measures and Decision Tree Complexity: A Survey.
In
Theoretical Computer Science, 288:21-43, 2002.
Evasiveness:
László Lovász :
Lecture Notes on Evasiveness of Graph Properties