Thema3
Aus ProgrammingWiki
Inhaltsverzeichnis |
Aufgabe 1
Wie viele berechenbare charakteristische Funktionen gibt es?
Hinweis: Potenzmenge unendlicher Mengen
Zu jeder Teilmenge der Menge $A^*$ existiert eine charakteristische Funktion. Daher gibt es so viele charakterisitsche Funktionen, wie es Teilmengen gibt. Sämtliche Teilmengen einer Menge $M$ sind in der Potenzmenge von $M$ enthalten. Da die Potenzmenge einer unendlichen Menge überabzählbar unendlich viele Elemente besitzt, gibt es demzufolge ebenfalls überabzählbar unendlich viele charakteristische Funktionen.
Aufgabe 2
Beispiel 1:
M ist die Menge aller Wörter aus $A^*$, die die Länge 3 besitzen, d.h.:
$A^* = \{a, b\}^* \text{ und } M \subset A^* = \{w \mid w \in A^*\text{ und } |w| = 3\}$
- bei diesem Beispiel handelt es sich um eine endliche Menge
- somit kann jedes Element der Menge mit dem gesuchten Element verglichen und eine Entscheidung getroffen werden
- die entsprechende charakteristische Funktion dazu ist: $ \chi_M(w) = \begin{cases} wahr, & \text{wenn } w \in M;\\ falsch, & \text{sonst} \end{cases} $
Beispiel 2 abzählbar unendliche Menge
$ M $ ist die Menge aller Wörter, die aus beliebeig vielen $ a $'s und $ b $'s bestehen und mit $ a $ beginnen: $ A^* = \{a,b\}^* $ und $ M \subset A^* = \{w = aw' | w' \in A^* \} $ .
Zeigen Sie, dass die beiden Mengen aus den Beispielen entscheidbar sind. Schreiben Sie je eine entsprechende Prozedur für die jeweilige charakteristische Funktion
Aufgabe 3
Zeigen Sie, dass die Menge der geraden Zahlen G eine aufzählbare Menge ist.
Um Aufzählbarkeit zu beweisen, muss gezeigt werden, dass die zu untersuchende Menge abzählbar und berechenbar ist.
Die Abzählbarkeit wird bewiesen, indem eine Funktion angegeben wird, welche die natürlichen Zahlen bijektiv auf die Menge der geraden Zahlen abbildet:
$$f(x) = 2x$$
Die Berechenbarkeit wird nachgewiesen, indem eine Prozedur angegeben wird, welche eine natürliche Zahl nimmt und ein Element der geraden Zahlen ausgibt:
Da sowohl die Abzählbarkeit, als auch die Berechnbarkeit nachgewiesen wurden, ist gezeigt, dass die Menge der geraden Zahlen aufzählbar ist.
Aufgabe 4
Zeigen Sie, dass die Menge der Primzahlen P aufzählbar ist.
Nach Euklid ist die Menge der Primzahlen eine unendliche Menge. Da sie außerdem eine Teilmenge der natürlichen Zahlen ist, die abzählbar unendlich sind, ist sie ebenfalls abzählbar unendlich.
Die Prozedur zur Berechnung einer Primzahl ist etwas umfangreicher:
Da wiederum die Abzählbarkeit und die Berechenbarkeit nachgewiesen werden konnten, ist gezeigt, dass die Menge der Primzahlen aufzählbar ist.
Aufgabe 5
Wir wissen, dass A* eine abzählbar unendliche Menge ist. Zeigen Sie, dass A* auch aufzählbar ist. Hinweis: Hierzu ist es notwendig ein Aufbauschema für A* zu entwerfen und anschließend eine Prozedur dafür zu implementieren.
Aufgabe 6
Zeigen Sie, dass jede endliche Menge M aufzählbar ist.
aufzählbar = abzählbar + berechenbar
Eine Menge ist endlich, wenn es eine bijektive Abbildung zwischen dieser Menge und den natürlichen Zahlen bis zu einem Element $n$ gibt. Durch diese bijektive Abbildung ist jede endliche Menge auch abzählbar.
Um die Aufzählbarkeit nachzuweisen, muss es laut Definition eine Funktion $f$ geben, die total berechenbar und mindestens surjektiv ist und die natürlichen Zahlen auf M abbildet ($f:\mathbb{N} \rightarrow M$). Diese Funktion stellt dann die Aufzählprozedur oder das Auzählverfahren von M dar. Sie nimmt als Eingabe eine natürliche Zahl und gibt ein Element der endlichen Menge aus. Es wird also der Reihe nach jedes Element aus $\mathbb{N}$ einem Element aus M zugeordnet.
Handelt es sich um eine surjektive Funktion, werden die restlichen Elemente von $\mathbb{N}$ auf ein beliebiges Element von M abgebildet werden. Somit ist die Funktion $f$ surjektiv, total und berechenbar.
Aufgabe 7
Die Menge G der Gitterpunkte (0, 0),(0, 1), ... einer x-y-Ebene ist aufzählbar.
1. Geben Sie eine Funktion f an, die $\N_0$ bijektiv auf G abbildet.
2. Definieren Sie eine Ordnungsrelation $p_<$ in G.
3. Geben Sie eine Funktion k zur Berechnung der Platznummer k(x, y) des betrachteten Gitterpunktes (x, y) an.
4. Geben Sie eine Aufzählprozedur für G an und begründen Sie deren Berechenbarkeit.
Aufgabe 8
Das Halteproblem ist semi-entscheidbar. Beweisen Sie diese Aussage.
Aufgabe 9
Geben Sie fur die Menge FIBS der Fibonacci-Zahlwörter eine Aufzählfunktion an und begründen Sie deren Berechenbarkeit. Weisen Sie nach, dass FIBS eine semi-entscheidbare Menge ist. Zeigen Sie, dass FIBS sogar entscheidbar ist.
Aufgabe 10
Übertragen Sie die vorhergehende Übungsaufgabe sinngemäß auf die Menge der Quadratzahlen $QZ = \{n^2 |n \in \N\}.$
Aufgabe 11
Weisen Sie nach, dass die Menge $M$ aller "Wörter" aus $\{a,b\}^*$, die mit a beginnen, semi-entscheidbar ist.
Damit eine Menge M semi-entscheidbar ist, muss die semi-charakteristische Funktion $\chi'_M$ berechenbar sein:
$$\chi'_M(w) = \begin{cases} wahr, & \text{wenn } w \in M,\\ \perp, & \text{sonst}.\end{cases}$$
Aufgabe 12
Definieren Sie die Menge der geraden Zahlen (Zahlwörter) und die der ungeraden Zahlen (Zahlwörter) und veranlassen Sie das ProgrammingWiki die 30 ersten Elemente der Vereinigungsmenge (in aufsteigender Sortierung) auszugeben.
Menge der geraden Zahlwörter: $M_G = \{"0","2","4","6", ...\}$
Menge der ungeraden Zahlwörter: $M_U = \{"1","3","5","7", ...\}$
Die zugehörigen Funktionen berechnen die entsprechenden Zahlen, die allerdings dann als String (Zahlwörter) dargestellt werden müssen.
$$f(n) = 2n$$ $$g(n) = 2n+1$$
Die Funktion zur Vereinugungsmenge dieser beiden Abbildungen sieht folgendermaßen aus:
$$h(n) = \begin{cases} f\left(\frac{n}{2}\right), & \text{wenn n gerade}, \\ g\left(\frac{n-1}{2}\right), & \text{sonst}. \end{cases}$$
