BuK/IIm10/BuK-Übung10 G1
Aus ProgrammingWiki
Wiki-Quelltext dieser Seite.
<language>Scheme</language>
= Primitiv rekursive zahlentheoretische Funktionen =
== Aufgabenstellung ==
Weisen Sie nach, dass die folgenden zahlentheoretischen Funktionen primitiv rekursiv sind. Dabei dürfen Sie bereits auf das Ergebnis der folgenden Aufgabe zurückgreifen.
*Vorgängerfunktion <math>P(n)= \begin{cases}
0 & ,\text{wenn } n=0\\
n-1 & sonst
\end{cases}</math>
*Potenzfunktion <math>pot(x,a)=a^x</math>
*Fakultät <math>fak(n)=n!</math>
*Monus-Operation <math>x\dot{-}y=\begin{cases}
0 & ,\text{wenn } x \leq y\\
x-y & sonst
\end{cases}</math>
*Abstandsfunktion <math>|x-y|</math>
*Signum-Funktion <math>signum(n)</math>
== Lösung ==
Vorgängerfunktion:
<math>P(0)=C_0^1=0</math>
<math>P(n+1)=P(S(n))=U_1^2(n,P(n))=n</math>
Potenzfunktion:
<math>pot(0,a) = C_1^1=1</math>
<math>pot(S(x),a) = g(x,pot(x,a),a) = mult(U_3^3(x,pot(x,a),a), U_2^3(x,pot(x,a),a))</math>
Fakultät:
<math>fak(0) = C_1^1=1</math>
<math>fak(S(n))= g(n, fak(n)) = mult(S(n), U_2^2(n,fak(n))</math>
Monus-Operation:
<math>mon(0,x)=U_1^1(x)=x</math>
<math>mon(S(y),x)=P(U_2^3(y,mon(y,x),x))</math>
Abstandsfunktion:
<math>ab(x,y) = add(U_2^2(mon(y,x),mon(x,y)), U_1^2(mon(y,x),mon(x,y)))</math>
Signum-Funktion:
<math>signum(0) = C_0^0=0</math>
<math>signum(S(n)) = U_2^2(n, signum(n))</math>
= Konstante Funktionen =
== Aufgabenstellung ==
Unsere Definition der Menge der primitiv rekursiven Funktionen verwendet die Nullfunktionen als Basisfunktionen. Manche Quellen nehmen alternativ die konstanten Funktionen als Basisfunktionen auf. Zeigen Sie mit unserer Definitionsform, dass die konstanten Funktionen <math>C_q^r : \mathbb{N}_0^r \mapsto \mathbb{N}_0^r</math>, mit <math>C_q^r(n_1,n_2,....,n_r)=q</math>, primitiv rekursiv sind.
== Lösung ==
<!--<math>C_q^r(n_1,n_2,....,n_r) = f(g(n_1),g(n_2),....,g(n_r)) = f(U_1^r(n_1,n_2,...,n_r),U_2^r(n_1,n_2,...,n_r),.....,U_q^r(n_1,n_2,...,n_r))</math>-->
<math>C_q^r(n_1,n_2,...,n_r)=S_a^2(a,C_0^r(n_1,n_2,...,n_r))</math> (Die Funktion S wird a-mal aufgerufen.)
<math>S_a^2(0,m)=m</math>
<math>S_a^2(S(a),m)=S_a^2(a,S(m))</math>
Beispiel:
<math>S_a^2(3,10)=S_a^2(2,11)=S_a^2(1,12)=S_a^2(0,13)</math>
= Polynom-Funktionen=
== Aufgabenstellung ==
Begründen Sie, weshalb Polynome mit natürlichen Koeffizienten primitiv rekursiv sind.
Beispiel:<math>p(n)=an^2+bn+c</math>
== Lösung ==
Es kann gezeigt werden, dass die Addition, die Multiplikation und die Potenzfunktion primitiv-rekursiv sind. Die Polynom-Funktion kann durch Verwendung dieser drei Funktionen durch Substitution und Rekursion gebildet werden. Da dies möglich ist und die Funktionen wie bereits erwähnt primitiv-rekursiv sind, ist auch die Polynom-Funktion primitiv-rekursiv.
= Rechenoperationen =
== Aufgabenstellung ==
Folgen Sie dem Schema der rekursiven Definitionen der elementaren binären Rechenoperationen (Addition (1), Multiplikation (2), Potenzieren (3), ...) und entwickeln Sie eine entsprechende Scheme-Prozedur op. Verwenden Sie add1 für die Nachfolger- und sub1 für die Vorgängerfunktion.
Aufrufbeispiel: (op 3 10 2) liefert 1024.
== Lösung ==
<code id="4dfb0910563c0">
(define add
(lambda (a b)
(cond
((= 0 a) b)
(else
(add1 (add (sub1 a) b))))))
</code>
<run id="4dfb0dcb97fc8">(add 10 2)</run>
<code id="4dfb0dcb97efc">
(define mult
(lambda (a b)
(cond
((= 0 a) 0)
(else
(add (mult (sub1 a) b) b)))))
</code>
<run id="4dfb0dcb9801e">(mult 2 3)</run>
<code id="4dfb0dcb97f5b">(define pot
(lambda (x a)
(cond
((= 0 x) 1)
(else
(mult (pot (sub1 x) a) a)))))</code>
<run id="4dfb0dcb98073">(pot 3 2)</run>
<code id="4dff0cde484e0">
(define op
(lambda (nr a b)
(cond
((= nr 1) (add a b))
((= nr 2) (mult a b))
((= nr 3) (pot a b))
(else
"Die Operationsnummer ist zu groß!"))))
</code>
<run id="4dff0cde48566">(op 3 10 2)</run>
=Ackermann-Peter-Funktion=
==Aufgabe==
Die AP -Funktion ist eine total berechenbare Funktion, die jedoch nicht primitiv rekursiv
ist.
Sie ist wie folgt definiert.
<math>AP (0, m) = m + 1</math>
<math>AP (nr, 0) = AP (nr -1, 1)</math>
<math>AP (nr, m) = AP (nr -1, AP (nr, m - 1))</math>
Füllen Sie die folgende Tabelle aus, soweit es eben geht.
==Lösung==
[[Bild:Simaschi_Ack.PNG]]
==Aufgabe==
Geben Sie eine effizientere Implementation für AP an, indem Sie herausfinden, wie sich
die Tabelleneinträge in Zeile i aus denen in Zeile i−1 gewinnen (ablesen) lassen. Benutzen
Sie außerdem memoizing.
==Lösung==
<code id="4dfdf7e7c6560">
(define ack
(lambda (n m)
(if (= n 0)
(+ m 1)
(if (= m 0)
(ack (- n 1) 1)
(ack (- n 1) (ack n (- m 1)))))))
</code>
<run id="4dfdf7e7c6617">(ack 3 4)</run>
Hier die Ackermann-Peter-Funktion mit Memoizing.
<code>
(define nimm-oder-berechne
(lambda (fkt n m tabelle)
(let ([resultat (getprop tabelle (+(* n 100000) m))])
(if resultat
resultat
(let ([res (fkt n m)])
(putprop tabelle (+(* n 100000) m) res)
res)))))
(define ack-mem
(lambda (n m)
(if (= n 0)
(+ m 1)
(if (= m 0)
(nimm-oder-berechne ack-mem(- n 1) 1 'acks)
(nimm-oder-berechne ack-mem(- n 1) (nimm-oder-berechne ack-mem n (- m 1) 'acks) 'acks)))))
</code>
<run>(ack-mem 5 0)</run>
= Sudan-Funktion =
== Aufgabenstellung ==
Der rumänische Mathematiker Gabriel Sudan (14.04.1899 - 22.06.1977) – wie Ackermann ebenfalls ein Schüler von David Hilbert – hat 1927 eine total berechenbare jedoch nicht primitiv rekursive Funktion publiziert. Sie ist folgendermaßen definiert.
<math>\begin{array}{ccc}
F_0(x,y) & = & x+y\\
F_{n+1}(x, 0) & = & x, n \geq 0\\
F_{m+1}(x, y+1) & = & F_n(F_{n+1}(x, y), F_{n+1}(x, y) + y + 1), n \geq 0
\end{array}</math>
Berechnen Sie <math>F_1</math> und <math>F_2</math> für selbstgewählte Argumente.
<language>Scheme</language>
== Lösung ==
<code id="4dff69fb62793">
(define sudan
(lambda (n x y)
(cond
((= 0 n) (+ x y))
((= 0 y) x)
(else
(sudan (sub1 n) (sudan n x (sub1 y)) (+ y (sudan n x (sub1 y))))))))
</code>
<run id="4dff69fb62801">(sudan 1 0 6)</run>
<run id="4dff69fb62855">(sudan 2 1 2)</run>