BuK/IIm14/Studenten/s3tomack

Wiki-Quelltext dieser Seite.

== Übungsaufgaben ==

Dieses Kapitel enthält die Übungsaufgaben geordnet nach den Vorlesungen.

=== Vorlesung 1: Vorbereitungen ===

=== Vorlesung 2: Berechenbarkeitsbegriff ===

==== abzählbar unendliche Mengen ====

Zeigen Sie, dass die folgenden Mengen abzählbar
unendlich sind: $\Z, \Q$, die Menge der Primzahlen, die geraden Zahlen.

'''Für $\Z$:'''

z.z.: Die Menge $\Z$ ist abzählbar unendlich.
* abzählbar, d.h. $\exists f : \N \rightarrow \Z | \text{ bijektiv }$
{| border="1" cellpadding="5" cellspacing="0"
|-
|| $\N$ || 0 || 1 || 2 || 3 || 4 || 5 || 6 || ...
|-
|| $\Z$ || 0 || -1 || 1 || -2 || 2 || -3 || 3 || ...
|-
|}
$$f(n) = \begin{cases}
\frac{n}{2}, & \text{wenn } n \text{ gerade}\\
-\left(\frac{n+1}{2}\right), & \text{wenn } n \text{ ungerade}\\
\end{cases}$$

'''Für $\Q$:'''

z.z.: Die Menge $\Q$ ist abzählbar unendlich.
* abzählbar, d.h. $\exists f : \N \rightarrow \Q | \text{ bijektiv }$
* Elemente von $\Q$ sind darstellbar durch: $\frac{p}{q} | q \neq 0 \text{ und } p, q \in \Z$
{| border="1" cellpadding="5" cellspacing="0"
|-
|| $p / q$ || -1 || 1 || -2 || 2 || -3 || 3 || -4 || 4 || -5 || 5 || $\ldots$
|-
|| 1 || $\frac{-1}{1}$ || $\frac{1}{1}$ || $\frac{-2}{1}$ || $\frac{2}{1}$ || $\frac{-3}{1}$ || $\frac{3}{1}$ || $\frac{-4}{1}$ || $\frac{4}{1}$ || $\frac{-5}{1}$ || $\frac{5}{1}$ || $\ldots$
|-
|| 2 || $\frac{-1}{2}$ || $\frac{1}{2}$ || $\frac{-2}{2}$ || $\frac{2}{2}$ || $\frac{-3}{2}$ || $\frac{3}{2}$ || $\frac{-4}{2}$ || $\frac{4}{2}$ || $\frac{-5}{2}$ || $\frac{5}{2}$ || $\ldots$
|-
|| 3 || $\frac{-1}{3}$ || $\frac{1}{3}$ || $\frac{-2}{3}$ || $\frac{2}{3}$ || $\frac{-3}{3}$ || $\frac{3}{3}$ || $\frac{-4}{3}$ || $\frac{4}{3}$ || $\frac{-5}{3}$ || $\frac{5}{3}$ || $\ldots$
|-
|| 4 || $\frac{-1}{4}$ || $\frac{1}{4}$ || $\frac{-2}{4}$ || $\frac{2}{4}$ || $\frac{-3}{4}$ || $\frac{3}{4}$ || $\frac{-4}{4}$ || $\frac{4}{4}$ || $\frac{-5}{4}$ || $\frac{5}{4}$ || $\ldots$
|-
|| 5 || $\frac{-1}{5}$ || $\frac{1}{5}$ || $\frac{-2}{5}$ || $\frac{2}{5}$ || $\frac{-3}{5}$ || $\frac{3}{5}$ || $\frac{-4}{5}$ || $\frac{4}{5}$ || $\frac{-5}{5}$ || $\frac{5}{5}$ || $\ldots$
|-
|| $\vdots$ || $\vdots$ || $\vdots$ || $\vdots$ || $\vdots$ || $\vdots$ || $\vdots$ || $\vdots$ || $\vdots$ || $\vdots$ || $\vdots$ || $\ddots$
|-
|}

Unter Zuhilfenahme des Cantorschen Diagonalisierungsverfahren 1. Art lassen sich alle Elemente erreichen.

'''Für die Menge der Primzahlen $P$:'''

z.z.: Die Menge $P$ ist abzählbar unendlich.
* abzählbar, d.h. $\exists f : \N \rightarrow P | \text{ bijektiv }$
* Die Menge der Primzahlen $P$ ist nach dem Satz von Euklid unendlich.
* Die Menge der Primzahlen $P$ ist abzählbar, da gilt $P \subset \N$ (nach Definition der Primzahlen).

'''Für die Menge der geraden Zahlen $G$:'''

z.z.: Die Menge $P$ ist abzählbar unendlich.
* abzählbar, d.h. $\exists f : \N \rightarrow G | \text{ bijektiv }$ 
* Die Menge der geraden Zahlen $G$ ist abzählbar, da gilt $G \subset \Z$.
$$f(n)=2n$$

=== Vorlesung 3: Entscheidbarkeit und Aufzählbarkeit ===

=== Vorlesung 4: Sätze und Zusammenhänge <WIP> ===

==== Aufzählbarkeit und Semi-Entscheidbarkeit ====

 Satz 1: Eine Menge $M$ ist genau dann ''aufzählbar'', wenn sie ''semi-entscheidbar'' ist.

z.z.:
*Wenn $M$ aufzählbar ist, dann ist $M$ semi-entscheidbar. (Teil 1)
*Wenn $M$ semi-entscheidbar ist, dann ist $M$  aufzählbar. (Teil 2)

Teil 1:
<blockquote>
Gegeben ist eine aufzählbare Menge $M$. Hieraus folgt, es gibt eine Aufzählprozedur $f_M$ für $M$, die die Menge der natülichen Zahlen $\N$ surjektiv auf $M$ abbildet: $f:\N \mapsto M$.<br/><br/>

Semi-entscheidbar ist eine Menge $M$, wenn ihre semi-charakteristische Funtion $\chi'_M:A^*\mapsto\{wahr\}$ berechenbar ist, also wenn es eine Prozedur gibt die $wahr$ zurückgibt, falls ein übergebenens Wort $w$ ein Element von $A^*$ ist und ansonsten ewig weiter läuft.
$$\chi'_M(w)=
\begin{cases}
wahr, & \quad \text{wenn } w \in M\\
\bot, & \quad \text{sonst}
\end{cases}$$
Unter Verwendung der Aufzählprozedur $f_M$ kann entschieden werden, ob ein übergebenen Wort $w \in A^*$ ein Element von $M$ ist. Hierbei wird $f_M$ der Reihe nach für jedes $i \mid i \in \N$ aufgerufen ($f_M(0),f_M(1),f_M(2),f_M(3),\ldots$). Ist dabei $f_M(i) = w$, gibt $\chi'_M wahr$ zurück, andernfalls läuft die Prozedur ewig weiter, d.h. nach Definition ist $M$ semi-entscheidbar.
$$\chi'_M(w)=
\begin{cases}
wahr, & \quad \text{wenn } f_M(i)=w \mid i \in \N\\
\bot, & \quad \text{sonst}
\end{cases}$$
</blockquote>
Teil2:
<blockquote>
Gegeben ist eine semi-entscheidbare Menge $M$. Somit steht eine partiell berechenbare Funktion $\chi'_M:A^*\mapsto\{wahr\}$ zur Verfügung.<br/><br/>
Gesucht ist eine surjektive, total berechenbare Aufzählfunktion: $f_M:\N\mapsto M$.<br/>
Problem: Ob für ein beliebiges Wort $w \in A^*$ entweder $w \in M$ oder $w \notin M$ gilt, kann nur mit <tt>chi-strich</tt> ermittelt werden. Zur Berechung von $f_M(i)$, nimmt man das $i$-te Element aus A^* (aufzählbare Menge) und berechnet $\chi'_M(w_i)$. Falls das Ergebnis $wahr$ ist, terminiert $\chi'_M(w_i)$, andernfalls läuft die Funktion ewig weiter.<br/>
Gegenmaßnahme: bijektive, total berechenbare Paarungsfunktion $\pi:\N\times\N\mapsto\N$<br/>
Cantorsche Paarungsfunktion: $$\pi(x,y)=\sum_{i=0}^{x+y}i+y$$
Unter der Verwendung von $\chi'_M(w_x)$ mit der Aufzählprozedur $g(x) = w_x$ für $A^*$ und $z = \pi(x,y)$ kann $f_M$ nun folgendermaßen definiert werden:
$$f_M(z)=\begin{cases}
g(x), & \quad \text{wenn } \chi'_M(g(x))[= wahr] \text{ innerhalb von } y \text{ Zeiteinheiten}\\
a, & \quad \text{wenn Proz. für } \chi'_M(g(x)) \text{ innerhalb von } y \text{ Zeiteinheiten ohne Ergebnis}\\
\end{cases} \mid M \neq \emptyset, a \in M, z \in \N$$

</blockquote>

----

Vervollständigen Sie die Herleitung der Funktionen für $x$ und $y$ aus $z = \pi(x, y)$.
<blockquote>
$z=\frac{(x+y)(x+y+1)}{2}+y=t+y$<br/>
$w=x+y$<br/>
$t,x,y,z,w \in \N$<br/><br/>
$t=z-y=\frac{w(w+1)}{2}=\frac{w^2+w}{2}$<br/>
Lösung von $w^2+w-2t=0$:<br/>
allgemeine Form: $w^2+pw-q=0$<br/>
pq-Formel: $w_{1,2}=-\frac{p}{2}\pm\sqrt{\left(\frac{p}{2}\right)^2-q}$<br/>
$w_{1,2}=-\frac{1}{2}\pm\sqrt{\left(\frac{1}{2}\right)^2+2t}$<br/>
$w_{1,2}=-\frac{1}{2}\pm\sqrt{\frac{1}{4}+\frac{8t}{4}}$<br/>
$w_{1,2}=-\frac{1}{2}\pm\sqrt{\frac{8t+1}{4}}$<br/>
$w_{1,2}=-\frac{1}{2}\pm\frac{\sqrt{8t+1}}{2}$<br/>
Für positive $w$ ergibt sich $w_1$:<br/>
$w_1=-\frac{1}{2}+\frac{\sqrt{8t+1}}{2}$<br/>
$w_1=\frac{\sqrt{8t+1}-1}{2}$<br/><br/>
Außerdem gilt:<br/>
$t \leq z, \text{ da } z = t + y$<br/>
$z = t + w - x, \text{ da } z = t + y \text{ und } y = w - x$<br/>
$z \leq t + w < t + w + 1$<br/>
$t + w + 1 = \frac{w^2 + w}{2} + w +1 = \frac{w^2+w+2x+2}{2} = \frac{(w^2+2x+1)+(w+1)}{2} = \frac{(w+1)^2+(w+1)}{2}$<br/>
$z < \frac{(w+1)^2+(w+1)}{2}$<br/><br/>
Unter Verwendung von $z < \frac{(w+1)^2+(w+1)}{2}$ können wir $w$ nach oben
abschätzen:<br/>
$w = \frac{\sqrt{8t + 1} - 1}{2} \leq \frac{\sqrt{8z + 1} - 1}{2} < w + 1$
Für $z$ wird $\frac{(w+1)^2+(w+1)}{2}$ eingesetz:<br/>
$\frac{\sqrt{8\left(\frac{(w+1)^2+(w+1)}{2}\right) + 1} - 1}{2}$<br/>
$\frac{\sqrt{8\left(\frac{w^2+3w+2}{2}\right) + 1} - 1}{2}$<br/>
$\frac{\sqrt{\left(\frac{8w^2+24w+16}{2}\right) + 1} - 1}{2}$<br/>
$\frac{\sqrt{4w^2+12w+9} - 1}{2}$<br/>
$\frac{\sqrt{(2w+3)^2} - 1}{2}$<br/>
$\frac{2w+2}{2}=w+1$<br/>
Daher ergibt sich $w=\lfloor \frac{\sqrt{8z + 1} - 1}{2} \rfloor \in \N$<br/><br/>
Um die beiden natürlichen Zahlen $x$ und $y$ aus $z$ zu gewinnen, ist als erstes $w=\lfloor \frac{\sqrt{8z + 1} - 1}{2} \rfloor$ zu berechnen.<br/>
Danach ergeben sich:<br/>
$t = \frac{w (w + 1)}{2}$<br/>
$y = z - t$<br/>
$x = w - y$<br/>
</blockquote>

----

Geben Sie als Beispiel die Ermittlung von $x$ und $y$ aus $z = \pi(1, 3) = 13$ an:

$w = \lfloor \frac{\sqrt{8z + 1} - 1}{2} \rfloor = \lfloor \frac{\sqrt{8 * 13 + 1} - 1}{2} \rfloor = \lfloor 4,6235 \rfloor = 4$<br/>
$t = \frac{w (w + 1)}{2} = \frac{4 (4 + 1)}{2} = \frac{20}{2} = 10$<br/>
$y = z - t = 13 - 10 = \underline{3}$<br/>
$x = w - y = 4 - 3 = \underline{1}$<br/>

==== Abzählbarkeit vs. Aufzählbarkeit ====

 Satz 2: Jede Teilmenge einer ''abzählbaren'' Menge ist ''abzählbar'', aber nicht jede Teilmenge einer ''aufzählbaren'' Menge ist ''aufzählbar''.

z.z.:
*Wenn $M_1$ eine abzählbare Menge ist, dann ist jede Teilmenge $M_2 \subseteq M_1$ abzählbar. (Teil 1)
*Wenn $M_1$ eine aufzählbare Menge ist, dann sind nicht alle Teilmengen $M_2 \subseteq M_1$ aufzählbar. (Teil2)
Teil 1:
<blockquote>
Gegeben ist eine bijektive Funktion $f_1 : \N \mapsto M_1$, da $M_1$ abzählbar ist.<br/>
Es ist zu zeigen , dass die Abzählbarkeit von $M_2$ daraus folgt.
Gesucht ist also mindestens eine surjektive Funktion $f_2 : \N \mapsto M_2$ für eine beliebige Teilmenge $M_2$. Man gewinnt $f_2$ aus $f_1$:
$$f_2(n)=\begin{cases}
f_1(n), & \quad \text{wenn } f_1(n)\in M_2\\
a, & \quad \text{sonst}\\
\end{cases} \mid M_2 \neq \emptyset, a \in M_2$$
</blockquote>
Teil 2:
<blockquote>
<tt>Annahme:</tt> Für eine aufzählbare Menge $M_1$ sind alle Teilmengen $M_2 \subseteq M_1$ aufzählbar.<br/>
Laut dieser Annahme ist die Menge $M_2$ aufzählbar, darausfolgt das $M_2$ semi-entscheidbar ist.<br/>
Gegeben ist eine surjektive, berechenbare Funktion $f_1 : \N \mapsto M_1$, da laut Voraussetzung die Menge $M_1$ aufzählbar ist. Laut der Annahmen existiert auch eine surjektive, berechenbare Funktion $f_2 : \N \mapsto M_2$. Die Funktion $f_2$ kann unter Verwendung von $f_1$ definiert werden:
$$f_2(n)=\begin{cases}
f_1(n), & \quad \text{wenn } f_1(n)\in M_2\\
a, & \quad \text{wenn } f_1(n)\in M_1 \backslash M_2\\
\end{cases} \mid a \in M_2$$
Damit $f_2$ berechenbar ist, muss die charakteristische Funktion $\chi_{M_2,M_1} : M_2 \mapsto \{wahr, falsch\}$ berechenbar sein.
$$\chi_{M_2,M_1}(w)=\begin{cases}
wahr, & \quad \text{wenn } f_1(n)\in M_2\\
falsch, & \quad \text{wenn } f_1(n)\in M_1 \backslash M_2\\
\end{cases}$$
Aus der Berechenbarkeit von $\chi_{M_2,M_1}(w)$ folgt, das $M_2$ entscheidbar ist. Dies steht im Widerspruch zu der aus der Annahme resultierenden Semi-Entscheidbarkeit. Folglich ist die Annahme falsch und der Satz korrekt.
</blockquote>

==== Entscheidbarkeit und Aufzählbarkeit <WIP> ====

 Satz 3: Wenn die Menge $M$ ''entscheidbar'' ist, dann ist $M$ ''aufzählbar''.

*Laut Voraussetzung ist $M$ entscheidbar, daraus folgt das $M$ auch semi-entscheidbar ist.
*In Satz 1 wurde bewiesen das semi-entscheidbare Mengen aufzählbar sind, daraus folgt die entscheidbare Menge $M$ ist auch aufzählbar.

 Satz 4: Eine Menge $M$, mit $M \subseteq A^*$, ist ''entscheidbar'' genau dann, wenn $M$ und $A^* \ M$ (Komplementmenge) ''aufzählbare'' Mengen sind.

z.z.: 
*Wenn $M$ eine entscheidbare Menge ist, dann sind $M$ und $A^*\backslash M$ aufzählbare Mengen. (Teil 1)
*Wenn $M$ und $A^*\backslash M$ aufzählbare Mengen sind, dann ist $M$ eine entscheidbare Menge. (Teil 2)

Teil 1
<blockquote>
Da $M$ laut Voraussetzung eine entscheidbare Menge ist, muss die charakteristische Funktion $\chi_{M,A^*}:A^* \mapsto \{wahr, falsch\}$ berechenbar sein. Da $A^*$ eine aufzählbare Menge ist, muss es eine Aufzählprozedur $f_{A^*}:\N\mapsto A^*$ für $A^*$ geben.<br/>
<tt>Gegeben:</tt>
$$\chi_{M,A^*}(w)=\begin{cases}
wahr, & \quad \text{wenn } w \in M\\
falsch, & \quad \text{wenn } w \in A^*\backslash M\\
\end{cases}$$
<tt>Gesucht:</tt>
\begin{align}
f_M & :\N\mapsto M & \mid surjektiv, berechenbar\\
f_{A^*\backslash M} & :\N\mapsto A^*\backslash M  & \mid surjektiv, berechenbar
\end{align}
Unter der Verwendung der Funktion $\chi_{M,A^*}(w)$ und der Aufzählprozedur $f_{A^*}$ von $A^*$ lassen sich die Aufzählprozeduren für $M$ und $A^*\backslash M$ wie folgt definieren:
\begin{align}
f_M(n) & =\begin{cases}
f_{A^*}(n), & \quad \text{wenn } \chi_{M,A^*}(f_{A^*}(n)) = wahr\\
a, & \quad \text{sonst}\\
\end{cases}\\
f_{A^*\backslash M}(n) & =\begin{cases}
f_{A^*}(n), & \quad \text{wenn } \chi_{M,A^*}(f_{A^*}(n)) = falsch\\
b, & \quad \text{sonst}\\
\end{cases}\\
\end{align}
wobei gilt: $a \in M, M \neq \emptyset$ und $b \in A^*\backslash M, A^*\backslash M \neq \emptyset$.
</blockquote>

Teil 2
<blockquote>
Laut Voraussetzung sind $M$ und $A^*\backslash M$ aufzählbare Mengen, d.h. gibt es surjektive und total berechenbare Funktionen $f_M:\N\mapsto M$ und $f_{A^*\backslash M}:\N\mapsto A^*\backslash M$.<br/>
<tt>Gegeben:</tt>
$$ $$
<tt>Gesucht:</tt>
$$\chi_{M,A^*}(w)=\begin{cases}
wahr, & \quad \text{wenn } w \in M\\
falsch, & \quad \text{wenn } w \in A^*\backslash M\\
\end{cases}$$
Ein Algorithmus für $\chi_{M,A^*}$ muss für jedes übergebene Wort $w$ genau ein $i$ finden, mit entweder $w=f(i)$ oder $w=g(i)$.<br/><br/>
Da $M \cap (A^*\backslash M) = \emptyset$ ist der Fall $f(i) = g(i) = w$ ausgeschlossen. Da $w \in A^*$ wegen $M \cup (A^*\backslash M) = A^*$ in einer der beiden Mengen enthalten sein muss, terminiert der Suchprozess von $w$.
</blockquote>

== Kreativaufgaben ==

[[BuK/IIm14/Studenten/s3tomack/ka/ram|RAM Programm]]