s3jeleus
Aus ProgrammingWiki
Inhaltsverzeichnis |
Übungsaufgabe 1
Prinzipiell Unlösbares:
- unscharfe Fragestellung
- Regeln zur Suche einer Antwort sind unklar
- zu viele abhängige Parameter
- emotionale Ebene
- exakte Vorhersagen
- begrenzte Ressourcen
- Annäherung an Ergebnisse durch Methoden der KI
Übungsaufgabe 2
Zeigen Sie, dass die folgenden Mengen abzählbar unendlich sind: $\mathbb{Z}, \mathbb{Q}$, die Menge der Primzahlen, die geraden Zahlen.
$\Z$ ist abzählbar unendlich
z.z. $\mathbb{Z}$ ist abzählbar unendlich, d.h. es existiert eine Funktion $\mathbb{f}: \mathbb{N} \xrightarrow{\text{bij.}} \mathbb{Z}$
| 0 | 1 | 2 | 3 | 4 | 5 | ... |
| 0 | -1 | 1 | -2 | 2 | 3 | ... |
$$f(n) = \begin{cases} \frac{n}{2}, & \text{wenn n gerade};\\ - \frac{n + 1}{2}, & \text{sonst }.\\ \end{cases}$$
Beweis durch vollständige Induktion
1. Gleichung
$$f(k) + 1 = f(k + 2)$$ $$f(2n) + 1 = f(2n + 2)$$
1.1Induktionsanfang
$$f(2 \cdot 0) + 1 = f(2 \cdot 0 + 2) $$ $$f(0) + 1 = f(2)$$ $$\frac{0}{2} + 1 = \frac{2}{2}$$ $$1 = 1$$
1.2 Induktionsvoraussetzung
$$f(2n) + 1 = f(2n +2)$$
1.3Induktionsbehauptung
$$ f(2(n + 1) + 1 = f(2(n +1) + 2)$$ $$ \frac{2(n + 1)+ 1}{2} = \frac{2(n+ 1)+ 2}{2}$$ $$ n + 1 +1 = n + 1 + 1$$ $$ n + 2 = n + 2$$ $$ n = n $$
2. Gleichung
$$f(2n + 1) - 1 = f(2n + 3)$$
2.1 Induktionsanfang
$$f(2 \cdot 0 + 1) - 1 = f(2 \cdot 0 + 3)$$ $$f(1) - 1 = f(3)$$ $$\frac{1 + 1}{-2} = \frac{3 +1}{-2}$$ $$-2 = -2$$
2.2 Induktionsvoraussetzung
$$f(2n +1) - 1 = f(2n + 3)$$
2.3Induktionsbehauptung
$$ f(2(n + 1) + 1) -1 = f(2(n +1) + 3)$$ $$f(2n + 2 + 1) -1 = f(2n +5)$$ $$f(2n + 3 )- 1) = f(2n +5)$$ $$ \frac{((2n + 3) + 1)}{-2} -1 = \frac{2n + 5 + 1}{-2}$$ $$\frac{2n + 4}{-2} - 1 = \frac{2n +6}{-2}$$ $$\frac{2n + 4}{- 2} - \frac{1 \cdot (-2)}{-2} = \frac{2n + 6}{-2}$$ $$\frac{2n + 4 +2}{-2} = \frac{2n +6}{-2}$$ $$\frac{2n +6}{-2} = \frac{2n + 6}{ -2}$$
$\Q$ ist abzählbar unendlich
z.z. $\mathbb{Q}$ ist abzählbar unendlich, d.h. es existiert eine Funktion $\mathbb{f}: \mathbb{N} \xrightarrow{\text{bij.}} \mathbb{Q}$
$$f(n) = \begin{cases} 1, & \text{wenn n = 1};\\ f(\frac{n}{2}) + 1, & \text{wenn n gerade};\\ \frac{1}{f(n-1)}, & \text{sonst }.\\ \end{cases}$$
| $\N^+$ \ $\Z$ | $-1$ | $ 1$ | $-2$ | $2$ | $-3$ | ... |
|---|---|---|---|---|---|---|
| 1 | -1/1 | 1/1 | -2/1 | 2/1 | -3/1 | ... |
| 2 | -1/2 | 1/2 | -2/2 | 2/2 | -3/2 | ... |
| 3 | -1/3 | 1/3 | -2/3 | 2/3 | -3/3 | ... |
| 4 | -1/4 | 1/4 | -2/4 | 2/4 | -3/4 | ... |
| 5 | -1/5 | 1/5 | -2/5 | 2/5 | -3/5 | ... |
| ... | ... | ... | ... | ... | ... | ... |
Durch das cantorschn Diagonalverfahren 1. Art lässt sich zeigen, dass die Menge $\Q$ abzählbar unendlich ist.
Die Primzahlen sind abzählbar unendlich
1. Die Menge der Primzahlen P ist unendlich (nach Satz von Euklid).
2. Die Menge der Primzahlen P ist abzählbar unendlich, da gilt: P $\subset \N$.
Die geraden Zahlen sind abzählbar unendlich
1. Die geraden Zahlen G sind unendlich (per Definition) und abzählbar unendlich, da gilt: G $\subset \Z$.
Übungsaufgabe 3
Beweisen Sie den folgenden Satz: Wenn $M_1, M_2, M_3, ... ∞$ abzählbare Mengen sind, dann ist auch die Menge $M_n n=1$ abzählbar.
Eine Menge $M$ ist endlich sofern eine surjektive Abbildung auf diese Menge existiert.
z.z. Es existiert eine Funktion $ f: \N \xrightarrow{\text{sur.}} \cup_{n = 1}^{∞} M_n$
$f_1: \N \xrightarrow{\text{bij.}} M_1$
$f_2: \N \xrightarrow{\text{bij.}} M_2$
$f_3: \N \xrightarrow{\text{bij.}} M_3$
$f_4: ...$
| $\R$ \ $\N$ | $0$ | $1$ | $2$ | $....$ | $j$ | ... |
|---|---|---|---|---|---|---|
| $M_{1}$ | $f_1(1)$ | $f_1(2)$ | $f_1(3)$ | ... | $f_1(j)$ | ... |
| $M_{2}$ | $f_2(1)$ | $f_2(2)$ | $f_2(3)$ | ... | $f_2(j)$ | ... |
| $M_{3}$ | $f_3(1)$ | $f_3(2)$ | $f_3(3)$ | ... | $f_3(j)$ | ... |
| ... | ... | ... | ... | ... | ... | ... |
| $M_{i}$ | $f_i(1)$ | $f_i(2)$ | $f_i(3)$ | ... | $f_i(j)$ | ... |
Mit Hilfe des cantorschn Diagonalverfahrens 1. Art lässt sich eine surjektive Abbildung darstellen.
Übungsaufgabe 4
Verifizieren Sie, dass die folgende Funktion $f : N^+ \xrightarrow{} \Q^+$ eine bijektive Funktion ist und implementieren Sie eine Prozedur, die die zugehörige Umkehrfunktion $f ^−1$ berechnet.
$$f(n) = \begin{cases} 1, & \text{wenn } n=1;\\ f(\frac{n}{2})+1, & \text{wenn } n \text{ gerade};\\ \frac{1}{f(n-1)}, & \text{wenn } n \text{ ungerade}. \end{cases}$$
| $\N^+$ \ $\Z^+$ | $1$ | $2$ | $3$ | $4$ | $5$ | ... |
|---|---|---|---|---|---|---|
| 1 | 1/1 | 2/1 | 3/1 | 4/1 | 5/1 | ... |
| 2 | 1/2 | 2/2 | 3/2 | 4/2 | 5/2 | ... |
| 3 | 1/3 | 2/3 | 3/3 | 4/3 | 5/3 | ... |
| 4 | 1/4 | 2/4 | 3/4 | 4/4 | 5/4 | ... |
| 5 | 1/5 | 2/5 | 3/5 | 4/5 | 5/5 | ... |
| ... | ... | ... | ... | ... | ... | ... |
Umkehrfunktion:
$$ f^{-1}(n) = \begin{cases}1, & n = 1 \\ f^{-1}(n-1) * 2, & n > 1 \\ f^{-1}(\frac{1}{n}) + 1, & sonst\end{cases} $$
Übungsaufgabe 5
Indirekter Beweis: R ist abzählbar unendliche Menge, d.h es existiert eine Funktion $f: \N \xrightarrow{\text{bij.}} \R$
$n_{ij} \in [0,9]$
Es lässt sich stets eine neue Zeile, die eine neue reele Zahl repräsentiert, hinzufügen.
$$n_i = \begin{cases} n_{ii} + 1, & \text{wenn $n_{ii} \neq 9$};\\ 0, & \text{sonst }.\\ \end{cases}$$
| $\R$ \ $\N$ | $0$ | $1$ | $2$ | $...$ | $j$ | ... |
|---|---|---|---|---|---|---|
| $n_{1}$ | $n_{10}$ | $n_{11}$ | $n_{12}$ | ... | $n_{1j}$ | ... |
| $n_{2}$ | $n_{20}$ | $n_{21}$ | $n_{22}$ | ... | $n_{2j}$ | ... |
| $n_{3}$ | $n_{30}$ | $n_{31}$ | $n_{32}$ | ... | $n_{3j}$ | ... |
| ... | ... | ... | ... | ... | ... | ... |
| $n_{i}$ | $n_{i0}$ | $n_{i1}$ | $n_{i2}$ | $n_{i3}$ | $n_{ij}$ | ... |
Kreativaufgabe Gödelisierung und $\mu$-rekursive Funktionen
Aufgabe
Sei eine Gödelisierung von
, d.h.
ist injektiv, total und berechenbar.
ist entscheidbar und
ist berechenbar.
Dann können die Wörter aus vermöge
gödelgeordnet werden, so dass
, für alle
und
.
Die folgende µ-rekursive Funktion liefert die Folge der Gödelnummern in aufsteigender Form.
Für gilt:
Die zur Definition von verwendete zahlentheoretische Funktion
ist
Illustrieren Sie die folgenden Aussagen durch den Einsatz selbst entwickelter Scheme-
Prozeduren. Wählen Sie exemplarisch und die Verschlüsselung im 3er-System,
mit
als Gödelisierung h mit
mit
. Das Wort
aba erhält dann die Gödelnummer
. Nicht jede natürliche
Zahl ist Gödelnummer eines Wortes aus
: Beispielsweise ist
keine.
ist ein total berechenbares Prädikat. (Hinweis: Hierzu benötigen Sie eine Scheme-Prozedur für ein total berechenbares Prädikat, das feststellt, ob eine gegebene Zahl y Gödelnummer ist, d.h. y muss in der Form
mit
darstellbar sein.)
wächst streng monoton und ist total. (Hinweis: Verwenden Sie eine Scheme-Prozedur zur Berechnung der ersten 10 Gödelnummern.)
Mit Hilfe der Funktion kann man das
-te Wort in der gödelgeordneten Folge der Wörter aus
bestimmen.
ist total und injektiv. Die zugehörige Umkehrfunktion
liefert somit auch wieder die Gödelisierung mit
.
Eine Prozedur zur Berechnung einer Gödelnummer ist gegeben durch
Eine Funktion zum Testen ob eine gegebene natürliche Zahl eine Gödelnummer ist gegeben durch die Funktion
$$f(x) = \begin{cases} 1, x < 3\\ 0, x mod 3 = 0\\ f( \lfloor{}x/3 \rfloor{}), sonst \end{cases}$$.
Beweis:
Ist die angegebene Zahl 1 oder 2, so tritt der Elementarfall ein und die Lösung lautet wahr.
Ansonsten prüft die Funktion, ob die gegebene Nummer dem Aufbauschema
$$p_{i}3^{i} + p_{i-1}3^{i-1} + ... + p_{1}3^{1} + p_{0}3^{0} $$
entspricht. Wobei p jeweils die Werte 1 oder zwei annehmen muss.
Ist der letzte Summand gleich 0, so entspricht die angegebene Zahl einem Vielfachen von drei.
Da der letzte Summand aber 1 oder zwei sein muss entspricht das nicht dem Schema und es muss falsch zurückgegeben werden. (x mod 3=0)
Die folgenden Schritte bestehen nun darin auch die nachfolgenden Summanden dieser Prüfung zu unterlegen.
Dazu eliminiert man mittels division durch drei und anschließender Abrundung den letzten Summanden.
Die Prozedur lautet damit
Eine Prozedur zur Auflistung ist gegeben durch
Eine schnellere Variante ergibt sich daraus, die natürlichen Zahlen durchzugehen und zu prüfen, ob diese Gödelnummern sind oder nicht
Die Umkehrfunktion ist gegeben durch
