2 posts tagged with "algorithms"

Die Standardnummerierung ist festgelegt als:

• $\mathbb{N}_0$: Die Menge aller Turingmaschinen (ein $i \in \mathbb{N}_0$ repräsentiert die Gödelnummer einer Turingmaschine), wobei $\mathcal{T}$ die Menge aller normierten Turingmaschinen ist. Die Abbildung $h: \mathbb{N}_0 \rightarrow \mathcal{T}$ ist definiert durch $h(i) = \begin{cases} T, & \text{falls } p(\tau(T)) = i\\ T_{\omega}, & \text{sonst} \end{cases}$ bildet also auf eine natürliche Zahl eine Turingmaschine ab.
• $\mathcal{P}$: Die Menge aller berechenbaren Funktionen.
• $\varphi: \mathbb{N}_0 \rightarrow \mathcal{P}$ ist eine Abzählung aller berechenbaren Funktionen. $\varphi$ ist festgelegt durch $\varphi(i) = f \Leftrightarrow f_{h(i)} = f$ Die berechenbare Funktion $\varphi(i)$ wird also durch die $i$-te Turingmaschine berechnet.

Die Standardnummerierung ist im Folgenden die Grundlage für die Formulierung von Entscheidbarkeitsproblemen bei Mengen.

Das spezielle Halteproblem​

Zunächst wird das spezielle Halteproblem (auch Selbstanwendbarkeitsproblem) betrachtet.
Vossen und Witt definieren es über folgende Menge:

$K$ enthält alle Nummern von Turingmaschinen, die, angewendet auf sich selbst, anhalten:

• $i$ ist die Codierung einer Turingmaschine.
• $\varphi_i$ ist die berechenbare Funktion, die von der Turingmaschine $p(\tau(T)) = i$ berechnet wird.
• $\text{Def}(\varphi_i)$ ist der Definitionsbereich der Funktion $\varphi_i$, also alle erlaubten Eingaben.
• $i \in \text{Def}(\varphi_i)$ bedeutet: Die Codierung $i$ der Turingmaschine $p(\tau(T)) = i$, die $\varphi_i$ berechnet, ist eine erlaubte Eingabe.

Vossen und Witt definieren $K$ als die "Menge aller Turingmaschinen, die, [...] anhalten."
Das bedeutet, dass von einer entscheidbaren Menge ausgegangen wird:
Es wird angenommen, dass sowohl $K$ als auch $\overline{K}$ semi-entscheidbar sind und die charakteristische Funktion $\chi_K$ von $K$ berechenbar ist.

Mit Satz 10.7 formulieren Vossen und Witt den Kern des Selbstanwendbarkeitsproblems, nämlich, dass $K$ zwar semi-entscheidbar, aber nicht entscheidbar ist:

Damit wird behauptet:

• $K$ ist semi-entscheidbar, da rekursiv-aufzählbar.
  Wenn $K$ semi-entscheidbar ist, ist auch die semi-charakteristische Funktion von $K$, $\chi'_K$, berechenbar.
  Wenn $K$ semi-entscheidbar und damit rekursiv aufzählbar ist, dann gilt äquivalent dazu: $K$ ist der Definitionsbereich einer berechenbaren Funktion $g: \mathbb{N}_{0} \rightarrow \mathbb{N}_0$ (s. Folgerung 10.2 [📖VW16, p. 356]). Es reicht also aus, eine solche Funktion anzugeben, um die Semi-Entscheidbarkeit und damit auch die rekursive Aufzählbarkeit nachzuweisen.
• Wenn $K$ entscheidbar ist, dann ist auch die charakteristische Funktion $\chi_K$ berechenbar: $\chi_K$ gibt $1$ aus, wenn die Turingmaschine $T$ angewendet auf $i = p(\tau(T))$ anhält (also wenn $\varphi_i(i)$ berechnet wird); und ansonsten ist $\chi_K(i) = 0$, wenn $T$ nicht anhält².

Beweisführung​

Der Beweis wird wie folgt geführt:

a) Vossen und Witt definieren die Funktion $f: \mathbb{N}_0 \rightarrow \mathbb{N}_0$ durch

Bei $u_{\varphi}$ handelt es sich um die universelle Funktion von $(\mathbb{N}_0, \mathcal{P}, \varphi)$:

$u_{\varphi}(i, j)$ berechnet die $i$-te berechenbare Funktion für die Eingabe $j$.

Mit $f$ als berechenbare Funktion kann gezeigt werden:

womit $K = \text{Def}(f)$ ist und damit $K$ rekursiv-aufzählbar und semi-entscheidbar ist.

b) Angenommen, $K$ ist entscheidbar. Dann ist $\chi_K$ berechenbar.
Vossen und Witt definieren eine berechenbare (Hilfs-)Funktion

$g: \mathbb{N}_0 \rightarrow \mathbb{N}_0$

durch

$g$ ist total berechenbar: Wenn $\chi_K(x) = 1$, dann ist $x \in \text{Def}(\varphi_x)$, und damit ist $u_\varphi(x, x) + 1 = \varphi_x(x) + 1$.

Da $g$ total berechenbar ist ($g \in \mathcal{R} \subset \mathcal{P}$), muss es ein $p \in \mathbb{N}_0$ geben mit $g = \varphi_p$. Es folgt

Für $g(p)$ werden nun zwei Fälle untersucht:

• Fall 1: $g(p) = 0$

  $$\begin{align} g(p) = 0 &\Leftrightarrow \chi_K(p) = 0 \quad \text{(Entscheidbarkeit $K$)}\\ & \Leftrightarrow p \notin K \\ & \Leftrightarrow p \notin \text{Def}(\varphi_p) \quad \text{($g = \varphi_p$)}\\ & \Leftrightarrow p \notin \text{Def}(g) \\ & \Leftrightarrow g(p) = \bot \quad \text{(Widerspruch zu $g$ total berechenbar)} \end{align}$$

  womit insgesamt die widersprüchliche Aussage folgt:

  $$g(p) = 0 \Leftrightarrow g(p) = \bot$$

• Fall 2: $g(p) = u_{\varphi}(p,p) + 1$

  $$\begin{align} g(p) &= u_{\varphi}(p, p) + 1 \quad \text{(Definition $g$)}\\ &= \varphi_p(p) + 1 \quad \text{($u_{\varphi}(p, p) = \varphi_p(p)$)}\\ &= g(p) + 1 \quad \text{($\varphi_p = g$)} \end{align}$$

  womit insgesamt die widersprüchliche Aussage folgt:

  $$g(p) = g(p) + 1$$

Insgesamt wird durch den Beweis gezeigt: Die Anwendung von $g$ auf $p$ - also von $g$ auf sich selbst (wegen $g = \varphi_p = f_{h(p)}, \varphi_p(p) = u_{\varphi}(p, p)$) - führt in jedem Fall zu einem Widerspruch.
Damit ist gezeigt, dass $\chi_K$ nicht berechenbar und folglich $K$ nicht entscheidbar ist.

Donald Shell stellt 1959 in [📖She59] einen Sortieralgorithmus vor, der später nach ihm benannt wird: Shellsort.
Die in dem Algorithmus verwendete Sortiermethode ist auch bekannt als Sortieren mit abnehmenden Inkrementen [📖OW17b, p. 88], das Verfahren ist eine Variation von Insertion Sort:

[Shellsort] uses insertion sort on periodic subarrays of the input to produce a faster sorting algorithm. [📖CL22, p. 48]

In der vorliegenden Implementierung (siehe Listing 1) werden $t = log_2(n)$ Inkremente¹ $h_t$² der Form $\lfloor {\frac{n}{2^i}} \rfloor$ verwendet, um $lg(n)$ $h$-sortierte Folgen zu erzeugen. Im letzten Schritt sortiert der Algorithmus dann in $h_1$ die Schlüssel mit Abstand=$1$.

Die Effizienz des Sortierverfahrens ist stark abhängig von $h$: So zeigt Knuth, dass $O(n^{\frac{3}{2}})$ gilt, wenn für $h$ gilt: $h_s = 2^{s+1} - 1$ mit $0 \leq s < t = \lfloor{lg(n)} \rfloor$ (vgl. [📖Knu97c, p. 91]³. In unserem Fall können wir von $O(n^2)$ ausgehen.

Anzahl der Aufrufe für Feldvergleiche​

Gesucht ist die Anzahl der zwischen zwei Feldelementen gemachte Vergleiche für große randomisierte Felder. Wir vermuten hierfür einen Wert zwischen $O(n\ lg\ n)$ und $O(n^2)$,

Um die Aufrufe der Feldvergleiche zu zählen, kann wie in Listing 1 eine Zählvariable $c3$ eingesetzt wird, die jeden Aufruf über ein increment protokolliert.

while (distanz > 0) {
    c1++;
    for (i = distanz; i < feld.length; i++) {
        j = i - distanz;
        c2++;
        while (j >= 0) {
            c3++;
            if (feld[j] > feld[j + distanz]) {
                c4++;
                swap(feld, j, j+distanz);
                j = j - distanz;
            } else {
                j =-1;
            }
        }
    }
    distanz = distanz / 2;
}

Zur Bestimmung von $c3$ können randomisierte Felder erzeugt werden, wie es der Test-Code in Listing 2 demonstriert. Dann wird überprüft, in welchen Bereichen sich $c3$ bewegt. Da jeder auf Vergleichsoperationen basierende Sortieralgorithmus zu der Laufzeitklasse $\Omega(n\ log\ n)$ gehört, kann im Mittel $c3 \geq n\ log\ n$ angenommen werden:

Jedes allgemeine Sortierverfahren benötigt zum Sortieren von N verschiedenen Schlüsseln sowohl im schlechtesten Fall als auch im Mittel wenigstens $\Omega(N\ log\ N)$ Schlüsselvergleiche.

[📖OW17b, p. 154]

Allerdings wird $n^{1.3}$ ab $n=982$ schneller wachsen als $n\ log\ n$ (siehe Abbildung 1), was in der Auswertung berücksichtigt werden muss. Sonst könnte man fälschlicherweise folgern, das in dem geg. Fall die Laufzeit im Durchschnitt $n\ log\ n$ beträgt.

int epochs = 2000;
while(epochs-- >= 0) {
    int[] tests = new int[]{10, 100, 1000, 100_000, 1_000_000};
    java.util.Random r = new java.util.Random();
    for (int i = 0; i < tests.length; i++) {
        int l = tests[i];
        int[] arr = new int[l];

        for (int j = l; j > 0; j--) {
            arr[l - j] = r.nextInt(l + 1);
        }

        ShellSort.sort(Arrays.copyOfRange(arr, 0, arr.length));
    }
}

^{Figure 1 Ab n=982 wächst n(4/3) schneller al n log n.}

Wegen $\Omega(n\ log\ n)$ interessieren wir uns für die Intervalle:

• $n\ log\ n \leq c3 \leq n^{1.3}$

• $n\ log\ n \leq n^{1.3} \leq c3 \leq n^2$

Die Ausführung des Tests zeigt, dass die Aufrufanzahl von $c3$ bei großen $n$ unterhalb $n^{1.3}$ oder zwischen $n^{1.3}$ und $n^2$ liegt:

It appears that the time required to sort $n$ elements is proportional to $n^{1.226}$.⁴ [📖She59, p. 31]

Laufzeitanalyse​

Für die nachfolgenden Betrachtungen sei eine Eingabegröße $n = 2^p$ gegeben. Die Inkremente $h$ entsprechen der über die Implementierung vorgegebenen Folge $h$ mit

Für die Analyse ist die Shellsort-Implementierung in Listing 3 gegeben.

public static int[] sort(int[] arr) {

    int n = arr.length;
    int delta = n/2;
    int min;
    int j;

    while (delta > 0) { // c1

        for (int i = delta; i < arr.length; i++) {

            // c2

            min = arr[i];
            j = i;

            while (j - delta >= 0 && min < arr[j - delta]) {

                // c3;

                arr[j] = arr[j - delta];
                j -= delta;
            }
            arr[j] = min;
        }

        delta = delta / 2;

    }
    return arr;
}

Im Folgenden betrachten wir die Anzahl für die im Code durch Kommentare markierten Stellen $c1$ in Zeile 8, $c2$ in Zeile 12 und $c3$ in Zeile 19.

Für eine erste worst-case-Analyse ist ein Feld der Länge $16$ gegeben, in absteigender Reihenfolge sortiert (s. Abbildung 2):

^{Figure 2 Die für die Laufzeitabschätzung verwendete Eingabefolge 16..1.}

Ganz offensichtlich gilt für c3, dass es $lg(n)$-mal aufgerufen wird⁵. c2 befindet sich im Block der durch die in Zeile 11 definierten Zählschleife.

Der Startwert für i ist in jedem Durchgang des Blocks $c1$ der aktuelle Wert von delta ⁶, und läuft jeweils bis $n - 1$.

In einem kompletten Durchlauf der Schleife entspricht die Anzahl der Aufrufe von $c2$ also

Für die Gesamtzahl der Aufrufe von $c2$ ergibt sich somit unter Berücksichtigung von $c1$

entspricht, und für unser Beispiel

ist.

In der while-Schleife in Zeile 17 findet die eigentliche Arbeit des Algorithmus statt: Es wird überprüft, ob $delta$-entfernte Elemente in aufsteigender Reihenfolge sortiert angeordnet sind.

Ist das nicht der Fall, werden die Elemente an den Stellen $j$ und $j - delta$ ausgetauscht, bis die $h$-Folge sortiert ist.
Für den ersten Durchgang des Algorithmus an dieser Stelle mit $h_4 = 8$ ergibt sich somit die in Abbildung 3 dargestellte Reihenfolge der Schlüssel:

^{Figure 3 Nach dem ersten Durchgang sind die Schlüssel in den Abständen h₄ = 8 sortiert, es ergeben sich zwei sortierte Teilfolgen der Länge 8.}

Die weiteren Durchgänge des Algorithmus sortieren das Feld entsprechend der Größe $h$: Es sind danach jeweils Schlüssel mit den Abständen $4$ (Abbildung 4 und $2$ (Abbildung 5) sortiert; im letzten Schritt dann vollständig (Abbildung 6):

^{Figure 4 Die Sortierung für h₃ = 4, es sind 4 Folgen deren Schlüssel jeweils den Abstand 4 zueinander haben.}

^{Figure 5 Im vorletzten Sortierschritt sind 8 Folgen der Länge 2 sortiert.}

^{Figure 6 Der letzte Durchgang des Algorithmus vergleicht Schlüssel mit Distanzfolgen der Länge 1, also direkt benachbarte Schlüssel.}

Für die Berechnung der Anzahl der Aufrufe von $c3$ stellt man fest, das in diesem Fall in jedem Schritt immer 2 Elemente, die eine Distanz von $h_s$ aufweisen, falsch sortiert sind.

Der Algorithmus tauscht daraufhin in jedem Durchgang alle Schlüssel untereinander aus, die er über min < arr[j-delta] miteinander vergleicht, was folglich die maximale Anzahl von Schlüsselvertauschungen in dieser vergleichsbasierten Implementierung für ein Feld der Größe $n$ ergibt, nämlich $\frac{n}{2}$. Insgesamt finden dadurch für $c3$

Aufrufe statt.

Mit der Anzahl der berechneten Aufrufe $c1, c2, c3$ ergibt sich somit für die Laufzeit $T(n)$ für diesen Fall

und zusammengefasst

was nach Einsetzen zu

Aufrufen für unser Beispiel führt.

Nachweis der Komplexitätsklasse​

Um $O$ zu ermitteln, werden nun alle Konstanten der Funktion

eliminiert, und der "dominante" Summand in Abhängigkeit von $n$ betrachtet, der in diesem Fall $lg(n) * n$ ist.

Wir vermuten ein $N-log-N$-Wachstum⁷ (vgl. [📖OW17a, p. 5]), und wollen nun zeigen, dass $T(n)$ in $O(n\ log\ n)$ liegt.
Hierfür müssen wir ein geeignetes $c$ und ein $n_0$ finden, so dass gilt:

(vgl. [📖GD18a, p. 11]).

Zu zeigen ist

Wir wählen für $n_0 = 1$ und $c = \frac{3}{2}$, denn es gilt sicher

Ausserdem gilt stets $\forall n \in \mathbb{N}: lg(n) < n$, woraus $lg(n) - n < 0$ folgt, und damit auch $lg(n) - n + 1 \leq 0$.

Insgesamt gilt also

womit $f = O(n * log(n))$ gezeigt ist. ◻

Worst-Case-Analyse​

Unter der Annahme, dass ein in umgekehrter Reihenfolge sortiertes Feld zu einer Laufzeit von $O(n^2)$ bei dem Shellsort-Algorithmus führt, konnten wir mit dem in dem vorherigen Abschnitt gewählten Parametern nur eine Laufzeit von $O(n\ log\ n)$ nachweisen.
Tatsächlich stellt der Anwendungsfall nicht den worst-case für den Algorithmus dar, da ja gerade diese Form von Sortierreihenfolge dem Algorithmus die Vorsortierung der $h$-Folgen ermöglicht:

The idea underlying Shellsort is that moving elements of A long distances at each swap in the early stages, then shorter distances later, may reduce this $O(n^2)$ bound. [📖Pra72, p. 3]

Es gilt also, die Vorsortierung auszuhebeln.
Für Insertion-Sort ist die Laufzeit im worst-case $O(n^2)$ (vgl. [📖OW17b, p. 87]). Da Shellsort mindestens im letzten Schritt diese Sortiermethode auf Distanzfolgen der Länge $1$ anwendet, muss der Algorithmus eine Folge als Eingabe erhalten, die durch die ersten $lg(n) - 1$-Durchgänge (mit $h_s = 2^{s - 1}, 1 \leq s < lg(n)$) keine Änderungen erfährt, um dann im allerletzten Schritt auf einen Schlag sortiert wird, was maximal $\frac{n}{2}$ Inversionen⁸ bedeutet, und damit ebenso viele Vertauschungen (zuzüglich der benötigten Verschiebe-Operationen).
Hierzu kann wie im vorherigen Beispiel für $n=16$ ein Feld mit folgender Schlüsselanordnung verwendet werden: Felder mit geradem Index enthalten kleinere Schlüssel als Felder mit ungeradem Index. Hier gilt für alle Elemente aus dem Feld $A$:

Abbildung 7 veranschaulicht die Anordnung.

^{Figure 7 Eine worst-case Schlüsselfolge für Shellsort. Felder mit geradem Index enthalten kleinere Schlüssel als Felder mit ungeradem Index.}

Markiert sind die direkt benachbarten Felder, die eine Inversion aufweisen, die im letzten Schritt des Algorithmus eine bzw. mehrere Verschiebungen bedingen.
In den vorherigen Schritten - also bei den Durchgängen mit Distanzfolgen $h_s > 1$ - findet der Algorithmus jeweils Schlüssel in korrekter Sortierreihenfolge vor.

Mit $h_4 = 8$ werden die Felder $A[0..7]$ mit den Feldern $A[8..15]$ verglichen - hier gilt in jedem Fall, dass die Schlüssel $A[i] < A[j] (\forall i < j, j - i = 8)$ sind.

Auch im darauffolgenden Durchgang ($h_3 = 4, j - i = 4$) finden keine Verschiebungen statt, da keine Inversion gefunden wird. Erst im letzten Schritt, in dem direkt benachbarte Elemente miteinander verglichen werden, werden die Inversionen ermittelt und die Verschiebung der Elemente findet statt (s. Abbildung 8.

^{Figure 8 Für die worst-case Schlüsselfolge werden im letzten Schritt 7 Inversionen festgestellt. Jede dieser Fehlstellung bedingt eine Verschiebung um die angegebene Anzahl von Positionen.}

In diesem Fall wird $c3$ insgesamt $32$ mal aufgerufen.

Da jeweils zwei Schlüssel bereits korrekt sortiert sind ($A[0]$ und $A[n-1]$) existieren noch $\frac{n}{2} - 1$ Inversionen. Jede Inversion erzwingt eine Verschiebung des größten Elements um $\frac{i}{2}$ Positionen nach links.

Für die Berechnung der Laufzeitkomplexität ergibt sich somit der Term

und unter Berücksichtigung der Terme für $c1$, $c2$, $c3$ die Funktion

was zu einer Laufzeitabschätzung von $O(n^2)$ führt.