5  Blatt 6

Aufgabe 1 - Radix Sort

1. Zuerst definieren wir folgende Python Funktion fuer Konvertierung die zahl x von Basis 10 auf basis base:

def convert(x, base) :
    if x == 0: return '0'
    s = []
    while (x > 0) :
        s.insert(0, str(x % base))
        x = x // base
    return "".join(s)

und konvertieren die Zahlen in \(A\) anhand dieser Funktion auf Basis 7:

A = [147, 44, 337, 528, 45, 622]
[convert(x, 7) for x in A]

['300', '62', '661', '1353', '63', '1546']

Wir sehen, dass die Zahlen hoechstens aus 4 Ziffern bestehen. Somit \(d = 4\).

2. Jetzt geben wir die folgende Python implementierung fuer KSort7() an, die Schluessel im Bereich \([0, 7)\) sortiert. Die Funktion erhaelt einen zusaetzlichen funktionalen Paremeter, dadurch die key() Funktion bestimmt wird. Beachte, dass danach die Elemente in Buckets hinzugefuegt werden der Zustand von Buckets ausgegeben wird. Am Ende werden die Buckets konkateniert und das Ergebniss zurueckgegeben

# sorts keys in range [0, 7)
def KSort7(s, key) :
    # initialize array with 7 empty buckets
    b = []
    for i in range(7) : b.append([])
    # insert elements into buckets
    for el in s : b[key(el)].append(el)
    # print state of the buckets
    for i in range(7) :
        print("bucket ", i, ": ", list(map(str, [convert(x, 7) for x in b[i]])))
    # declare array holding results
    res = []
    # append elements in buckets to res
    for i in range(7) :
        for el in b[i] : res.append(el)
    return res

Nun definieren die LSDRadixSort7() Funktion, die den Radix Sort algorithmus fuer Basis 7 anhand KSort7() implementiert.

def LSDRadixSort7(a) :
    for i in range(4) :
        print("d == ", i)
        a = KSort7(a, lambda x : (x // 7**i) % 7)
        print("")
    return a

Am Ende jeder Iteration wird der Zustand von den Buckets anhand KSort7() ausgegeben. Wir rufen die Funktion auf \(A\) auf und konvertieren das Ergebniss zu Basis 7:

[convert(x, 7) for x in LSDRadixSort7(A)]

d ==  0
bucket  0 :  ['300']
bucket  1 :  ['661']
bucket  2 :  ['62']
bucket  3 :  ['1353', '63']
bucket  4 :  []
bucket  5 :  []
bucket  6 :  ['1546']

d ==  1
bucket  0 :  ['300']
bucket  1 :  []
bucket  2 :  []
bucket  3 :  []
bucket  4 :  ['1546']
bucket  5 :  ['1353']
bucket  6 :  ['661', '62', '63']

d ==  2
bucket  0 :  ['62', '63']
bucket  1 :  []
bucket  2 :  []
bucket  3 :  ['300', '1353']
bucket  4 :  []
bucket  5 :  ['1546']
bucket  6 :  ['661']

d ==  3
bucket  0 :  ['62', '63', '300', '661']
bucket  1 :  ['1353', '1546']
bucket  2 :  []
bucket  3 :  []
bucket  4 :  []
bucket  5 :  []
bucket  6 :  []

['62', '63', '300', '661', '1353', '1546']

Aufgabe 2 - Pivotwahl

1. Ziehen mit Zuruecklegen \(\Rightarrow |\Omega| = \binom{n + 5 - 1}{5} = \binom{n + 4}{5}\). Fuer ein beliebiges Ergebniss des Experiments ist die Riehenfolge und somit das mittlere Element fixiert, z.B. \(i\).

• Fuer die kleineren 2 Elemente waehlt man aus der Menge \(\{1,\dots, i\}\) mit Zuruecklegen: \(\binom{i + 2 - 1}{2} = \binom{i + 1}{2}\)
• Fuer die groesseren 2 Elemente waehlt man aus der Menge \(\{i,\dots, n\}\) mit Zuruecklegen: \(\binom{n - i + 1 + 2 - 1}{2} = \binom{n - i + 2}{2}\)

Diese Waehle sind unabhaengig und fuer den beschriebenen Ereigniss laeuft \(i\) von \(n/4 + 1\) bis \(3n/4 - 1\). Somit: \[ |E| = \sum_{i = n/4 + 1}^{3n/4 - 1}\binom{i + 1}{2}\binom{n - i + 2}{2} \].

Dann die gesuchte Wahrsceinnlichkeit:

\[\begin{align*} p_n &= \frac{|E|}{|\Omega|} \\ &= \frac{\sum_{i = n/4 + 1}^{3n/4 - 1}\binom{i + 1}{2}\binom{n - i + 2}{2}}{\binom{n + 4}{5}} \end{align*}\]

Wir koennten diese Formel nicht weiter algebraisch vereinfachen. Das Software fuer symbolische Mathematik Mathematica™ lieferte den Ausdruck

\[ p_n = \frac{203 n^4+744 n^3+592 n^2-384 n}{256 n (n+1) (n+3) (n+4)} \]

Fuer \(n=100\) ist diese Wahrscheinlichkeit \(p_{100} \approx 0.77\)

2. Wahrscheinlichkeit eines Misserfolgs: \(1 - p_n\). Der beschriebene Vorgang entspricht einer geometrischen Verteilung mit \(p = 1 - p_n\). Der Erwartungswert einer geometrischen Verteilung ist gegeben als:

\[ \mu = \frac{1}{p} = \frac{1}{1 - p_n} \]

Fuer \(n = 100\) \(\mu \approx \frac{1}{1 - 0.77} \approx 4.4\)