BuK-Übung02 G2

Aus ProgrammingWiki
< BuK < IIm10
Archivierte Version vom 2011-03-28T16:54:51+00:00. Aktuelle Version

Inhaltsverzeichnis

Halteproblem

Aufgabe

Lösung





Beweise
Aufgabe 1
Zeigen Sie, dass die Menge der rationalen Zahlen abzählbar unendlich ist.
Lösung
Eine Menge ist dann abzählbar unendlich wenn sie gleichmächtig zur Menge der natürlichen Zahlen \mathbb{N} ist. Mit Cantors erstes Diagonalargument lässt sich zeigen, dass die unendliche Menge der rationalen Zahlen \mathbb{Q} gleichmächtig mit der Menge der natürlichen Zahlen \mathbb{N} ist.
Aufgabe 2
Zeigen Sie, dass die Wortmenge A^{\ast} über A abzählbar unendlich ist.
Aufgabe 3
Zeigen Sie, dass die Menge der reellen Zahlen überabzählbar unendlich ist.
Kreativität
Schauen Sie sich das Video an, um den Begriff der Kreativität besser zu verstehen.
Bijektive Funktion
Aufgabe
Verifizieren Sie, dass die folgende Funktion f : \mathbb{N}^{+} \rightarrow \mathbb{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 gerade};\\
\frac{1}{f(n - 1)}, & \text{wenn n ungerade}.
\end{cases}


Lösung
Scheme Prozedur




Handrechnung

\begin{array}{ccccc}
f(1) & = & 1 \\
f(2) & = & f(1) + 1 & = & 2 \\
f(3) & = & 1 / f(2) & = & 1 / 2 \\
f(4) & = & f(2) + 1 & = & 3 \\
f(5) & = & 1 / f(4) & = & 1 / 3 \\
f(6) & = & f(3) + 1 & = & 3 / 2 \\
f(7) & = & 1 / f(6) & = & 2 / 3 \\
...\\
\end{array}


Effizienzsteigerung mit Memoizing