s3jeleus

Aus ProgrammingWiki
< BuK < IIm14 < Studenten
Archivierte Version vom 2015-04-16T07:26:29+00:00. Aktuelle Version

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}

| 012345...
| 01-12-23...
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 \cdot 0) + 1 = f(2 \cdot 0 + 2) f(0) + 1 = f(2) \frac{0}{2} + 1 = \frac{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}

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-22-3...
| 1-1/11/1-2/12/1-3/1...
| 2-1/21/2-2/22/2-3/2...
| 3-1/31/3-2/32/3-3/3...
| 4-1/41/4-2/42/4-3/4...
| 5-1/51/5-2/52/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 \ \N012....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.

\N^+ \ \Z^+12345...
| 11/12/13/14/15/1...
| 21/22/23/24/25/2...
| 31/32/33/34/35/3...
| 41/42/43/44/45/4...
| 51/52/53/54/55/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} 

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