2 posts tagged with "algorithms"

Oft wird der Nachweis, dass das Halteproblem nicht entscheidbar ist, in der Fachliteratur (Schöning [📖Sch08, 119 f.], Asteroth und Baier [📖BA02, 106 f.], Sipser [📖Sip12, 216 f.]) mithilfe einer Turingmaschine und einem Widerspruchsbeweis gezeigt, in etwa:

Angenommen,

ist entscheidbar.

Sei $T'$ ist die Turingmaschine, die $K'$ entscheidet.
Sei $w = \langle T \rangle$ die Codierung¹ einer Turingmaschine, die wie folgt arbeitet:

• $T$ simuliert das Verhalten von $T'$ bei der Eingabe $w$:
  • $T$ stoppt, wenn $T'$ die Eingabe $w$ verwirft ($w \notin K'$)
  • $T$ stoppt nicht, wenn $T'$ die Eingabe $w$ akzeptiert ($w \in K'$)

Damit folgt: $T$ stoppt bei Eingabe $w$ $\Leftrightarrow$ $T'$ verwirft $w$ $\Leftrightarrow$ $w \notin K'$ $\Leftrightarrow$ $T$ stoppt nicht

Widerspruch!

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, 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, 48]

In der vorliegenden Implementierung (siehe Listing 1) werden $t = log_2(n)$ Inkremente[^1] $h_t$[^2] 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, 91][^3]. In unserem Fall können wir von $O(n^2)$ ausgehen.