Friedhelm Meyer auf der Heide 1 HEINZ NIXDORF INSTITUTE University of Paderborn Algorithms and Complexity Algorithmen und Komplexität Teil 1: Grundlegende

Friedhelm Meyer auf der Heide 1

HEINZ NIXDORF INSTITUTEUniversity of Paderborn

Algorithms and Complexity

Algorithmen und KomplexitätTeil 1: Grundlegende Algorithmen

WS 08/09

Friedhelm Meyer auf der Heide

Vorlesung 11, 18.11.08




Randomisierte Algorithmen



Algorithms and ComplexityBeispiel: Quicksort

Eingabe: S={s1,…,sn} ½ N.

Algo: Falls n=0, gebe leere Folge aus; falls n=1, gebe s1 aus.

Sonst: - erzeuge Splitelement si, i 2 {1,…,n}

- vergleiche jedes sj, ji, mit si, erzeuge dadurch

S1 ={sj, sj < si} und S2 ={sj, sj > si}

- sortiere S1 und S2 rekursiv

- gebe “sortiertes S1”, si , “sortiertes S2” aus.

Laufzeit: Hängt von Schritt 1 (Wahl des Splitelements) ab.

Best case: Splitelement ist immer der Median ! Laufzeit O(n logn)Worst case: Splitelement ist immer das Minimum ! Laufzeit O(n2)Average case: Splitelement ist s1 , Eingabe ist zufällige Permutation ! Durchschnittliche Laufzeit O(n logn)




Ist “durchschnittliche Laufzeit” ein interessantes Kostenmaß?

Beispiel: Quicksort mit s1 als Split-Element.

Absteigend sortierte Folge ist ein schlechtester Fall.

Ist sie eine typische Eingabe?




Ist “durchschnittliche Laufzeit” ein interessantes Kostenmaß?

Bester Fall · Durchschnitt · schlechtester

Fall

Wo liegt der “typische Fall”?

Hängt von Problem und Algorithmus ab, ist meist nicht formal beschreibbar.



Algorithms and ComplexityRandomisierte Algorithmen

Beispiel: Quicksort mit zufälligem si als Split-Element.

Es gibt keine guten oder schlechten Eingaben mehr!!!

Es gibt nur noch gute oder schlechte Ergebnisse der Zufallsexperimente im Algorithmus!

Wir betrachten Algorithmen, die Zufallszahlen benutzen, und davon den Verlauf der Rechnung abhängig machen, sog. probabilistische oder randomisierte Algorithmen.



Algorithms and ComplexityBeispiel: Randomisierter Quicksort

Eingabe: S={s1,…,sn} ½ N.

Algo: Falls n=0, gebe leere Folge aus; falls n=1, gebe s1 aus.

Sonst: - erzeuge zufälliges Splitelement si, i 2 {1,…,n}

- vergleiche jedes sj, ji, mit si, erzeuge dadurch

S1 ={sj, sj < si} und S2 ={sj, sj > si}

- sortiere S1 und S2 rekursiv

- gebe “sortiertes S1”, si , “sortiertes S2” aus.

Laufzeit (Wir messen die Zahl der Vergleiche):Die Laufzeit hängt von der Ergebnissen der Zufallsexperimente ab.

Wir berechnen die erwartete Laufzeit bei zufälliger Wahl der Splitelemente




Erwartete Laufzeit des randomisierten Quicksort

Wir müssen E(Xi,j) berechnen.

Wir müssen pi,j berechnen.





Wann wird S(i) mit S(j) verglichen?

Es gibt nur eine Chance:

Betrachte die Situation, wenn Quicksort für eine Teilmenge S’ aufgerufen wird mit

1. S(i), S(j) 2 S’ (und damit {S(i), S(i+1),…, S(j-1), S(j)} µ S’)

2. Als Splitelement wird ein S(r) gewählt mit i· r · j.

Nur in dieser Situation kann S(i) mit S(j) verglichen werden.

Wann passiert das wirklich?

Genau wenn r=i oder r=j gilt!

Also:











Algorithms and ComplexityEin elementares Beispiel

Best case: 1, worst case: n-k+1

Best case: 1

worst case 1, (tritt mit W’keit 0 ein)

erwartete Zahl von Versuchen: (n-k)/k +1



Algorithms and ComplexityEin elementares Beispiel




Friedhelm Meyer auf der HeideHeinz Nixdorf Institute& Computer Science DepartmentUniversity of PaderbornFürstenallee 1133102 Paderborn, Germany

Tel.: +49 (0) 52 51/60 64 80Fax: +49 (0) 52 51/62 64 82E-Mail: [email protected]://www.upb.de/cs/ag-madh

Thank you for your attention!Thank you for your attention!

Documents

Friedhelm Meyer auf der Heide 1 HEINZ NIXDORF INSTITUTE University of Paderborn Algorithms and Complexity Algorithmen und Komplexität Teil 1: Grundlegende