Rolf Wanka Alexander Raß, Moritz Mühlenthaler Erlangen, 18. April 2016 Übungen zur Vorlesung Randomisierte Algorithmen SS 2016 Blatt 2 AUFGABE 4: Sei H (i) = ∑ik=1 1k die i-te Harmonische Zahl. Zeigen Sie: n−1 n ∑ ∑ i=1 j=i+1 2 = (2n + 2) · H (n) − 4n j−i+1 In der Vorlesung wurde gezeigt, daß dies der Erwartungswert für die Anzahl der Vergleiche ist, die R AND QS beim Sortieren von n Schlüsseln benötigt. Mit der Abschätzung ln(i + 1) ≤ H (i) ≤ ln i + 1 bestimmen Sie einen möglichst kleinen Faktor c, mit dem die obige Summe durch c · n · log2 n abgeschätzt werden kann. AUFGABE 5: Betrachten Sie den folgenden randomisierten Algorithmus: A LGORITHMUS Unbekannt for t := 1 to T do (1) würfle(unabhängig und gleichverteilt (x, y) mit − 12 ≤ x, y ≤ 12 ; 1 falls 4x2 + 4y2 ≤ 1 (2) Xt := 0 sonst done; 4 T gib Z := · ∑ Xt aus; T t=1 (a) Berechnen Sie E[Z]. Hinweis: Welches geometrische Objekt wird durch die ≤-Bedingungen in (1) und welches durch den ≤-Test in (2) beschrieben? (b) Geben Sie in Abhängigkeit von d ∈ IN und δ, 0 < δ < 1, einen möglichst kleinen Wert für T an, so daß gilt: Pr[Z und E[Z] stimmen auf den ersten d Nachkommastellen überein] ≥ 1 − δ Benutzen Sie dazu zwei Ansätze: Wenden Sie zuerst die Tschebyscheffsche Ungleichung an, um T zu bestimmen, dann bestimmen Sie T unter Anwendung der Chernoff-Schranken. (Auf der Rückseite geht es weiter õ) Zur Erinnerung: • Tschebyscheffsche Ungleichung: Sei X eine Zufallsvariable. Für jedes ε > 0 gilt: Pr[|X − E[X]| ≥ ε] ≤ Var[X] . ε2 • Chernoff-Schranke: Seien X1 , . . . , Xn unabhängige 0-1-Zufallsvariablen. Dann gilt für X = ∑ni=1 Xi und E[X] = ∑ni=1 Pr[Xi = 1] und jedes ε, 0 < ε ≤ 1: 2 /4 Pr[|X − E[X]| ≤ ε · E[X]] ≥ 1 − 2e−E[X]ε AUFGABE 6: Beim S AMMELALBUM -P ROBLEM in Aufgabe 3 auf Blatt 1 haben wir ein Experiment kennengelernt, bei dem eine Aktion genau solange unabhängig wiederholt wird, bis sie erfolgreich war. Bezeichne die Zufallsvariable X die Anzahl der durchgeführten Aktionen. Wenn ein einzelner Versuch mit Wahrscheinlichkeit p erfolgreich ist, ist die Anzahl der Aktionen geometrisch verteilt: Pr[X = i] = p · (1 − p)i−1 Berechnen Sie E[X] und Var[X]. AUFGABE 7: In einer Kiste liegen n Bälle mit den eindeutigen Beschriftungen 1, . . . , n. Aus der Kiste werden ohne Zurücklegen k Bälle gezogen. Berechnen Sie den Mittelwert und die Varianz der Summe S der gezogenen Bälle. Welche konkreten Werte kommen bei n = 49 und k = 6 heraus?
© Copyright 2024 ExpyDoc