Black Box Algorithmen

Hartmut KlauckUniversität FrankfurtSS 05

13.5.

Organisatorisches Vorlesung: Mi. 16-18, Fr. 10-12 c.t. Übung: Mo. 16-18 SR 11(ab 18.4.) Schein: Fachgespräch Zuordnung T2,T3 Voraussetzung: Vordiplom

(Informatik, Mathematik oder Physik) Website:

www.thi.informatik.uni-frankfurt.de/~klauck/BB05.html

Themen der Vorlesung

Algorithmen mit sublinearer Laufzeit Unter welchen Umständen ist es möglich, etwas zu

berechnen, ohne genug Zeit zu haben, die gesamte Eingabe zu lesen?

Nicht: Parallele Algorithmen Untere Schranken für die Anzahl der Lesezugriffe auf die

Eingabe Was sind Lesezugriffe? Untere Schranken Laufzeit, Time-Space Tradeoffs

Verschiedenen Berechnungsmodi Deterministisch Randomisiert Nichtdeterministisch Quantenmechanisch

Entscheidungsbäume

Einfachstes Berechnungmodell (?) Definition 1.1: Eingabe: x1,...,xn : n Bits Funktion f: {0,1}n! {0,1}

zu berechnen Baum, Knoten fragen Variablen ab, Kante verzweigen

entsprechend, Blätter mit Funktionswert markiert

Entscheidungsbäume

Beispiel: f(x,y,z)=x Ç(y©z)

Komplexität einer Funktion

Definition 1.2.: Tiefe eines Baums: entspricht Anzahl der Lesezugriffe auf die Eingabe, maximiert über alle Eingaben

D(T): Tiefe des Baums T (Deterministische Tiefe)

D(f)=min{D(T): T berechnet f} minimale Anzahl der Lesezugriffe auf die

Eingabe( im worst case) eines Baums für f

Ein Problem, das schnell gelöst werden kann Gegeben sei ein Tournament:

n Spieler/Mannschaften, jeder gegen jeden Matrix: M[i,j]=1 wenn i gewonnen hat kein Unentschieden

Gibt es eine Mannschaft, die gegen alle anderen gewonnen hat?

n2 - n Eingaben abfragbar ! Bzw. Eingaben

Ein Problem, das schnell gelöst werden kann Eingaben abfragbar ! Entscheidbar mit O(n) Fragen/in Zeit O(n) Algorithmus:

Frage [1,2] Verlierer kann nicht gegen alle anderen gewonnen

haben, “entferne” Spalte und Zeile des Verlierers Iteration Pro Runde eine Frage, ein Spieler entfernt Nach n-1 Runden noch 1 Spieler übrig Teste, ob dieser alle Spiele gewonnen hat

Insgesamt 2n-3 Fragen

Ein Problem, das schnell gelöst werden kann Algorithmus:

Frage [1,2] Verlierer kann nicht gegen alle anderen gewonnen

haben, “entferne” Spalte und Zeile des Verlierers Iteration Pro Runde eine Frage, ein Spieler entfernt Nach n Runden noch 1 Spieler übrig Teste, ob dieser alle Spiele gewonnen hat

Insgesamt 2n-3 Fragen Zeit: Speichere alle nicht entfernten Spieler in Liste,

teste erste zwei in Liste, also Zeit O(n)

Struktur des Problems

Nicht alle Matrizen sind als Eingaben erlaubt, nur Tournament Matrizen (M[i,j]=M[j,i]=1 nicht erlaubt)

Algo funktioniert auch auf beliebigen gerichteten azyklischen Graphen

Nur spezielle Eingaben erlaubt, was ist mit Problem, wenn alle Matrizen/Graphen erlaubt sind? “Gibt es eine Zeile 1111...1111 ?” Dann sind mind. (n2) Fragen notwendig

Noch ein Problem

Gegeben seien n Punkte in einem metrischen Raum, mit Distanzen in einer Matrix D[i,j]

Gesucht: maximale Distanz maxi,j D[i,j]

Algorithmus: wähle beliebiges 1· i· n Berechne E=maxj D[i,j] Klar: nur n Fragen Auch klar: E· maxi,j D[i,j] Ist E auch eine gute Abschätzung?

Seien a,b so dass D[a,b] maximal Dann ist D[a,b]· D[a,i]+D[i,b]· 2E

Algorithmus ist approximativ

Sublineare Algorithmen

Es gibt Probleme, die in sublinearer Zeit lösbar sind

Oft sind Anforderungen an die Eingabe im Spiel

Algorithmen sind typischerweise randomisiert, oft liefern sie nur ein approximatives Ergebnis

Untere Schranken

SortierproblemAlgorithmen: Laufzeit O(n log n), wie

Quicksort (randomisiert), Heapsort etc.

Vergleichsbasierte Algorithmen brauchen Zeit (n log n)

Beweis: basiert auf Entscheidungsbäumen

Untere Schranke für Sortieren Eingabe: x1,...,xn, Zugriff nur durch Vergleiche Eingabe: Matrix, M[i,j]=1 wenn xi·xj

n2 Eingaben! Behauptung: (n log n) Fragen notwendig Beweis:

Angenommen {x1,...,xn}={1,...,n} Blätter des Baumes sind mit Permutationen markiert

(: x(i) ist sortiert) Jede Permutation ist möglich, taucht daher an einem

der Blätter auf Es gibt n! Permutationen Tiefe¸ log2 Anzahl Blätter¸ log2 n!=(n log n)

Entscheidungsprobleme

Sortieren hat viele Ausgaben, daher viele verschiedene Blätter im Entscheidungsbaum, also viele Fragen

Einfach zu verstehen! Was ist mit Funktionen {0,1}n! {0,1}? Beispiele:

Oder(x1,...,xn)=1 wenn es xi=1 gibt Und(x1,...,xn)=1, wenn alle xi=1 Mehrheit(x1,...,xn)=1 wenn n/2 mal xi=1 Parität(x1,...,xn)= xi mod 2 Index(x1,...,xn,y1,...,ylog n)=xy

Untere Schranken D(f)

Zum Beispiel Oder(x1,...,xn) Adversary Argument:

Algorithmus berechne Oder Es seien t Fragen gestellt Nächste Frage wird mit “xi=0” beantwortet

• “Gegner konstrolliert Eingabe” Nach n-1 Fragen immer noch unklar, ob Oder=1 ! Daher n Fragen notwendig

Analog: Und, Parität Argument f. Majorität nicht viel schwieriger Alle brauchen n Fragen

Gibt es einfache Funktionen? Index(x1,...,xn,y1,...,ylog n)=xy

Frage y’s, Frage xy, also log n+1 Fragen

Theorem 1.1: Eine Funktion, die von allen Eingaben abhängt, braucht D(f)¸ log n

Beweis: Wenn f von allen Variablen abhängt, taucht

jedes xi an einem Knoten des Baumes auf Daher gibt es mindestens n innere Knoten,

was nur bei Tiefe log n möglich ist.

Frage:

Sind randomisierte (vergleichbasierte) Algorithmen zum Sortieren schneller?

Anwort: Nein, Beweis später

Randomisierte Entscheidungsbäume Definition 1.3.:

Ein randomisierter Entscheidungsbaum hat zusätzliche Knoten, an denen eine Münze geworfen wird

Ein randomisierter Entscheidungsbaum berechnet eine Funktion korrekt, wenn auf jeder Eingabe mit Wahrscheinlichkeit 2/3 das richtige Ergebnis produziert wird

Tiefe ist wie zuvor definiert, wobei Zufallsknoten nicht mitgerechnet werden

Komplexitätsmass R(f) ist Minimum der Tiefe, über alle korrekten randomisierten Entscheidungsbäume für f

Randomisierte Entscheidungsbäume Beispiel: f(x,y,z)=xÇyÇ z Randomisierter Algorithmus:

ziehe Zufallsvariable r aus {1,2,3} x,z, oder y=1: Akz. Sonst verwerfe

Tiefe 2 Fehler: 1/3

für alle Eingaben

Randomisierte Entscheidungsbäume f(x,y,z)=xÇyÇ z Randomisierter Algorithmus:

ziehe Zufallsvariable r aus {1,2,3} x,z, oder y=1: Akz. Sonst verwerfe

Fazit

Jede Komplexität D(f) zwischen log n und n kann auftreten

Im allgemeinen konstante Laufzeit deterministisch nicht zu erreichen

Plan der Vorlesung

1. (Partielle) Funktionen mit sehr schnellen Algorithmen ) Property Testing

2. Komplexität von Entscheidungsbäumen1. Wie kann man systematisch Schranken zeigen?2. Was hilft Randomisierung

(Nichtdeterminismus/Quantenberechnung) ?3. Quantenalgorithmen

3. Anwendungen:1. Lernbarkeit2. Laufzeit von Parallelrechnern3. Tradeoffs zwischen Zeit und Platz 4. ...

Property Testing

Szenario zunächst: Eingabe ist Adjazenzmatrix eines (un)gerichteten Graphen

Definition 1.4.: Grapheigenschaft: Boolesche Funktion, die alle Graphen mit ja/nein klassifiziertUND die invariant unter Permutation der Knoten ist

Beispiel: Hat mindestens eine Kante ist Grapheigenschaft Hat Kante zwischen 1 und 2 ist keine

Grapheigenschaften

“Hat eine Kante” ist welche Funktion? Oder auf Variablen Braucht also viele Fragen Definition 1.5.: Grapheigenschaften mit

D(f)= heissen schrecklich.(engl. evasive: ausweichend)

Grapheigenschaften heissen monoton, wenn sie bei Einfügung neuer Kanten nicht verlorengehen Beispiel: Hat eine Kante monoton, Hat keine

Kante antimonoton

Grapheigenschaften

Beispiel für nicht schreckliche Grapheigenschaft: Der Einfachheit halber auf gerichteten Graphen.

Ähnlich Tournament:• Akzeptiere, wenn es einen Knoten mit Ingrad n-1 und

Ausgrad 0 gibt, verwerfe sonst Nicht monoton!

Anderaa, Karp, Rosenberg-Vermutung:Alle nichttrivialen, monotonen Grapheigenschaften sind schrecklich

Immer noch offen, aber (n2) ist bewiesen Randomisiert: (n4/3) bewiesen

Property Testing

Wie sind trotzdem schnelle Algorithmen möglich? Weitere Anforderungen an die Eingaben Definition 1.6.:

Ein Graph heisst -weit von einer Eigenschaft entfernt, wenn mindestens n2 Kanten entfernt/eingefügt werden müssen, damit man einen Graphen mit der Eigenschaft erhält Property Testing:

• Alle Graphen mit der Eigenschaft sollen akzeptiert werden

• Alle Graphen, die weit von der Eigenschaft sind, sollen verworfen werden

• Alle anderen Graphen: egal

Property Testing

Property Testing: Alle Graphen mit der Eigenschaft sollen akzeptiert

werden Alle Graphen, die weit von der Eigenschaft sind,

sollen verworfen werden Alle anderen Graphen: egal

Komplexität eines Testers: Anzahl der Fragen/Zeit Im allgemeinen sind Tester randomisiert! Eine Eigenschaft heisst testbar, wenn sie einen Tester

besitzt, der obigen Anforderungen genügt, und der in Zeit f(1/) läuft (mit Erfolgswahrscheinlichkeit 3/4).

Ein Property Tester

Beispiel: Eigenschaft: Hat keine Kante

• Akzeptiere alle Graphen ohne eine Kante• Verwerfe alle Graphen mit n2 Kanten mit hoher

Wahrscheinlichkeit Algorithmus:

• Ziehe 100/ Positionen (i,j) in der Adjazenzmatrix• Teste, ob eine Kante vorhanden• Ja: verwerfe• Nein: Akzeptiere

Klar: Keine Kante vorhanden, dann wird akzeptiert Kanten da, dann werden erwartet (100/)¢ =100

Kanten gefunden Wahrscheinlichkeit, dass dann keine Kante gesehen wird ist

durch kleine Konstante beschränkt [tatsächlich: ] Also ist die Eigenschaft testbar