Vorlesung

Black Box Algorithmen

Hartmut Klauck

SS 05


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.:

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









7.6.2005,   Hartmut Klauck