Thema2
Aus ProgrammingWiki
Inhaltsverzeichnis |
Aufgabe 1
Kommentieren Sie. Nennen Sie Beispiele.
- Unzugängliches (wenigstens) für Computer
- Praktisch Unmöglich
zu 1:
- benötigte Beschreibungssprachen fehlen, dadurch nicht maschinell verarbeitbar bzw. formalisierbar
- es sind umfassende Probleme, mit vielen abhängigen Parametern vorhanden
- durch den Einsatz von künstlicher Intelligenz, Data Mining und Computersimulation wird die Klasse der unzugänglichen Probleme immer mehr verkleinert
- Beispiel: Wird alles gut werden? , Gefällen ihr die Schuhe oder nicht?
zu 2:
- vorhandene Probleme können maschinell beschrieben werden, aber nicht effizient gelöst werden
- Beispiel: Travelling Salesman Problem, Job Shop Scheduling Problem
Aufgabe 2
Wiederholen Sie die Definition von abzählbar unendlichen Mengen.
abzählbar unendliche Mengen
Eine Menge ist abzählbar unendlich, wenn es möglich ist eine bijektive Abbildung zwischen der Menge der natürlichen Zahlen und der Menge X zu finden ist.
überabzählbar unendliche Mengen
Wird eine solche Funktion nicht gefunden, ist die zu untersuchenden Menge überabzählbar unendlich.
Aufgabe 3
Cantorisches Diagonalisierungsverfahren 1.Art: Idee und am Beispiel der Wortmenge $A^*$
Cantorsches Diagonalisierungsverfahren 1. Art
Motivation dieses Verfahrens ist es, eine sichere Aussage über die Überabzählbarkeit von Mengen zu treffen.
Diese Art ist konstruktiver Natur und läuft auf das Abzählen der Elemente hinaus. Hierbei versucht man die Mengen nach einem bestimmten Prinzip zu ordnen und bildet sie anschließend auf die Menge der natürlichen Zahlen ab.
Beispiel: Wortmenge $A^*$
- Alphabet: $A={a,b,c} \rightarrow$ die Wortmenge wird längen-lexikografisch (nach Länge und Alphabet) geordnet
- Wortmenge: $A^* = \{\epsilon, a,b,c, aa, ab, ac, ba, bc, ca, cb, abc, ...\} \rightarrow$ durch die Verkettung entstehen neue Wörter
- außerdem lassen sich die einzelnen Wörter in Bereiche unterteilen $\rightarrow$ die Länge der einzelnen Bereich entspricht einer Kardinalität von $|A|^{\text{Ordnungsrelation des Bereiches}}$
- 1.Bereich: $\epsilon$
- 2.Bereich: $a,b,c$
- usw.
- somit ist es möglich jedes Element der Wortmenge auf die natürlichen Zahlen ($\mathbb{N}\rightarrow$ A*) bijektiv abzubilden
- und es kann gesagt werden, dass die Wortmenge A* eine abzählbar unendliche Menge ist
Aufgabe 4
Zeigen Sie, dass die folgenden Mengen abzählbar unendliche Mengen sind $\mathbb{Z}$, $\mathbb{Q}$, die Menge der Primzahlen und die geraden Zahlen.
Die Menge der ganzen Zahlen ($\mathbb{Z}$)
- die Elemente der Menge der ganzen Zahlen können auf eine Zahlenstrahl dargestellt und somit indexiert werden.
- 0,-1,1,-2,2,-3,3,...
- $f(i)=\begin{cases}-\frac{i}{2} & \text{, wenn }i(i \in \mathbb{N})\text{ gerade}\\\frac{i+1}{2} & \text{, sonst}\end{cases}$
$\rightarrow$ mit dieser Funktion wird die bijektive Abbildung der natürlichen Zahlen auf die ganzen Zahlen noch einmal verdeutlicht
- somit kann gesagt werden, das die Menge der ganzen Zahlen eine abzählbar unendliche Menge ist
Die Menge der rationalen Zahlen ($\mathbb{Q}$)
- um zu beweisen, dass die Menge der rationalen Zahlen abzählbar unendlich ist, kommt das 1.Cantorsche Diagonalverfahren zum Einsatz
| $0$ | $1$ | $2$ | $3$ | $4$ | $5$ | ... | |
|---|---|---|---|---|---|---|---|
| 0 | --- | --- | --- | --- | --- | --- | ... |
| 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 | ... |
| ... | ... | ... | ... | ... | ... | ... | ... |
- Dadurch kann bewiesen werden, dass die Menge der rationalen Zahlen ein abzählbar unendliche Menge ist
Die Menge der Primzahlen
- Die Menge der natürlichen Zahlen ist eine abzählbar unendliche Menge und die Menge der Primzahlen ist eine Teilmenge der natürlichen Zahlen
- P $\subseteq \mathbb{N}$
- Die Menge der ganzen Zahlen ist eine abzählbar unendliche Menge und die Menge der Primzahlen ist eine Teilmenge der genzen Zahlen
- Nach dem Satz von Euklid sind die Primzahlen unendlich
Die Menge der geraden Zahlen
- Die Menge der natürlichen Zahlen und die der ganzen Zahlen sind abzählbare unendliche Mengen und da die Menge der geraden Zahlen eine Teilmenge dieser ist, ist sie somit ebenfalls abzählbar unendlich
Aufgabe 5
Beweisen Sie den folgenden Satz:
Wenn $M_0,M_1,M_2,M_3$,.... abzählbare Mengen sind, dann ist auch die Menge $\bigcup_{n=1}^\infty M_n$ abzählbar.
- dies kann wiederum mit dem 1.Cantorschen Diagonalverfahren nachgewiesen werden
- da es sich hier um eine abzählbar uneendliche Menge handelt lassen sich diese auch Ordnen $\rightarrow$ somit zeigen das auch die Vereinigung der Mengen abzählbar unendliche Mengen sind
| 0 | 1 | 2 | 3 | … | |
| $m_0$ | $m_{0}(0) = n(0)$ | $m_{0}(1) = n(2)$ | $m_{0}(2) = n(5)$ | $m_{0}(3) = n(9)$ | … |
| $m_1$ | $m_{1}(0) = n(1)$ | $m_{1}(1) = n(4)$ | $m_{1}(2) = n(8)$ | $m_{1}(3) = n(13)$ | … |
| $m_2$ | $m_{2}(0) = n(3)$ | $m_{2}(1) = n(7)$ | $m_{2}(2) = n(12)$ | $m_{2}(3) = n(18)$ | … |
| $m_3$ | $m_{3}(0) = n(6)$ | $m_{3}(1) = n(11)$ | $m_{3}(2) = n(17)$ | $m_{3}(3) = n(24)$ | … |
| ... | … | … | … | … | … |
Aufgabe 6
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}$$
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 = 0, 1, 2,...,7$ mit Hand
$f(1) = 1$
$f(2) = f(2/2) + 1 = 1 + 1 = 2$
$f(3) = f(1/f(3-1)) = 1/2$
$f(4) = f(4/2) + 1 = f(2) + 1 = 3 $
$f(5) = f(1/f(5-1)) = 1/3$
$f(6) = f(6/2) + 1 = f(3) + 1 = 3/2$
$f(7) = f(1/f(7-1)) = f(1/f(6)) = f(1/(3/2) = 2/3$
3. Verbessern Sie die Effizienz der Prozedur f mittels memoizing.
Aufgabe 7
Zeigen Sie, dass die Menge der reellen Zahlen überabzählbar unendlich ist.
Hinweis: Es reicht schon aus zu zeigen, dass es im Intervall [0,1] überabzählbar unendlich viele reelle Zahlen gibt.
Um zu zeigen das die Menge der reellen Zahlen eine überabzählbar unendliche Menge ist, kann das Verfahren des indirekten Beweises angewendet werden.
- Annahme: Die Menge der der reellen Zahlen ist abzählbar unendlich.
- Ist die Annahme, die aufgestellt wurden ist korrekt, dann ist es möglich alle reellen Zahlen der Reihenfolge nach anzuordnen
| 1 | 2 | 3 | … | |
| $m_1$ | $m_{1,1}$ | $m_{1,2}$ | $m_{1,3}$ | … |
| $m_2$ | $m_{2,1}$ | $m_{2,2}$ | $m_{2,3}$ | … |
| $m_3$ | $m_{3,1}$ | $m_{3,2}$ | $m_{3,3}$ | … |
| … | … | … | … | … |
- um jetzt zu zeigen das die reellen Zahlen abzählbar unendlich sind, muss eine Zahl gefunden werden, die in der Menge vorkommt
- durch diese Such wird deutlich das es Zahlen gibt, die nicht in der Menge vorkommt $\rightarrow$ Widerspruch
- des weiteren können nicht alle reellen Zahlen auf die natürlichen Zahlen abgebildet werden
