uebung2
Aus ProgrammingWiki
Inhaltsverzeichnis |
Aufgabe 1
- Unzugängliches (wenigstens) für Computer
- Praktisch Unmögliches
Kommentieren Sie. Nennen Sie Beispiele.
Lösung:
Unzugängliches:
- es fehlt eine Beschreibungssprache, nicht maschinell verarbeitbar
- Probleme/Aufgaben sind oft komplex und besitzen viele (abhängige) Parameter
- Beispiele: "Gefallen ihr die Blumen?", "Gewinne ich morgen im Lotto?"
Praktisch Unmögliches:
- das sind Probleme die maschinell beschreibbar, jedoch aufgrund begrenzter Ressourcen nicht effizient lösbar sind.
- Beipsiele: n-Damen-Problem, Traveling-Salesman-Problem, Stundenplan-Problem
Aufgabe 2
Warum ist es so schwierig ein leistungsfähiges Schachprogramm zu entwerfen?
Lösung:
Theoretisch kein Problem, man berechnet alle möglichen Konstellationen. Praktisch schwierig durch hohen Speicherverbrauch und die benötigte Zeit.
Aufgabe 3
Zeigen Sie, dass die folgenden Mengen abzählbar unendlich sind: $\Z, \Q$, die Menge der Primzahlen, die geraden Zahlen.
Lösung:
... Die Menge der ganzen Zahlen $\Z$: ...
Mit der Funktion , mit
können alle ganzen Zahlen bijektiv auf die natürlichen Zahlen abgebildet werden.
| 0 | 1 | 2 | 3 | 4 | 5 | ... | |
| 0 | 1 | -1 | 2 | -2 | 3 | ... |
... Die Menge der rationalen Zahlen $\Q$: ...
Beweisen mit Cantor 1. Art:
Zuerst betrachtet man die Menge der positiven rationalen Zahlen $\Q⁺$.
Die Brüche lassen sich in einem zweidimensionalen Schema anordnen, sodass folgende Tabelle entsteht:
| $\N$\$\N$ | $1$ | $2$ | $3$ | $4$ | $5$ | ... |
|---|---|---|---|---|---|---|
| 1 | 1/1 | 1/2 | 1/3 | 1/4 | 1/5 | ... |
| 2 | 2/1 | 2/2 | 2/3 | 2/4 | 2/5 | ... |
| 3 | 3/1 | 3/2 | 3/3 | 3/4 | 3/5 | ... |
| 4 | 4/1 | 4/2 | 4/3 | 4/4 | 4/5 | ... |
| 5 | 5/1 | 5/2 | 5/3 | 5/4 | 5/5 | ... |
| ... | ... | ... | ... | ... | ... | ... |
Die Brüche lassen sich diagonal abzählen. Dabei blendet man die ungekürzten Brüche aus, da sie sich in den Äquivalenzklassen der entsprechenden gekürzten Brüche befinden.
Auf diese Weise erhält man eine Abzählung der positiven rationalen Zahlen:
| 1 | 2 | 3 | 4 | 5 | ... | |
| 1 | $\frac{1}{2}$ | 2 | 3 | $\frac{1}{3}$ | ... |
Durch das Beschränken auf den ungekürzten Repräsentanten der jeweiligen Äquivalenzklasse eines Bruches wird die bijektive Abbildung auf die natürlichen Zahlen erreicht.
Um nun auf auf den gesamten Bereich der rationalen Zahlen zu verallgemeinern, wird die Abzählung erweitert, indem vor die Eins die Null und hinter jede Zahl ihr Negatives ergänzt wird.
| 1 | 2 | 3 | 4 | 5 | ... | |
| 0 | 1 | -1 | $\frac{1}{2}$ | $-\frac{1}{2}$ | ... |
... Die Menge der Primzahlen: ...
Nach Euklid ist die Menge der Primzahlen unendlich und als Teilmenge der natürlichen Zahlen abzählbar unendlich.
... Die Menge der gerade Zahlen ...
Die Menge der geraden Zahlen ist per Definition unendlich und als Teilmenge der ganzen Zahlen abzählbar unendlich.
Aufgabe 4
Beweisen Sie den folgenden Satz: Wenn $M_{1}, M_{2}, M_{3} ...$ abzählbare Mengen sind, dann ist auch die Menge $\bigcup_{n=1}^\infty {M_{n}}$ abzählbar.
Lösung:
Das kann mit Cantor 1. Art bewiesen werden.
Die Mengen sind abzählbar und somit lassen sie sich in geordneter Reihenfolge aufschreiben.
| $m_{1}(0) = n(0)$ | $m_{1}(1) = n(1)$ | $m_{1}(2) = n(5)$ | $m_{1}(3) = n(6)$ | … |
| $m_{2}(0) = n(2)$ | $m_{2}(1) = n(4)$ | $m_{2}(2) = n(7)$ | $m_{2}(3) = n(13)$ | … |
| $m_{3}(0) = n(3)$ | $m_{3}(1) = n(8)$ | $m_{3}(2) = n(12)$ | $m_{3}(3) = n(17)$ | … |
| $m_{4}(0) = n(9)$ | $m_{4}(1) = n(11)$ | $m_{4}(2) = n(18)$ | $m_{4}(3) = n(24)$ | … |
| … | … | … | … | … |
Mit dem Verfahren kann man an jedes Element der Teilmengen gelangen und somit ist die Vereinigungsmenge abzählbar.
Aufgabe 5
Verifizieren Sie, dass die folgende Funktion $f:\N^+ \rightarrow \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}$$
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} $$
1. Schreiben Sie als erstes eine Scheme-Prozedur für $f$ und führen Sie einige rekursive Berechnungen aus.
2. Berechnen Sie $f(n)$ für $n = 1,2,....,7$ mit Hand.
3. Verbessern Sie die Effizienz der Prozedur für $f$ mittels memoizing.
Lösung:
zu 1.
zu 2.
$f(1) = 1$
$f(2) = 2$
$f(3) = 0,5$
$f(4) = 3$
$f(5) = \frac{1}{3}$
$f(6) = 1,5$
$f(7) = \frac{2}{3}$
zu 3.
OFFEN
Aufgabe 6
Zeigen Sie, dass $\mathbb{R}$ überabzählbar unendlich ist. Hinweis: Es reicht schon aus zu zeigen, dass es im Intervall [0, 1] überabzählbar unendlich viele reelle Zahlen gibt.
Lösung:
Indirekter Beweis
Annahme: $\mathbb{R}$ ist abzählbar unendlich.
Wenn dem so ist, dann kann man die reelen Zahlen nacheinander auflisten.
$n_{1} = 0,$ $n_{11}$ $n_{12}$ $n_{13}$ $n_{14} ... $
$n_{2} = 0,$ $n_{21}$ $n_{22}$ $n_{23}$ $n_{24} ... $
$n_{3} = 0,$ $n_{31}$ $n_{32}$ $n_{33}$ $n_{34} ... $
$.$
$.$
$.$
$n_{i} = 0,$ $n_{i1}$ $n_{i2}$ $n_{i3}$ $n_{i4} ... $
$.$
$.$
$.$
Konstruktion einer Zahl $x$ mit $x \in [0 ; 1]$, die nicht in der Menge vorkommen kann:
$x = 0,$ $x_{1}$ $x_{2}$ $x_{3}$ $x_{4} ...$
| $n_{1}$ | $\bf n_{11}$ | $n_{12}$ | $n_{13}$ | $n_{14}$ | $...$ | $...$ |
| $n_{2}$ | $n_{21}$ | $\bf n_{22}$ | $n_{23}$ | $n_{24}$ | $...$ | $...$ |
| $n_{3}$ | $n_{31}$ | $n_{32}$ | $\bf n_{33}$ | $n_{34}$ | $...$ | $...$ |
| $n_{4}$ | $n_{41}$ | $n_{42}$ | $n_{43}$ | $\bf n_{44}$ | $...$ | $...$ |
| $...$ | $...$ | $...$ | $...$ | $...$ | $...$ | $...$ |
| $x$ | $x_{1} $ | $x_{2}$ | $x_{3} $ | $x_{4}$ | $\bf x_{5}$ | $...$ |
wobei $x_{i} = (n_{ii} +1)$ $mod 10$ sein soll. Durch diese Definition wird ersichtlich, dass man immer eine Zahl $x$ findet, die nicht innerhalb $\mathbb{R}$ ist.
Wenn es immer eine Zahl $x$ gibt, die nicht in der Menge ist, dann ist $\mathbb{R}$ auch nicht abzählbar unendlich und damit überabzählbar unendlich.
