BuK/IIm14/Studenten/s3jeleus

Wiki-Quelltext dieser Seite.

<language>Scheme</language>
== Ü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}$

{| border="1" cellpadding="5" cellspacing="0"
|-
|| 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(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{2(n+ 1)+ 2}{2}$$
$$ n + 1 +1 = n + 1 + 1$$
$$ n + 2 = n + 2$$
$$ n = n $$

''' 2. Gleichung'''

$$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{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}$$

{| border="1" cellpadding="5" cellspacing="0"
!$\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: ...$

{| border="1" cellpadding="5" cellspacing="0"
!$\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}$$

{| border="1" cellpadding="5" cellspacing="0"
!$\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 || ...
|-
|| ... || ... || ... || ... || ... || ... || ...
|-
|}

<code id="552e94541ee0b">(define f 
    (lambda (n) 
        (if (= n 1)
            1
            (if (= (modulo n 2) 0)
                (+ 1 (f (/ n 2)))
                (/ 1 (f (- n 1)))
            )
        )
    )
)</code>

<run id="552e94541ee7c"></run>


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

{| border="1" cellpadding="5" cellspacing="0"
!$\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}$  || ...
|-
|}