s3jeleus

Aus ProgrammingWiki

Archivierte Version vom 2015-04-16T06:45:25+00:00. Aktuelle Version

Inhaltsverzeichnis

1 Übungsaufgabe 1
2 Übungsaufgabe 2

Ü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

f(n) + 1 = f(n + 2) f(2n) + 1 = f(2n + 2)

Induktionsanfang

f(2 *0) + 1 = f(2 * 0 + 2) f(0) + 1 = f(2) 0/2 + 1 = 2/2 1 = 1

Induktionsvoraussetzung

f(2n) + 1 = f(2n +2)

Induktionsbehauptung

f(2(n + 1) + 1 = f(2(n +1) + 2) \frac{2(n + 1)+ 1}{2} = \frac{f(2(n+ 1)+ 2}{2} n + 1 +1 = n + 1 + 1 n + 2 = n + 2 n = n

\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}

\Z \ \N	-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	...
\| ...	...	...	...	...	...	...

f(n) = \begin{cases} 1, & wenn \text{wenn n = 1};\\ f(\frac{n}{2}) + 1, & \text{wenn n gerade};\\ \frac{1}{f(n-1)}, & \text{sonst }.\\ \end{cases}

Die Primzahlen sind abzählbar unendlich

Die Geraden Zahlen sind abzählbar unendlich

(define f 
    (lambda (n) 
        (if (= n 1)
            1
            (if (= (modulo n 2) 0)
                (+ 1 (f (/ n 2)))
                (/ 1 (f (- n 1)))
            )
        )
    )
)

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}

Reele Zahlen

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}	...