s3tomack
Aus ProgrammingWiki
Inhaltsverzeichnis |
Ü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 }$
| $\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$
| $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:
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$.
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}$$
Teil2:
Gegeben ist eine semi-entscheidbare Menge $M$. Somit steht eine partiell berechenbare Funktion $\chi'_M:A^*\mapsto\{wahr\}$ zur Verfügung.
Gesucht ist eine surjektive, total berechenbare Aufzählfunktion: $f_M:\N\mapsto M$.
Problem: Ob für ein beliebiges Wort $w \in A^*$ entweder $w \in M$ oder $w \notin M$ gilt, kann nur mit chi-strich 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.
Gegenmaßnahme: bijektive, total berechenbare Paarungsfunktion $\pi:\N\times\N\mapsto\N$
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$$
Vervollständigen Sie die Herleitung der Funktionen für $x$ und $y$ aus $z = \pi(x, y)$.
$z=\frac{(x+y)(x+y+1)}{2}+y=t+y$
$w=x+y$
$t,x,y,z,w \in \N$
$t=z-y=\frac{w(w+1)}{2}=\frac{w^2+w}{2}$
Lösung von $w^2+w-2t=0$:
allgemeine Form: $w^2+pw-q=0$
pq-Formel: $w_{1,2}=-\frac{p}{2}\pm\sqrt{\left(\frac{p}{2}\right)^2-q}$
$w_{1,2}=-\frac{1}{2}\pm\sqrt{\left(\frac{1}{2}\right)^2+2t}$
$w_{1,2}=-\frac{1}{2}\pm\sqrt{\frac{1}{4}+\frac{8t}{4}}$
$w_{1,2}=-\frac{1}{2}\pm\sqrt{\frac{8t+1}{4}}$
$w_{1,2}=-\frac{1}{2}\pm\frac{\sqrt{8t+1}}{2}$
Für positive $w$ ergibt sich $w_1$:
$w_1=-\frac{1}{2}+\frac{\sqrt{8t+1}}{2}$
$w_1=\frac{\sqrt{8t+1}-1}{2}$
Außerdem gilt:
$t \leq z, \text{ da } z = t + y$
$z = t + w - x, \text{ da } z = t + y \text{ und } y = w - x$
$z \leq t + w < t + w + 1$
$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}$
$z < \frac{(w+1)^2+(w+1)}{2}$
Unter Verwendung von $z < \frac{(w+1)^2+(w+1)}{2}$ können wir $w$ nach oben abschätzen:
$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:
$\frac{\sqrt{8\left(\frac{(w+1)^2+(w+1)}{2}\right) + 1} - 1}{2}$
$\frac{\sqrt{8\left(\frac{w^2+3w+2}{2}\right) + 1} - 1}{2}$
$\frac{\sqrt{\left(\frac{8w^2+24w+16}{2}\right) + 1} - 1}{2}$
$\frac{\sqrt{4w^2+12w+9} - 1}{2}$
$\frac{\sqrt{(2w+3)^2} - 1}{2}$
$\frac{2w+2}{2}=w+1$
Daher ergibt sich $w=\lfloor \frac{\sqrt{8z + 1} - 1}{2} \rfloor \in \N$
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.
Danach ergeben sich:
$t = \frac{w (w + 1)}{2}$
$y = z - t$
$x = w - y$
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$
$t = \frac{w (w + 1)}{2} = \frac{4 (4 + 1)}{2} = \frac{20}{2} = 10$
$y = z - t = 13 - 10 = \underline{3}$
$x = w - y = 4 - 3 = \underline{1}$
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:
Gegeben ist eine bijektive Funktion $f_1 : \N \mapsto M_1$, da $M_1$ abzählbar ist.
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$$
Teil 2:
Annahme: Für eine aufzählbare Menge $M_1$ sind alle Teilmengen $M_2 \subseteq M_1$ aufzählbar.
Laut dieser Annahme ist die Menge $M_2$ aufzählbar, darausfolgt das $M_2$ semi-entscheidbar ist.
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.
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
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.
Gegeben: $$\chi_{M,A^*}(w)=\begin{cases} wahr, & \quad \text{wenn } w \in M\\ falsch, & \quad \text{wenn } w \in A^*\backslash M\\ \end{cases}$$ Gesucht: \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$.
Teil 2
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$.
Gegeben: $$ $$ Gesucht: $$\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)$.
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$.
