BuK-Übung02 G2

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

Inhaltsverzeichnis

Halteproblem

Aufgabe

Lösung





Beweise
Kreativität
Schauen Sie sich das Video http://www.youtube.com/watch?v=oyo_oGUEH-I 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